采用网络分区与预计算策略的k近邻查询算法

K-nearest neighbors queries using network partitions and precomputation

k近邻查询是GIS和空间数据库等领域的研究热点。文章针对道路网络中的k近邻查询,通过分区以及预计算近邻集策略,获得查询点的k近邻结果:首先利用自适应格网分区方法将道路网络划分为若干格网单元,并存储格网内节点与边界点、边界点之间距离;其次在网络中的节点预先存储近邻集。实验证明,在兴趣点密度高、k值较大情况下,算法具有较好的性能。

k-nearest neighbors （kNN） queries is a hot topic in fields of GIS and spatial databases, et al. To get kNN of query points, the approach based on the existed road networks was proposed by partitioning road networks and precomputing NNs. First, the road networks were divided into grid cells, and the distances between nodes and border points were saved in tables, then the precomputed NNs were prestored in nodes of networks. The experiments result showed that the method could reduce the expensive shortest path computation and the search space, optimize kNN query algorithm with good performance.