基于路網的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.