基于4-叉樹結(jié)構(gòu)的路網(wǎng)數(shù)據(jù)最近鄰查詢算法

陳可心，陳業(yè)斌

(安徽工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，安徽馬鞍山243032)

路網(wǎng)數(shù)據(jù)由于其結(jié)構(gòu)的復(fù)雜性和龐大的數(shù)據(jù)量，使用一般的查詢算法很難滿足其對興趣點(point of interest，POI)查詢效率的需求[1-3]。如何利用新的查詢算法或改進現(xiàn)有的查詢算法來提高查詢效率是一個值得研究的問題。鮑金玲等[4]綜述了路網(wǎng)環(huán)境下的最近鄰查詢技術(shù)，對2018年之前應(yīng)用在路網(wǎng)領(lǐng)域中的查詢算法進行了比較分析；陳業(yè)斌等[5]提出基于Spark SQL(structured query language)的查詢方法，在Spark 中嵌入索引管理機制，將其封裝在彈性分布式數(shù)據(jù)集內(nèi)，用于提高查詢效率；于啟迪等[6]通過對線性樹型結(jié)構(gòu)的改進，提出一種基于自適應(yīng)虛擬樹存儲結(jié)構(gòu)、利用空間關(guān)鍵詞查詢來提高查詢效率的查詢算法；Bok等[7]、Chan等[8]提出利用不同單元格點距離的排序構(gòu)建索引表，以此提高k近鄰查詢的效率；陳小迪等[9]對基于路網(wǎng)k近鄰查詢的相關(guān)算法進行了比較，并展望k近鄰查詢算法未來的研究方向和重點；閆紅松等[10]利用分治法的思想，將查詢區(qū)域進行網(wǎng)格劃分，縮小有效的查詢區(qū)域，快速定位查詢點所在路徑，進而找到最近鄰數(shù)據(jù)點；朱良等[11]提出了k聚集最近鄰數(shù)據(jù)查詢方法?，F(xiàn)有文獻多聚焦于查詢算法本身的效率改進，較少關(guān)注數(shù)據(jù)本身的存取問題。鑒于此，文中提出一個新的思想：利用Voronoi圖對空間進行劃分，確定興趣點的位置，利用空間分區(qū)技術(shù)將空間劃分至理想大小，利用4-叉樹結(jié)構(gòu)存儲興趣點，并建立相應(yīng)的索引表，最后結(jié)合最近鄰查詢算法找出最近的興趣點。

1 空間數(shù)據(jù)最近鄰查詢相關(guān)技術(shù)

最近鄰(the nearest neighbor，NN)查詢?yōu)榭臻g數(shù)據(jù)查詢中應(yīng)用比較普通的一種查詢技術(shù)，其查詢思想可描述為：給定網(wǎng)絡(luò)數(shù)據(jù)集K和查詢點q，在網(wǎng)絡(luò)數(shù)據(jù)集K中查詢q距離最接近的點p(p∈K)，若找到返回點p，則點p為數(shù)據(jù)集K中與查詢點q的最近鄰點。路網(wǎng)空間數(shù)據(jù)集K中，通常稱查詢的目標點p為興趣點(POI)，這種興趣點通常不止一個，以|q，pi|表示q和pi兩點之間的距離，q的最近鄰點p用NN(K)表示，如式(1)

Voronoi圖是由一組連接兩點的垂直平分線構(gòu)成的連續(xù)多邊形組成，又稱泰森多邊形。假設(shè)歐氏空間的點集P={p1，p2，…，pn}，Voronoi圖以點集P中的每一點作為生成元來劃分平面區(qū)域，如式(2)

其中：V(pi)為劃分出的平面區(qū)域；d(p,pi)表示點p 到點pi的距離。Voronoi 圖具有按距離劃分臨近區(qū)域的特征，使用Voronoi圖可將空間數(shù)據(jù)集劃分為n個空間單元，使用不同標識(identification，id)號標識不同的單元，并將單元中興趣點的相關(guān)信息存儲到相應(yīng)數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)結(jié)構(gòu)中至少包含id(即空間單元id)、內(nèi)容和位置坐標等信息。給定任意查詢源點q，若查詢q點的最近鄰點(目標點)，需遍歷所有POI。

