陳小迪 馮誠

摘 要：在互聯(lián)網(wǎng)時(shí)代，基于地理位置的服務(wù)越來越普遍，k最近鄰查詢通過與給定位置的距離來檢索k個最近的興趣點(diǎn)（POIs），是一個與之高度相關(guān)的查詢。與歐式空間相比，基于路網(wǎng)的k最近鄰查詢的研究更具有現(xiàn)實(shí)的意義和價(jià)值，同時(shí)也面臨著更大的挑戰(zhàn)，引起了國內(nèi)外學(xué)者的廣泛關(guān)注。本文將對基于路網(wǎng)的k最近鄰查詢算法的研究進(jìn)展進(jìn)行綜述，并展望該問題未來的研究方向和重點(diǎn)。

關(guān)鍵詞：基于地理位置的服務(wù);路網(wǎng);k最近鄰;最短路徑;路網(wǎng)距離

文章編號：2095-2163（2019）04-0202-04 中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼：A

0 引 言

近年來，隨著移動互聯(lián)網(wǎng)、全球定位系統(tǒng)和地理信息等技術(shù)的迅猛發(fā)展，以及使用移動設(shè)備的人數(shù)的爆炸式增長，基于地理位置的服務(wù)（Location-Based Services，LBS）也變得越來越普遍。k最近鄰查詢作為基于地理位置服務(wù)中十分重要的支持性技術(shù)之一，成為學(xué)術(shù)界的研究熱點(diǎn)。

k最近鄰查詢，即在給定的空間數(shù)據(jù)集中，返回距離查詢頂點(diǎn)最近的k個數(shù)據(jù)對象，主要包括基于歐式空間和基于路網(wǎng)的2類。傳統(tǒng)的k最近鄰技術(shù)都是基于歐式空間的[2-4]。例如，用戶使用美團(tuán)時(shí)，若選擇以“離我最近”的方式顯示查詢結(jié)果，就是根據(jù)用戶與查詢目標(biāo)之間的歐式距離即直線距離進(jìn)行排序的。因?yàn)?點(diǎn)之間的歐式距離只與坐標(biāo)有關(guān)，比較容易計(jì)算，所以傳統(tǒng)的k最近鄰查詢技術(shù)目前已經(jīng)趨于成熟。但是人們在日常生活中，位置和運(yùn)動往往都會受到道路網(wǎng)絡(luò)建設(shè)的約束，不可能完全按直線移動，所以，基于路網(wǎng)的k最近鄰查詢技術(shù)越來越受到國內(nèi)外學(xué)者的關(guān)注。

基于路網(wǎng)的k最近鄰查詢，相對基于歐式空間的k最近鄰查詢面臨著更大的挑戰(zhàn)。由于道路網(wǎng)絡(luò)的數(shù)據(jù)規(guī)模相當(dāng)龐大且數(shù)據(jù)結(jié)構(gòu)復(fù)雜多樣，要求查詢算法必須具有良好的存儲結(jié)構(gòu)以及可擴(kuò)展性。而且，基于路網(wǎng)的k最近鄰查詢在很大程度上與最短路徑（或路網(wǎng)距離）有關(guān)，不如歐式距離容易計(jì)算，要求算法設(shè)計(jì)出能夠快速確定2點(diǎn)間最短路徑的方法。同時(shí)，查詢對象的總數(shù)通常比k大得多，如果通過計(jì)算所有對象到查詢位置的最短路徑距離，來獲取k最近鄰結(jié)果是不高效的，這就要求算法設(shè)計(jì)出高效的剪枝策略，能夠盡可能多的忽略不是k最近鄰的對象和與查詢對象無關(guān)的路網(wǎng)轉(zhuǎn)換。

目前，基于路網(wǎng)的k最近鄰查詢技術(shù)已經(jīng)得到了很大的發(fā)展，本文將對有價(jià)值的研究成果進(jìn)行綜述。文獻(xiàn)[1]對比較典型的查詢算法進(jìn)行了實(shí)現(xiàn)和比較INE[6]、IER[6]、DisBrw[7]、ROAD[8-9]和 G-tree[10-11]方法。文獻(xiàn)[5]分別對基于 Dijkstra 式搜索模式、基于啟發(fā)式擴(kuò)展模式、基于相鄰區(qū)域迭代式擴(kuò)展模式的k最近鄰查詢算法進(jìn)行了分析和總結(jié)。

