基于路网的k最近邻查询算法综述

陈小迪 冯诚

摘 要：在互联网时代，基于地理位置的服务越来越普遍，k最近邻查询通过与给定位置的距离来检索k个最近的兴趣点（POIs），是一个与之高度相关的查询。与欧式空间相比，基于路网的k最近邻查询的研究更具有现实的意义和价值，同时也面临着更大的挑战，引起了国内外学者的广泛关注。本文将对基于路网的k最近邻查询算法的研究进展进行综述，并展望该问题未来的研究方向和重点。

关键词：基于地理位置的服务;路网;k最近邻;最短路径;路网距离

文章编号：2095-2163（2019）04-0202-04 中图分类号：TP301.6 文献标志码：A

0 引 言

近年来，随着移动互联网、全球定位系统和地理信息等技术的迅猛发展，以及使用移动设备的人数的爆炸式增长，基于地理位置的服务（Location-Based Services，LBS）也变得越来越普遍。k最近邻查询作为基于地理位置服务中十分重要的支持性技术之一，成为学术界的研究热点。

k最近邻查询，即在给定的空间数据集中，返回距离查询顶点最近的k个数据对象，主要包括基于欧式空间和基于路网的2类。传统的k最近邻技术都是基于欧式空间的[2-4]。例如，用户使用美团时，若选择以“离我最近”的方式显示查询结果，就是根据用户与查询目标之间的欧式距离即直线距离进行排序的。因为2点之间的欧式距离只与坐标有关，比较容易计算，所以传统的k最近邻查询技术目前已经趋于成熟。但是人们在日常生活中，位置和运动往往都会受到道路网络建设的约束，不可能完全按直线移动，所以，基于路网的k最近邻查询技术越来越受到国内外学者的关注。

基于路网的k最近邻查询，相对基于欧式空间的k最近邻查询面临着更大的挑战。由于道路网络的数据规模相当庞大且数据结构复杂多样，要求查询算法必须具有良好的存储结构以及可扩展性。而且，基于路网的k最近邻查询在很大程度上与最短路径（或路网距离）有关，不如欧式距离容易计算，要求算法设计出能够快速确定2点间最短路径的方法。同时，查询对象的总数通常比k大得多，如果通过计算所有对象到查询位置的最短路径距离，来获取k最近邻结果是不高效的，这就要求算法设计出高效的剪枝策略，能够尽可能多的忽略不是k最近邻的对象和与查询对象无关的路网转换。

目前，基于路网的k最近邻查询技术已经得到了很大的发展，本文将对有价值的研究成果进行综述。文献[1]对比较典型的查询算法进行了实现和比较INE[6]、IER[6]、DisBrw[7]、ROAD[8-9]和 G-tree[10-11]方法。文献[5]分别对基于 Dijkstra 式搜索模式、基于启发式扩展模式、基于相邻区域迭代式扩展模式的k最近邻查询算法进行了分析和总结。

1 问题定义

连续k最近邻查询（Continuous k Nearest Neighbor Query， CkNN）：指在图G中，查询点q和查詢对象至少一方是移动的k最近邻查询。

2 基于路网的k最近邻查询算法

针对基于路网的k最近邻查询问题，已经涌现出来很多经典的算法。根据算法所用的查询方式主要分为2类：基于扩展的，例如本节中介绍的INE[6]、Island[13]、S-GRID[14]、ROAD[8-9]算法等;基于最佳优先遍历的，如本节介绍的IER[6]、DisBrw[7]、G-tree[10-11]、DS-tree[15]算法等。

在文献[6]中，Papadias等人提出了INE和IER 2种方法。其中，INE是扩展的Dijkstra算法，从查询位置逐步向邻近点扩展，直到获得k最近邻结果。IER利用空间修剪技术改进了INE，即通过欧式距离作为启发式从O中检索候选对象，因为其是任意连通2点之间距离的下界。

文献[12]中，Kolahdouzan和Shahabi提出了基于网络Voronoi图的方法，用于将空间网络划分为NVP，每个数据对应一个NVP。并用空间访问法对NVPs进行索引，将问题简化为欧式空间中的点定位问题。并通过对网络vps的预计算最小化在线网络距离。

文献[13]使用了Island方法解决k最近邻查询问题，以每个数据对象为中心，给定的r为半径形成Island，Island所覆盖的点都与其中心相关联。在该方法中，同时使用了预先计算的Island和从查询点开始的受限网络扩展。