2 路網(wǎng)空間結(jié)構(gòu)化分區(qū)與信息存儲

在歐氏空間中，若查詢最近鄰，則需遍歷所有的POI，查詢效率不高。文中以路網(wǎng)數(shù)據(jù)及其結(jié)構(gòu)為研究對象，首先對其空間結(jié)構(gòu)進行均分，用樹型結(jié)構(gòu)存儲查詢信息，對查詢區(qū)域進行準確定位，以降低查詢的目標范圍，提高查詢效率?？臻g均分法(part half cut method，PHC)的思路為：在歐氏空間的基礎(chǔ)上，將整塊空間均分為B1，B2，B3，B44個區(qū)域，再使用相同方式對每個區(qū)域進行第二次劃分，兩次劃分后將產(chǎn)生42個區(qū)域，第三次劃分后將產(chǎn)生43個區(qū)域，循環(huán)迭代出4n個區(qū)域，直到每個分區(qū)中POI的密度滿足某個給定的值為止，空間均分法示意圖如圖1。

使用空間均分法劃分空間的過程中，空間區(qū)域是以4 的指倍增加，新產(chǎn)生塊的信息可使用4-叉樹結(jié)構(gòu)保存。根節(jié)點指向樹中第0 層節(jié)點，當(dāng)整個空間被第一次切分后會產(chǎn)生B1，B2，B3，B44 個節(jié)點，此為第1 層節(jié)點；第二次切分會得到16 個節(jié)點，依次為B12，B13，B14，…，B41，B42，B43，B44，此為第2 層節(jié)點。通過循環(huán)迭代直到最后分區(qū)中的查詢點數(shù)量滿足區(qū)域分割粒度要求為止，迭代完成后構(gòu)造出4-叉樹結(jié)構(gòu)，如圖2。

圖1 空間均分法示意圖Fig.1 Schematic diagram for part half cut method

圖2 4-叉樹存儲結(jié)構(gòu)示意圖Fig.2 Schematic diagram for quad-tree storage structure

4-叉樹結(jié)構(gòu)的葉子節(jié)點即為最后的分區(qū)塊，通過計算可得每塊的坐標信息，Voronoi 圖中每個POI的數(shù)據(jù)結(jié)構(gòu)中存儲有位置坐標。在構(gòu)建4-叉樹結(jié)構(gòu)過程中，若POI中的點坐標被塊坐標包含，則將該POI存儲到該葉塊的數(shù)據(jù)鏈表中，如表1。這樣就可將查詢范圍直接定位到某區(qū)塊下的數(shù)據(jù)鏈表中，大大縮小查詢范圍，提高查詢效率。

表1 分區(qū)索引表Tab.1 Partitioned index table

3 基于4-叉樹結(jié)構(gòu)的最近鄰查詢算法流程

要查詢q點的最近鄰點，q點即為查詢源點。輸入q點坐標及查詢內(nèi)容，根據(jù)q點坐標找到其所在的葉子節(jié)點，即q點位于的最小分區(qū)塊，通過和葉子節(jié)點中存儲的信息鏈表對比查詢興趣點。若找不到目標，則通過在該葉子節(jié)點相鄰的葉子節(jié)點鏈表中迭代查詢；若相鄰的葉子節(jié)點中仍找不到，則轉(zhuǎn)到其父節(jié)點相鄰節(jié)點的葉子節(jié)點數(shù)據(jù)鏈表中迭代查找。找到的目標節(jié)點即為最近的POI，即最近鄰，其算法流程如圖3。

圖3 最近鄰查詢算法流程圖Fig.3 Algorithm flowchart of the nearest neighbor query

4 實驗結(jié)果及分析

4.1 實驗

對于路網(wǎng)數(shù)據(jù)分區(qū)查詢，傳統(tǒng)的劃分方法有興趣點迭代切分法(iterative division between points method，IBP)和折半分割法(half split method，HM)[12]。其中：IBP是基于POI的密度進行分區(qū)；HM是基于空間中POI 的數(shù)量進行均分。為驗證本文提出的均勻劃分(PHC)最近鄰查詢算法的有效性，文中采用PHC，IBP和HM 3種方法對路網(wǎng)數(shù)據(jù)進行分區(qū)查詢實驗，基于分區(qū)中興趣點數(shù)量對分區(qū)時間和查詢時間的影響，比較分析PHC，IBP和HM 3種方法的分區(qū)性能。

