基于格網(wǎng)劃分的道路最近鄰查詢算法

閆紅松，George Almpanidis，凡高娟

(河南大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，河南 開(kāi)封 475003)

0 引言

目前，地圖服務(wù)已經(jīng)成為人類(lèi)衣食住行必不可少的方式，在地圖服務(wù)中，查詢最近設(shè)施(例如，飯店、學(xué)校等)是最為普遍的，最近鄰查詢算法是其中最常用的算法。雖然目前的最近鄰查詢算法眾多且比較成熟，但是仍然面臨著巨大的挑戰(zhàn)。例如，現(xiàn)實(shí)中的物體數(shù)量遠(yuǎn)遠(yuǎn)大于被查詢的最近鄰設(shè)備數(shù)量；另外，真實(shí)的物體不僅與其自身的地理位置有關(guān)，還與其周?chē)鷱?fù)雜的地形以及路線有很大關(guān)系。這些因素都會(huì)增加對(duì)最近鄰物體查詢的難度。

為了解決現(xiàn)實(shí)問(wèn)題，有許多成熟的最近鄰算法，例如文獻(xiàn)[1]中的聚合關(guān)鍵字最近鄰(aggregate keyword nearest neighbor,ANN)算法,其基本思想是Dijkstra算法，以歐幾里得距離的形式計(jì)算最短路徑距離；文獻(xiàn)[1]中的增量網(wǎng)絡(luò)擴(kuò)張(incremental network expansion,INE)算法，是從Dijkstra算法派生出來(lái)的，記錄了當(dāng)前處理過(guò)的優(yōu)先級(jí)較高的一些頂點(diǎn)，也就是保存了到查詢點(diǎn)最近的點(diǎn)的集合。文獻(xiàn)[2]使用空間誘導(dǎo)連鎖認(rèn)知(spatially induced linkage cognizance,SILC)索引法解決K近鄰(K-nearest neighbor,KNN)查詢。在文獻(xiàn)[3]中,INE算法的搜索空間可能十分巨大，而路由轉(zhuǎn)換和關(guān)聯(lián)目錄(route overlay and association directory，ROAD)算法通過(guò)排除不包含目標(biāo)區(qū)域的搜索剪枝對(duì)INE算法進(jìn)行了優(yōu)化。文獻(xiàn)[4]同樣是以圖的劃分構(gòu)造一棵樹(shù)的索引，從而通過(guò)子圖層次來(lái)高效計(jì)算道路網(wǎng)絡(luò)之間的距離。這種劃分和ROAD算法中的劃分相似，通過(guò)遞歸按層次不斷劃分。與ROAD算法劃分不同的是，G-tree算法的每次劃分，每個(gè)點(diǎn)都屬于不同的區(qū)域，不存在交叉。文獻(xiàn)[5]更為詳細(xì)地描述了文獻(xiàn)[1-4]算法的效率分析。目前，最近鄰查詢也有通過(guò)對(duì)查詢區(qū)域進(jìn)行劃分的算法，例如，文獻(xiàn)[6]將查詢區(qū)域進(jìn)行格網(wǎng)劃分。然而，現(xiàn)有的最近鄰算法都是把數(shù)據(jù)點(diǎn)和道路視為頂點(diǎn)和邊的網(wǎng)絡(luò)圖[7]，這與現(xiàn)實(shí)生活并不完全一致，事實(shí)上，更多的物體是在道路內(nèi)，也就是點(diǎn)在邊上，而非只是在邊的端點(diǎn)。另一方面，現(xiàn)有最近鄰算法并沒(méi)有給出查詢點(diǎn)所在位置的具體算法，而是以頂點(diǎn)出發(fā)計(jì)算其最近鄰的點(diǎn)集合[8-16]。

針對(duì)以上問(wèn)題，本文結(jié)合INE算法[1]，設(shè)計(jì)了一種基于格網(wǎng)劃分的算法，將查詢區(qū)域進(jìn)行N×N的方格劃分，并且根據(jù)物體與道路真實(shí)的包含關(guān)系進(jìn)行結(jié)構(gòu)設(shè)計(jì)。這樣可以到達(dá)快速定位查詢點(diǎn)所在道路，進(jìn)而計(jì)算出道路最近鄰點(diǎn)，并且結(jié)合文獻(xiàn)[1]的算法計(jì)算其最近鄰點(diǎn)。

1 研究方法

