种基于路网的连续最近邻查询算法.doc

一种基于路网的连续 摘 要：路网中的密度UNICONS等改进了这些不足。然而在查询对象密集分布的路网中，存在无效计算最近邻（Nearest Neighbor，NN）的问题。针对这个问题，本文提出并证明了非交叉点子路径中的预计算方法，并基于该方法提出了CNN查询算法。该算法利用分治法以交叉点为划分依据，将查询路径划分成子路径，然后对子路径中的结点进行NN查询，从而降低了NN查询的计算代价。通过实验，验证了本文提出的查询处理方法在CNN查询中的正确性和有效性，性能优势尤为明显。 关键词：最近邻查询; 基于位置的服务UNICONS; 预计算方法; 分治算法 Algorithm for CNN Query over Road Network Wang Heng1,2 Ying-Yuan Xiao1,2 1Tianjin Key Laboratory of Intelligence Computing and Novel Software Technology, Tianjin University of Technology，300384, Tianjin 2Key Laboratory of Computer Vision and System （Tianjin University of Technology）, Ministry of Education, 300384, Tianjin Abstract In Road Network (RN), Continuous Nearest Neighbor (CNN) query frequently used in Location-Based Services (LBS). The majority of the existing works on CNN queries are largely affected by the density of objects of interest, others such as UNICONS overcome these problems, yet there may be over-calculating problem. In this paper, we propose and proof a pre-computation theory based on non-intersection path, and then presented an algorithm for CNN query, which uses divide and conquer method to query NN on sub path, where is divided the query path into sub path based on non-intersection points, and then to reduce the computational cost. Experimental results show that our processing approach in the CNN query is correct and effective, especially the result is well performance when the intersection points sparsely distributed. Keywords CNN; LBS; UNICONS; pre-computation; divide and conquer method 1 引言 随着移动计算、无线通讯、GIS（Geographic Information System）、以及GPS空间定位、空间网络数据库（SNDB）等技术的迅速发展，基于位置的服务（Location-Based-Service, LBS）得到了广泛的应用。连续最近邻（Continuous Nearest Neighbor）查询作为LBS中重要的查询类型，引起了国内外学者的。Feng等人[]提出一种启发式计算的区域，。只能k=1的CNN查询。之后，Kolahdouzan 等人[]提出了基于VN3（Voronoi-Based Network Nearest Neighbor）的CNN查询UBA（Upper Bound Algorithm）。但该方法需要进行大量的NN查询来查找划分点，查询NN的VN3方法，依赖于路网中的密度和k值的大小。Cho等人[]提出了一种UNICONSa Unique Continuous Search algorithm）处理方法，该方法NN对象列表，Dijkstra算法。该方法的优势不依赖路网中的密度，因此表现出较好的性能。但发现在处