文献[14]中引入了S-GRID算法，将空间网络划分为不相交的子网，并预先计算每对边界点的最短路径。为了找到k最近邻，首先在子网内执行网络扩展，然后利用预先计算的信息进行边界点之间的外部扩展。

在文献[7]中，Samet等人提出了DisBrw方法，预先计算所有顶点对之间的最短路径，并使用基于四叉树的编码进行存储，通过将欧几里德距离存储为最短路径距离边界，然后具体找到k最近邻。

文献[8-9]提出了ROAD算法，通过建立路网索引和目标索引来实现对搜索空间的修剪，使整个算法更快地查询到最近的对象。构建路网索引时，将其划分为若干子图，对每个子图保存所有边界点之间的最短路径距离，如图2所示。在进行k最近邻查询时，根据目标索引若发现某个子图中没有查询对象，则直接利用这些快捷方式跳过对该子图的遍历。

文献[10-11]中提出了G-tree算法，通过G-tree索引以及最佳优先遍历的方法能够快速获得k最近邻查询结果，这也是目前最先进的算法之一。在G-tree索引中，每个树节点都存储了一个距离矩阵，用于查询过程中快速计算q与查询对象之间的最短路径距离（使用基于拼接的方法）。同时，该算法构建目标索引发生列表，使那些没有目标对象的G-tree节点被过滤掉。

文献[15]中，采用新的索引技术DS-tree解决了G-tree算法在LCA（u， v）中计算最短路径可能出现错误的局部性的问题。DS-tree中除根节点之外的所有节点都存储的是其子节点集合的收缩图，能够快速计算2点的最短路径距离。

3 连续k最近邻查询技术

连续k最近邻查询技术在日常生活中有广泛的应用，例如用户在某一位置查询距离自己最近的空闲出租车。出租车是处于运动状态的，且随着出租车的移动，返回的结果也会发生变化。

文献[16]中，Kyriakos Mouratidis等人提出了IMA和GMA 2种实现技术。 IMA用扩展树进行存储，只有扩展树中的对象和边更新时，才能改变q的最近邻结果，从而忽略了无关更新。当最近邻结果更新或q移动到新位置时，IMA保持扩展树中的有效部分，这样能很快查询到新的k最近邻结果。GMA则使用IMA监视交叉点的k最近邻结果有效地计算路径中所有查询结果。

文献[17]中，Long Guo、 Jie Shao等人提出了2种以递增方式遍历网络的方法，即以查询为中心的算法（QCA）和以对象为中心的算法（OCA），这2种方法都维护一个树结构减少网络边缘的重复遍历，以获得更好的性能。

文献[18]提出了一种基于对象模型运动状态的对象候选处理（OCP）算法。在修剪阶段，算法修剪在给定时间间隔内不会是k最近邻查询结果的对象;在精炼阶段，确定给定时间间隔中能获得k最近邻查询结果的子间隔。

文献[19]提出了一种新的索引V-Tree，有2个显著的特征：一是平衡的搜索树，可以支持高效的连续k最近邻查询;此外，还可以支持移动对象的动态更新。同时，在查询时还使用边界来有效地计算k最近邻。

文献[20]中，Kyoungso提出了一种基于模式的方法，利用距离关系模式（DRP）来有效地处理连续k最近邻查询的方法。DRP是按照单元格中的点与其它单元格之间的距离按升序排序的相对坐标列表，以便通过顺序访问单元格。

4 结束语

基于路网的k最近邻查询技术目前已经取得了很多有价值的研究成果，给人们的生活带来了极大的便利。当然，随着路网日趋复杂以及人们的查询需求日趋多样，基于路网的k最近邻查询技术在深度和广度上都还有很大的发展空间。例如，从深度上讲，研究出速度更快、准确率更高的查询技术;从广度上讲，对更多的k最近邻变体技术进行研究，例如基于关键字的k最近邻查询、偏好k最近邻查询等。

参考文献

[1]ABEYWICKRAMA T， CHEEMA M A， TANIAR D. K-nearest neighbors on road networks：A journey in experimentation and in-memory implementation[J].Proc. of the VLDB Endowment， 2016，9（6）：492-503.

[2]SEIDL T， KRIEGEL H P. Optimal multi-step k-nearest neighbor search[J]. ACM SIGMOD Record， 1998， 27（2）：154-165.