本文定義全部道路構(gòu)成無(wú)向邊的集合E{ei|i∈I}，I為道路編號(hào)的集合；道路端點(diǎn)構(gòu)成頂點(diǎn)集合V{vi|i∈I}，I為頂點(diǎn)編號(hào)的集合；道路內(nèi)的數(shù)據(jù)點(diǎn)P{pi|i∈I}，I為數(shù)據(jù)點(diǎn)編號(hào)的集合。

1.1 道路分割

圖1 道路分割圖

當(dāng)查詢點(diǎn)Q落在某一子線段上，可以證明，若該子線段包含數(shù)據(jù)點(diǎn)，該數(shù)據(jù)點(diǎn)即所查找的最近鄰點(diǎn)；若該子線段不包含數(shù)據(jù)點(diǎn)，則必是道路端點(diǎn)，以該端點(diǎn)為起點(diǎn)通過(guò)INE算法[1]查找相鄰道路最近鄰點(diǎn)。具體證明如下：

顯然，除數(shù)據(jù)點(diǎn)P1、P2外，其他數(shù)據(jù)點(diǎn)距離查詢點(diǎn)Q更遠(yuǎn)，因此，只需證明P1和P2中哪個(gè)數(shù)據(jù)點(diǎn)距離查詢點(diǎn)Q更近。

1.2 格網(wǎng)劃分

i=k×n+l，k∈0,…,m；l∈0,…,n。

(1)

受Bresenham算法的啟發(fā)，本文計(jì)算每條道路經(jīng)過(guò)的單元格，并且記錄每個(gè)單元格所包含的子道路。道路經(jīng)過(guò)的單元格如圖3所示。

圖2 查詢區(qū)域格網(wǎng)劃分

圖3 道路經(jīng)過(guò)的單元格

根據(jù)笛卡爾二維坐標(biāo)系，以道路一個(gè)端點(diǎn)為坐標(biāo)原點(diǎn)，按照道路所在象限可分為4個(gè)方向，不考慮道路方向，即無(wú)向圖情況下，可將道路分為2個(gè)方向，道路邊的斜率k≥0或k<0。因此，可將4個(gè)方向的道路簡(jiǎn)化為2個(gè)方向，計(jì)算道路經(jīng)過(guò)的單元格，并記錄每個(gè)單元格包含的子道路。

1.3 矩形劃分

作為對(duì)比，還設(shè)計(jì)了單向格網(wǎng)劃分，或者稱(chēng)之為矩形劃分，利用分治法的思想，將查詢區(qū)域進(jìn)行格網(wǎng)劃分，只在水平或者垂直方向進(jìn)行等比例劃分。這里以垂直方向劃分為例進(jìn)行分析，水平方向與之類(lèi)似。

圖4 查詢區(qū)域矩形劃分

1.4 獲取查詢點(diǎn)最近鄰點(diǎn)

根據(jù)式(1)，由查詢點(diǎn)坐標(biāo)(x0,y0)獲取查詢點(diǎn)所在單元格，這里假設(shè)查詢點(diǎn)總是在某條道路上，從而，在查詢點(diǎn)所在單元格包含的子道路集合中必有一條子道路包含該查詢點(diǎn)，所以，由點(diǎn)到直線的距離為：

(2)

計(jì)算查詢點(diǎn)到所在單元格內(nèi)所有子道路的距離Di，使得Di=0的子道路sei即為查詢點(diǎn)所在子道路。根據(jù)圖1，由上文可知：當(dāng)該子道路包含數(shù)據(jù)點(diǎn)時(shí)，例如M1M2、M2M3，該數(shù)據(jù)點(diǎn)即查詢點(diǎn)最近鄰點(diǎn)；當(dāng)該子道路不包含數(shù)據(jù)點(diǎn)時(shí)，例如AM1、M3B，該子道路必包含所屬道路端點(diǎn)，以此端點(diǎn)為起點(diǎn)，通過(guò)INE算法[1]計(jì)算查詢點(diǎn)最近鄰點(diǎn)。

2 實(shí)驗(yàn)數(shù)據(jù)

本文的原始數(shù)據(jù)來(lái)自美國(guó)5個(gè)城市的地圖數(shù)據(jù)[17]，分別是加利福尼亞(CA)、舊金山(SF)、北美(NA)、圣華金縣(TG)和奧爾登堡(OL)。

原始數(shù)據(jù)由頂點(diǎn)和道路構(gòu)成，其中，頂點(diǎn)V(ID,X,Y)由頂點(diǎn)編號(hào)和坐標(biāo)構(gòu)成；道路R(ID,start_ID,end_ID)由道路編號(hào)、起點(diǎn)編號(hào)和終點(diǎn)編號(hào)構(gòu)成。