1 問題定義

連續(xù)k最近鄰查詢（Continuous k Nearest Neighbor Query， CkNN）：指在圖G中，查詢點(diǎn)q和查詢對象至少一方是移動的k最近鄰查詢。

2 基于路網(wǎng)的k最近鄰查詢算法

針對基于路網(wǎng)的k最近鄰查詢問題，已經(jīng)涌現(xiàn)出來很多經(jīng)典的算法。根據(jù)算法所用的查詢方式主要分為2類：基于擴(kuò)展的，例如本節(jié)中介紹的INE[6]、Island[13]、S-GRID[14]、ROAD[8-9]算法等;基于最佳優(yōu)先遍歷的，如本節(jié)介紹的IER[6]、DisBrw[7]、G-tree[10-11]、DS-tree[15]算法等。

在文獻(xiàn)[6]中，Papadias等人提出了INE和IER 2種方法。其中，INE是擴(kuò)展的Dijkstra算法，從查詢位置逐步向鄰近點(diǎn)擴(kuò)展，直到獲得k最近鄰結(jié)果。IER利用空間修剪技術(shù)改進(jìn)了INE，即通過歐式距離作為啟發(fā)式從O中檢索候選對象，因?yàn)槠涫侨我膺B通2點(diǎn)之間距離的下界。

文獻(xiàn)[12]中，Kolahdouzan和Shahabi提出了基于網(wǎng)絡(luò)Voronoi圖的方法，用于將空間網(wǎng)絡(luò)劃分為NVP，每個數(shù)據(jù)對應(yīng)一個NVP。并用空間訪問法對NVPs進(jìn)行索引，將問題簡化為歐式空間中的點(diǎn)定位問題。并通過對網(wǎng)絡(luò)vps的預(yù)計(jì)算最小化在線網(wǎng)絡(luò)距離。

文獻(xiàn)[13]使用了Island方法解決k最近鄰查詢問題，以每個數(shù)據(jù)對象為中心，給定的r為半徑形成Island，Island所覆蓋的點(diǎn)都與其中心相關(guān)聯(lián)。在該方法中，同時(shí)使用了預(yù)先計(jì)算的Island和從查詢點(diǎn)開始的受限網(wǎng)絡(luò)擴(kuò)展。

文獻(xiàn)[14]中引入了S-GRID算法，將空間網(wǎng)絡(luò)劃分為不相交的子網(wǎng)，并預(yù)先計(jì)算每對邊界點(diǎn)的最短路徑。為了找到k最近鄰，首先在子網(wǎng)內(nèi)執(zhí)行網(wǎng)絡(luò)擴(kuò)展，然后利用預(yù)先計(jì)算的信息進(jìn)行邊界點(diǎn)之間的外部擴(kuò)展。

在文獻(xiàn)[7]中，Samet等人提出了DisBrw方法，預(yù)先計(jì)算所有頂點(diǎn)對之間的最短路徑，并使用基于四叉樹的編碼進(jìn)行存儲，通過將歐幾里德距離存儲為最短路徑距離邊界，然后具體找到k最近鄰。

文獻(xiàn)[8-9]提出了ROAD算法，通過建立路網(wǎng)索引和目標(biāo)索引來實(shí)現(xiàn)對搜索空間的修剪，使整個算法更快地查詢到最近的對象。構(gòu)建路網(wǎng)索引時(shí)，將其劃分為若干子圖，對每個子圖保存所有邊界點(diǎn)之間的最短路徑距離，如圖2所示。在進(jìn)行k最近鄰查詢時(shí)，根據(jù)目標(biāo)索引若發(fā)現(xiàn)某個子圖中沒有查詢對象，則直接利用這些快捷方式跳過對該子圖的遍歷。

文獻(xiàn)[10-11]中提出了G-tree算法，通過G-tree索引以及最佳優(yōu)先遍歷的方法能夠快速獲得k最近鄰查詢結(jié)果，這也是目前最先進(jìn)的算法之一。在G-tree索引中，每個樹節(jié)點(diǎn)都存儲了一個距離矩陣，用于查詢過程中快速計(jì)算q與查詢對象之間的最短路徑距離（使用基于拼接的方法）。同時(shí)，該算法構(gòu)建目標(biāo)索引發(fā)生列表，使那些沒有目標(biāo)對象的G-tree節(jié)點(diǎn)被過濾掉。