[3]SHARIFZADEH M， SHAHABI C. Vor-Tree：R-trees with voronoi diagrams for efficient processing of spatial nearest neighbor queries[J].Proceedings of the VLDB Endowment， 2010，3（1-2）：1231-1242.

[4]JI Shengyue， LI Chen. Location-based instant search[C]//BAYARD C J， FRENCH J， BOWERS S. Scientific and Statistical Database Management. SSDBM 2011. Lecture Notes in Computer Science. Berlin/Heidelberg：Springer， 2011，6809：17-36.

[5]鮑金玲，王斌，杨晓春，等. 路网环境下的最近邻查询技术[J]. 软件学报，2018，29（3）：642-662.

[6]PAPADIAS D， ZHANG Jun， MAMOULIS N， et al. Query processing in spatial network databases[C]//Proceedings 2003 VLDB Conference.Berlin， Germany：dblp， 2008：802-813.

[7]SAMET H， SANKARANARAYANAN J， ALBORZI H. Scalable network distance browsing in spatial databases[C]// Proceedings of the ACM SIGMOD International Conference on Management of Data（ SIGMOD 2008）. Vancouver， BC， Canada：IEEE， 2008：43-54.

[8]LEE K C K， LEE W C， ZHENG Baihua， et al. Road：A new spatial object search framework for road networks[J].IEEE Transactions on Knowledge and Data Engineering 2012，24（3）：547-560.

[9]LEE K C K， LEE W C， ZHENG Baihua. Fast object search on road networks[C]// 12th International Conference on Extending Database Technology（EDBT 2009）. Saint Petersburg， Russia：ACM， 2009：1018-1029.

[10]ZHONG Ruicheng， LI Guoliang，TAN K L，et al. Gong. G-tree：An efficient and scalable index for spatial search on road networks[J].IEEE Transactions on Knowledge and Data Engineering，2015，27（8）：2175-2189.

[11]ZHONG Ruicheng， LI Guoliang， TAN K L，et al. G-tree：An efficient index for KNN search on road networks[C]//Proceedings of the 22nd ACM International Conference on Conference on Information & Knowledge Management.San Francisco， California， USA：ACM ，2013：39-48.

[12]KOLAHDOUZAN M， SHAHABI C. Voronoi-based k nearest neighbor search for spatial network databases[C]//Proc. the 30th VLDB. Toronto：VLDB Endowment， 2004：840-851.

[13]HUANG Xuebing， JENSEN C S， ALTENIS S. The island approach to nearest neighbor querying in spatial networks[C]// BAUZER M C， EGENHOFER M J， BERTINO E. Advances in Spatial and Temporal Databases. SSTD 2005. Lecture Notes in Computer Science， Berlin/ Heidelberg：Springer ，2005，3633：73-90.

[14]HUANG Xuegang， JENSEN C S，LU Hua， et al. S-grid：A versatile approach to efficient query processing in spatial networks[C]// PAPADIAS D， ZHANG D， KOLLIOS G. Advances in Spatial and Temporal Databases. SSTD 2007. Lecture Notes in Computer Science， Berlin/ Heidelberg：Springer， 2007，4605：93-111.

[15]彭勃. 大數据环境下道路网Top-k查询优化技术研究与实现[D]. 哈尔滨：哈尔滨工业大学，2016.

[16]MOURATIDIS K， YIU M L， PAPADIAS D， et al. Continuous nearest neighbor monitoring in road networks[C]// Proceedings of the 32nd International Conference on Very Large Data Bases. Seoul， Korea：dblp，2006：43-54.

[17]GUO Long， SHAO Jie， AUNG H H， et al. Efficient continuous top-k spatial keyword queries on road networks[J].GeoInformatica，2015， 19（1）：29-60.

[18]FAN Ping， LI Guohui， YUAN Ling. Continuous K-nearest neighbor processing based on speed and direction of moving objects in a road network[J]. Telecommunication Systems， 2014，55（3）：403-419.

[19]SHEN Bilong， ZHAO Ying， LI Guoliang， et al. V-tree：Efficient kNN search on moving objects with road-network constraints[C]// 2017 IEEE 33rd International Conference on Data Engineering （ICDE）. San Diego. CA， USA：IEEE， 2017：609-620.

[20]BOK K， PARK Y， YOO J. An efficient continuous k-nearest neighbor query processing scheme for multimedia data sharing and transmission in location based services[J]. Multimedia Tools and Applications， 2019， 78（5）：5403-5426.