根據(jù)原始數(shù)據(jù)的頂點(diǎn)和道路,手動(dòng)設(shè)置邊上是否有數(shù)據(jù)點(diǎn)以及數(shù)據(jù)點(diǎn)的數(shù)量。本文按照比率P0隨機(jī)獲取N×P0條邊的索引，其中，N為邊的總數(shù)，對(duì)于這些邊的每條邊，按照邊上包含的數(shù)據(jù)點(diǎn)不超過(guò)M個(gè),以比率P1隨機(jī)獲取M×P1個(gè)百分比P{pi|i≤M×P1}，pi表示第i個(gè)數(shù)據(jù)點(diǎn)到所在邊起始點(diǎn)距離與邊長(zhǎng)的百分比，由此計(jì)算第i個(gè)數(shù)據(jù)點(diǎn)到所在邊起始點(diǎn)距離，生成道路數(shù)據(jù)點(diǎn)，其中，數(shù)據(jù)點(diǎn)DP(ID,X,Y,R_ID)由道路數(shù)據(jù)點(diǎn)編號(hào)、坐標(biāo)和所在道路編號(hào)構(gòu)成。按照以上方法，可生成查詢點(diǎn)QP(ID,X,Y)，

表1 美國(guó)5個(gè)城市的頂點(diǎn)、邊、數(shù)據(jù)點(diǎn)和查詢點(diǎn)

由查詢點(diǎn)編號(hào)和坐標(biāo)構(gòu)成。美國(guó)5個(gè)城市的頂點(diǎn)、邊、數(shù)據(jù)點(diǎn)和查詢點(diǎn)如表1所示。

3 實(shí)驗(yàn)結(jié)果與分析

本文按照劃分查詢區(qū)域設(shè)置不同比率p，包含數(shù)據(jù)點(diǎn)邊的頂點(diǎn)數(shù)與總頂點(diǎn)數(shù)比率p0=0.005，數(shù)據(jù)點(diǎn)的邊數(shù)與總邊數(shù)的不同比率p1，邊上包含數(shù)據(jù)點(diǎn)的最大數(shù)量p2=5，邊上包含查詢點(diǎn)的最大數(shù)量p3=2，對(duì)不同城市進(jìn)行實(shí)驗(yàn)分析，具體設(shè)置如表2所示。

表2 查詢區(qū)域劃分設(shè)置

根據(jù)表1的設(shè)置，分別對(duì)美國(guó)5個(gè)城市進(jìn)行實(shí)驗(yàn)，按包含數(shù)據(jù)點(diǎn)的邊數(shù)與總邊數(shù)比率p1=0.5的情況，對(duì)查詢區(qū)域劃分比率lgp分別為-4，-3，-2，-1的格網(wǎng)劃分、矩形劃分、INE算法查詢效率進(jìn)行實(shí)驗(yàn)分析，美國(guó)5個(gè)城市平均查詢時(shí)間如圖5所示。

(a) CA (b) OL (c) TG

(d) NA (e) SF

圖5 美國(guó)5個(gè)城市平均查詢時(shí)間

由圖5可知：隨著格網(wǎng)劃分比率的增大，格網(wǎng)劃分算法的平均查詢時(shí)間明顯低于現(xiàn)有INE算法。由圖5a可知：在查詢區(qū)域數(shù)據(jù)點(diǎn)較少的情況下，矩形劃分與格網(wǎng)劃分查詢時(shí)間差別較小，這主要是由于數(shù)據(jù)點(diǎn)較少時(shí)，矩形包含的數(shù)據(jù)點(diǎn)數(shù)量與格網(wǎng)包含的數(shù)據(jù)點(diǎn)數(shù)量差別較小所致，甚至可能是矩形劃分查詢時(shí)間比格網(wǎng)劃分查詢時(shí)間更小，如圖5b和圖5c所示。這說(shuō)明當(dāng)數(shù)據(jù)點(diǎn)比較少時(shí)，矩形劃分與格網(wǎng)劃分效果差別不大，從資源占用角度分析，當(dāng)數(shù)據(jù)點(diǎn)數(shù)量不大時(shí)，使用矩形劃分更為合理。由圖5d和圖5e可知：當(dāng)數(shù)據(jù)點(diǎn)數(shù)量極大時(shí)，格網(wǎng)劃分查詢時(shí)間明顯優(yōu)于矩形劃分查詢時(shí)間，這也說(shuō)明了當(dāng)數(shù)據(jù)量極大時(shí)，矩形包含的數(shù)據(jù)點(diǎn)數(shù)量遠(yuǎn)大于格網(wǎng)包含的數(shù)據(jù)點(diǎn)數(shù)量，使得定位查詢點(diǎn)時(shí)間較長(zhǎng)，以上分析更加說(shuō)明了格網(wǎng)劃分算法在大數(shù)據(jù)量下查詢效率提升顯著。