實驗測試設(shè)備為實驗室中的PC 機，操作系統(tǒng)為64 位的WIN10，使用型號為7-4510U 的CPU，主頻為2.6 GHz，內(nèi)存為8 GB。使用Eclipse開發(fā)平臺和Java語言實現(xiàn)最近鄰查詢算法。實驗數(shù)據(jù)取自開源wiki地圖(open street map，OSM)官網(wǎng)的路網(wǎng)數(shù)據(jù)，數(shù)據(jù)大小為16 GB，數(shù)據(jù)格式為XML格式，將其轉(zhuǎn)換為TXT格式的目標文件，目標文件有兩個：block.txt和node.txt，格式數(shù)據(jù)按行存儲。block文件中數(shù)據(jù)結(jié)構(gòu)為{B_id,x1,y1,x2,y2,Bf_id,Bc_id,Bb_id}，其中：B_id為分區(qū)塊的唯一標識；x1，y1，x2，y2為塊坐標；Bf_id為父塊標識；Bc_id為子塊標識；Bb_id為相鄰塊標識。node文件中數(shù)據(jù)結(jié)構(gòu)為{B_id,N_id,x,y,content}，其中：B_id為分區(qū)塊的唯一標識；N_id為當(dāng)前POI的id；x，y為POI坐標；content為POI內(nèi)容。

圖4 分區(qū)時間與POI數(shù)量的關(guān)系Fig.4 Relationship for partition time and number of POI

4.2 實驗結(jié)果與分析

4.2.1 興趣點數(shù)量對分區(qū)時間的影響

為能較好地顯示分區(qū)數(shù)量一定的情況下，POI數(shù)量對分區(qū)時間的影響，選取POI 數(shù)量(|D|)變化區(qū)間為200～2 000 個點，空間均分法(PHC)、基于興趣點迭代切分法(IBP)、折半分割法(HM)3種方法的分區(qū)結(jié)果如圖4。由圖4可看出：POI數(shù)量為1 000時，PHC，HM，IBP的消耗時間分別為0.12，0.18，0.38 s；POI 數(shù)量為1 500 時，PHC，HM，IBP 的消耗時間分別0.35，0.59，1.18 s。由此表明，PHC，HM，IBP 3 種分區(qū)方法的消耗時間隨著興趣點數(shù)量的增加均呈線性分布，其中IBP消耗時間的增長速度比HM更快，PHC消耗時間增長最慢，效果最好。

4.2.2 興趣點數(shù)量對查詢時間的影響

在POI 數(shù)量一定的情況下，PHC，IBP，HM 3 種方法最近鄰查詢時間與分區(qū)數(shù)量的關(guān)系如圖5。由圖5可看出：分區(qū)數(shù)量為400時，PHC，HM，IBP的消耗時間分別為0.42，0.82，0.88 s；分區(qū)數(shù)量為600時，PHC，HM，IBP 的消耗時間分別0.24，0.80 0.86 s。由此表明：在POI 數(shù)量一定的情況下，當(dāng)分區(qū)數(shù)量k增加時，每個分區(qū)中需查詢的POI數(shù)量減少，3種方法的查詢耗時都會降低；但空間均分法(PHC)通過分區(qū)方式產(chǎn)生最佳平衡的分區(qū)元素，效率最高。

圖5 查詢時間與分區(qū)數(shù)量關(guān)系Fig.5 Relationship for query time and number of partitions

5 結(jié) 論

針對路網(wǎng)數(shù)據(jù)中數(shù)據(jù)量較大、查詢效率低等問題，提出利用4-叉樹結(jié)構(gòu)對路網(wǎng)數(shù)據(jù)進行均勻劃分的最近鄰查詢算法。實驗結(jié)果表明，與基于興趣點迭代切分法(IBP)、折半分割法(HM)相比，基于4-叉樹結(jié)構(gòu)的路網(wǎng)數(shù)據(jù)最近鄰查詢算法具有更高的查詢效率，可減少查詢所要訪問的POI數(shù)量，降低查詢開銷。但本實驗查詢對比的內(nèi)容相對簡單，如何基于中文字符進行復(fù)雜內(nèi)容比較是下一步研究的問題。