文獻(xiàn)[15]中，采用新的索引技術(shù)DS-tree解決了G-tree算法在LCA（u， v）中計(jì)算最短路徑可能出現(xiàn)錯誤的局部性的問題。DS-tree中除根節(jié)點(diǎn)之外的所有節(jié)點(diǎn)都存儲的是其子節(jié)點(diǎn)集合的收縮圖，能夠快速計(jì)算2點(diǎn)的最短路徑距離。

3 連續(xù)k最近鄰查詢技術(shù)

連續(xù)k最近鄰查詢技術(shù)在日常生活中有廣泛的應(yīng)用，例如用戶在某一位置查詢距離自己最近的空閑出租車。出租車是處于運(yùn)動狀態(tài)的，且隨著出租車的移動，返回的結(jié)果也會發(fā)生變化。

文獻(xiàn)[16]中，Kyriakos Mouratidis等人提出了IMA和GMA 2種實(shí)現(xiàn)技術(shù)。 IMA用擴(kuò)展樹進(jìn)行存儲，只有擴(kuò)展樹中的對象和邊更新時(shí)，才能改變q的最近鄰結(jié)果，從而忽略了無關(guān)更新。當(dāng)最近鄰結(jié)果更新或q移動到新位置時(shí)，IMA保持?jǐn)U展樹中的有效部分，這樣能很快查詢到新的k最近鄰結(jié)果。GMA則使用IMA監(jiān)視交叉點(diǎn)的k最近鄰結(jié)果有效地計(jì)算路徑中所有查詢結(jié)果。

文獻(xiàn)[17]中，Long Guo、 Jie Shao等人提出了2種以遞增方式遍歷網(wǎng)絡(luò)的方法，即以查詢?yōu)橹行牡乃惴ǎ≦CA）和以對象為中心的算法（OCA），這2種方法都維護(hù)一個樹結(jié)構(gòu)減少網(wǎng)絡(luò)邊緣的重復(fù)遍歷，以獲得更好的性能。

文獻(xiàn)[18]提出了一種基于對象模型運(yùn)動狀態(tài)的對象候選處理（OCP）算法。在修剪階段，算法修剪在給定時(shí)間間隔內(nèi)不會是k最近鄰查詢結(jié)果的對象;在精煉階段，確定給定時(shí)間間隔中能獲得k最近鄰查詢結(jié)果的子間隔。

文獻(xiàn)[19]提出了一種新的索引V-Tree，有2個顯著的特征：一是平衡的搜索樹，可以支持高效的連續(xù)k最近鄰查詢;此外，還可以支持移動對象的動態(tài)更新。同時(shí)，在查詢時(shí)還使用邊界來有效地計(jì)算k最近鄰。

文獻(xiàn)[20]中，Kyoungso提出了一種基于模式的方法，利用距離關(guān)系模式（DRP）來有效地處理連續(xù)k最近鄰查詢的方法。DRP是按照單元格中的點(diǎn)與其它單元格之間的距離按升序排序的相對坐標(biāo)列表，以便通過順序訪問單元格。

4 結(jié)束語

基于路網(wǎng)的k最近鄰查詢技術(shù)目前已經(jīng)取得了很多有價(jià)值的研究成果，給人們的生活帶來了極大的便利。當(dāng)然，隨著路網(wǎng)日趨復(fù)雜以及人們的查詢需求日趨多樣，基于路網(wǎng)的k最近鄰查詢技術(shù)在深度和廣度上都還有很大的發(fā)展空間。例如，從深度上講，研究出速度更快、準(zhǔn)確率更高的查詢技術(shù);從廣度上講，對更多的k最近鄰變體技術(shù)進(jìn)行研究，例如基于關(guān)鍵字的k最近鄰查詢、偏好k最近鄰查詢等。

參考文獻(xiàn)

[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]鮑金玲，王斌，楊曉春，等. 路網(wǎng)環(huán)境下的最近鄰查詢技術(shù)[J]. 軟件學(xué)報(bào)，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]彭勃. 大數(shù)據(jù)環(huán)境下道路網(wǎng)Top-k查詢優(yōu)化技術(shù)研究與實(shí)現(xiàn)[D]. 哈爾濱：哈爾濱工業(yè)大學(xué)，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.