圖6為SF不同數(shù)據(jù)點(diǎn)平均查詢時(shí)間。由圖6可知：當(dāng)同一地區(qū)包含數(shù)據(jù)點(diǎn)數(shù)量不同時(shí)，基于格網(wǎng)劃分的查詢時(shí)間與INE算法的查詢時(shí)間有明顯不同。由圖6a可以看出：當(dāng)數(shù)據(jù)點(diǎn)較少時(shí)，格網(wǎng)劃分查詢時(shí)間與INE算法的查詢時(shí)間相近，這是由于數(shù)據(jù)點(diǎn)較少時(shí)，數(shù)據(jù)點(diǎn)出現(xiàn)在邊的端點(diǎn)的概率較大，而INE算法是基于頂點(diǎn)查詢的，因此當(dāng)數(shù)據(jù)點(diǎn)較少時(shí)格網(wǎng)劃分將退化為INE算法。由圖6b和圖6c可以看出：隨著數(shù)據(jù)點(diǎn)數(shù)量的增加，格網(wǎng)劃分的查詢時(shí)間明顯優(yōu)于INE算法的查詢時(shí)間。

(a)p1=0.01(b)p1=0.10(c)p1=0.50

圖6 SF不同數(shù)據(jù)點(diǎn)平均查詢時(shí)間

對(duì)比分析圖5和圖6可知：隨著格網(wǎng)劃分比率的增大，格網(wǎng)劃分算法的平均查詢時(shí)間明顯低于現(xiàn)有INE算法，同時(shí)矩形劃分介于格網(wǎng)劃分與INE算法之間，這說(shuō)明對(duì)查詢區(qū)域進(jìn)行劃分有效地降低了查詢時(shí)間；另一方面，說(shuō)明劃分區(qū)域過(guò)大對(duì)提升查詢效率是有限的。其次，通過(guò)圖6a可以看出：當(dāng)包含數(shù)據(jù)點(diǎn)的邊數(shù)與總邊數(shù)比率p1為0.01時(shí)，即在邊上的數(shù)據(jù)點(diǎn)不多的情況下，3種算法的平均查詢時(shí)間基本一致，這也表明本文的格網(wǎng)劃分算法對(duì)數(shù)據(jù)點(diǎn)大量在邊上的查詢效率明顯，當(dāng)邊上數(shù)據(jù)點(diǎn)不多的情況下，退化為INE算法。由圖6可以看出：對(duì)于不同比率p1，隨著格網(wǎng)劃分比率的增大，格網(wǎng)劃分算法的平均查詢時(shí)間都遠(yuǎn)小于INE算法的查詢時(shí)間，表明本文的算法對(duì)于超大數(shù)據(jù)量的執(zhí)行效率更高。

4 結(jié)束語(yǔ)

大數(shù)據(jù)量的道路最近鄰查詢效率問(wèn)題的解決一直存在困難，尤其是數(shù)據(jù)點(diǎn)在邊上而不只是作為邊的頂點(diǎn)出現(xiàn)，本文提出的算法通過(guò)將大圖劃分為小圖的分治思想，有效地解決了這個(gè)問(wèn)題，并且提高了查詢效率。根據(jù)實(shí)驗(yàn)結(jié)果分析，計(jì)算查詢點(diǎn)所在最近鄰，若查詢點(diǎn)所在子道路包含數(shù)據(jù)點(diǎn)則時(shí)間復(fù)雜度為O(1)，反之，則和INE算法復(fù)雜度相同。

本文算法不僅可以在道路最近鄰查詢中有很好的應(yīng)用，也可應(yīng)用在其他最近鄰相關(guān)算法，采用格網(wǎng)劃分可以避免全局搜索帶來(lái)的效率低下問(wèn)題。同時(shí)，可以應(yīng)用到地理信息系統(tǒng)及全球定位系統(tǒng)定位服務(wù)當(dāng)中，下一步將對(duì)格網(wǎng)劃分查詢算法內(nèi)存占用進(jìn)行優(yōu)化，以進(jìn)一步提升效率。