基于并行kNN的公路地理數(shù)據(jù)查詢優(yōu)化方法

劉俊杰，劉士寬，上官甦，劉 玲

（1.中交宇科空間信息有限公司，北京 100101；2.中國(guó)公路工程咨詢集團(tuán)有限公司，北京100101）

公路作為交通管理中最重要的地物，也是交管系統(tǒng)數(shù)據(jù)組織的核心[1]。在勘察設(shè)計(jì)、施工設(shè)計(jì)、運(yùn)營(yíng)養(yǎng)護(hù)等各階段公路都將產(chǎn)生大量信息，因此空間數(shù)據(jù)檢索技術(shù)對(duì)公路建設(shè)和公路應(yīng)用系統(tǒng)具有重要支撐作用。如何高效地從海量公路地理空間數(shù)據(jù)中查詢有用信息以指導(dǎo)公路建設(shè)運(yùn)營(yíng)管理成為研究的熱點(diǎn)[2]。

在空間數(shù)據(jù)處理分析中，搜索一定空間范圍內(nèi)距離給定點(diǎn)最近的空間對(duì)象，稱為空間近鄰查詢問(wèn)題[3]。最近鄰的空間對(duì)象可以是一個(gè)或多個(gè)，即空間查詢中經(jīng)典的kNN問(wèn)題。kNN算法是一種理論上較成熟的查詢算法。近年來(lái)，學(xué)者們從提高分類速度、降低算法對(duì)樣本庫(kù)容量的依賴性以及k值選定對(duì)算法的影響等方面入手，提出了許多有效的改進(jìn)方法。PAN J S[4]等提出了快速算法（KWENNS）；Cheema M A[5]等提出了一種基于CircularTrip的kNN算法；宋曉宇[6]等提出了針對(duì)空間數(shù)據(jù)庫(kù)的組反k最近鄰概念，設(shè)計(jì)了基于R樹的剪枝方法，通過(guò)提煉獲取最終的GRkNN結(jié)果；Kim Y[7]等研究了通過(guò)MapReduce框架對(duì)top-k相似性算法進(jìn)行改進(jìn)的方法，實(shí)現(xiàn)了divide-and-conquer和 branch-and-bound算法，提出了all pair partitioning和 essential pair partitioning方法，用于最小化map和reduce函數(shù)之間的數(shù)據(jù)傳送量；劉義[8]等在索引構(gòu)建過(guò)程中，提出了一種采樣算法，可快速確立空間劃分函數(shù)，再利用R樹索引進(jìn)行k近鄰連接查詢，提高了查詢效率；杜欽生[9]使用Hilbert曲線將多維空間中的點(diǎn)映射到一維空間，并通過(guò)塊嵌套循環(huán)的方法解決了k近鄰的連接；王飛[10]等提出了一種基于數(shù)據(jù)流的計(jì)算框架，利用空間填充曲線將多維數(shù)據(jù)映射為一維數(shù)據(jù)，從而將k近鄰連接查詢轉(zhuǎn)化為一維范圍查詢。

常規(guī)索引往往是通過(guò)記錄的存儲(chǔ)地址來(lái)確定屬性值，而倒排索引[11]則是根據(jù)屬性值來(lái)尋找記錄位置。在MapReduce框架[12]下，有些學(xué)者提出通過(guò)可并行的倒排索引結(jié)構(gòu)處理海量文本數(shù)據(jù)的方法?；诖耍诤Ａ靠臻g數(shù)據(jù)處理的過(guò)程中，也可有效利用數(shù)據(jù)的空間特性劃分空間區(qū)域網(wǎng)格，并通過(guò)相應(yīng)的映射函數(shù)處理空間對(duì)象坐標(biāo)屬性值，從而得到空間對(duì)象在網(wǎng)格單元中的具體位置。為了進(jìn)一步管理空間對(duì)象和維護(hù)其與網(wǎng)格單元的位置關(guān)系，本文將空間網(wǎng)格索引與倒排索引相結(jié)合，提出了一種新的倒排網(wǎng)格索引；并針對(duì)海量公路空間數(shù)據(jù)，在倒排網(wǎng)格索引的基礎(chǔ)上，重點(diǎn)探討了基于輪圈的kNN算法在處理大規(guī)模公路空間數(shù)據(jù)集方面的應(yīng)用。

1 基于輪圈的kNN算法

基于空間k最近鄰查詢方法，本文通過(guò)兩個(gè)步驟來(lái)實(shí)現(xiàn)可并行的kNN算法：①初步查找，根據(jù)給定的查詢點(diǎn)由近及遠(yuǎn)訪問(wèn)空間網(wǎng)格；②精細(xì)查找，通過(guò)網(wǎng)格索引查詢距離給定點(diǎn)最近的k個(gè)空間對(duì)象。為了方便說(shuō)明，本文均針對(duì)二維空間的點(diǎn)狀數(shù)據(jù)?？臻gkNN查詢的形式化定義為：

設(shè)P為二維空間的一個(gè)數(shù)據(jù)點(diǎn)集合，q為給定查詢點(diǎn)，k為正整數(shù)，那么kNN查詢就是在范圍空間中找尋一個(gè)包含k個(gè)數(shù)據(jù)點(diǎn)的集合kNN，且滿足任意點(diǎn)p'∈kNN 和任意點(diǎn)p∈p-kNN，始終有d(p',q)≤d(p,q)。符號(hào)表示含義如表1所示。

輪圈算法是一種非常有效的訪問(wèn)空間網(wǎng)格的算法，其返回的結(jié)果是經(jīng)過(guò)一次輪圈后與圓弧相交的所有網(wǎng)格單元。如圖1所示，執(zhí)行一次輪圈算法會(huì)依次遍歷圖中所有陰影表示的網(wǎng)格，并將其加載到一個(gè)堆棧H中；再遍歷堆棧中的網(wǎng)格單元CH，找到與查詢點(diǎn)q最近鄰的k個(gè)空間點(diǎn)。圖1中C_start為起始網(wǎng)格，C為當(dāng)前訪問(wèn)網(wǎng)格，C_u和C_r為當(dāng)前訪問(wèn)網(wǎng)格的鄰居，需通過(guò)計(jì)算距離并與當(dāng)前畫圓半徑r進(jìn)行比較來(lái)確定下一個(gè)將要訪問(wèn)的網(wǎng)格，如通過(guò)計(jì)算得到mind(C_u,q)

表1 符號(hào)定義表

圖1 輪圈算法解析圖

2 改進(jìn)的可并行kNN算法

基于輪圈的kNN算法是一種串行執(zhí)行算法，執(zhí)行過(guò)程中需根據(jù)每次輪圈訪問(wèn)的結(jié)果確定下一次輪圈的畫圓半徑。本文結(jié)合并行計(jì)算、分布式存儲(chǔ)等技術(shù)，對(duì)基于輪圈的kNN算法進(jìn)行了適當(dāng)改進(jìn)，實(shí)現(xiàn)了可并行化，從整體上提升了算法查詢性能，使其在大規(guī)?？臻g數(shù)據(jù)查詢中具有更強(qiáng)的適應(yīng)性。對(duì)基于輪圈的kNN算法的改進(jìn)思路為：

1）采用倒排網(wǎng)格索引。網(wǎng)格索引的建立過(guò)程與空間kNN查詢過(guò)程是相對(duì)獨(dú)立的，且倒排網(wǎng)格索引本身具有可并行性，索引建立一次，可完成多次查詢。

2）原有算法中輪圈半徑r的初始化為r0

3）原有算法終止條件為mind(c,q)≥q.dk，即要找到第k個(gè)最近鄰，且q點(diǎn)到第k個(gè)最近鄰的距離不大于q點(diǎn)當(dāng)前要訪問(wèn)網(wǎng)格的最小距離，算法結(jié)束。本文改進(jìn)算法的終止條件為并行輪圈訪問(wèn)網(wǎng)格所收集的對(duì)象點(diǎn)之和|P|不小于k，并再進(jìn)行一次輪圈訪問(wèn)，收集網(wǎng)格內(nèi)的對(duì)象點(diǎn)到集合P中。

圖2 改進(jìn)算法執(zhí)行實(shí)例圖

改進(jìn)算法的具體執(zhí)行過(guò)程如圖2所示。假設(shè)算法可并行的最大線程數(shù)為2，則q點(diǎn)的兩個(gè)最近鄰，k=2。如圖2a所示，第一次有兩個(gè)輪圈并行執(zhí)行，在半徑為r0和r0+a的輪圈訪問(wèn)中分別收集到p1和p2，此時(shí)集合P={ p1,p2}，滿足|P|≥k=2，根據(jù)改進(jìn)算法的終止條件，需再進(jìn)行一次輪圈；如圖2b所示，在半徑為r0+2a的輪圈訪問(wèn)中又收集到p4，加入到集合P中后P={ p1,p2,p4}，再通過(guò)距離計(jì)算最終確定q點(diǎn)的兩個(gè)最近鄰（2NN）為{ p1,p4}，查詢結(jié)束。

3 可并行kNN算法的驗(yàn)證與分析

在公路實(shí)際建設(shè)過(guò)程中，往往會(huì)涉及許多空間查詢問(wèn)題，這些問(wèn)題均與空間最近鄰查詢相關(guān)。通過(guò)真實(shí)和模擬數(shù)據(jù)，本文從效率、網(wǎng)格邊長(zhǎng)、k值3個(gè)方面對(duì)可并行kNN算法進(jìn)行驗(yàn)證。

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

實(shí)驗(yàn)數(shù)據(jù)集包括真實(shí)數(shù)據(jù)和模擬數(shù)據(jù)兩種：真實(shí)數(shù)據(jù)為海南公路基礎(chǔ)數(shù)據(jù)庫(kù)中描述公路空間實(shí)體地理位置的公路控制點(diǎn)，模擬數(shù)據(jù)為通過(guò)數(shù)據(jù)生成器在橫、縱坐標(biāo)為0～1 000的范圍內(nèi)隨機(jī)均勻產(chǎn)生的空間對(duì)象點(diǎn)（表2）。

表2 實(shí)驗(yàn)空間數(shù)據(jù)集說(shuō)明

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

3.2.1 算法效率對(duì)比

可并行kNN算法采用網(wǎng)格邊長(zhǎng)逐步遞增的方式選擇輪圈半徑，并不依賴于上次輪圈訪問(wèn)的結(jié)果，且結(jié)合多線程并行技術(shù)，每次可實(shí)現(xiàn)多個(gè)輪圈的并行訪問(wèn)。圖3反映的是在不同數(shù)據(jù)規(guī)模下，原有算法與改進(jìn)算法的空間數(shù)據(jù)查詢效率對(duì)比結(jié)果。

圖3 不同數(shù)據(jù)規(guī)模算法執(zhí)行效率

實(shí)驗(yàn)中設(shè)置網(wǎng)格邊長(zhǎng)為1，k=4，可并行kNN算法設(shè)置的最大并行執(zhí)行線程數(shù)為2。從圖3中曲線的變化趨勢(shì)來(lái)看，當(dāng)數(shù)據(jù)集規(guī)模不斷增大時(shí)，兩種算法查詢空間4個(gè)最近鄰點(diǎn)的響應(yīng)時(shí)間都在增加；當(dāng)數(shù)據(jù)集規(guī)模相同時(shí)，改進(jìn)算法的查詢時(shí)間明顯比原有算法短。從圖3中曲線的走向來(lái)看，隨著數(shù)據(jù)集規(guī)模的增大，改進(jìn)算法的查詢時(shí)間增長(zhǎng)速度變慢，查詢效率變得穩(wěn)定，所以改進(jìn)算法更能適應(yīng)較大規(guī)?？臻g數(shù)據(jù)的查詢。

3.2.2 網(wǎng)格邊長(zhǎng)的設(shè)置對(duì)算法的影響

由于公路地理數(shù)據(jù)的空間線性分布性，在建立倒排網(wǎng)格索引時(shí)，網(wǎng)格邊長(zhǎng)的設(shè)置將影響網(wǎng)格內(nèi)空間對(duì)象點(diǎn)的密度。對(duì)于同一個(gè)空間分布，當(dāng)網(wǎng)格邊長(zhǎng)設(shè)置為較大值時(shí)，網(wǎng)格內(nèi)空間對(duì)象點(diǎn)的平均密度就較大，單個(gè)輪圈執(zhí)行時(shí)間較長(zhǎng)；當(dāng)網(wǎng)格邊長(zhǎng)設(shè)置為較小值時(shí)，輪圈次數(shù)可能隨之增加，同時(shí)創(chuàng)建網(wǎng)格索引的代價(jià)也可能相應(yīng)增大。在兩個(gè)數(shù)據(jù)集上的算法執(zhí)行效率如圖4、5所示。

圖4 海南公路基礎(chǔ)數(shù)據(jù)庫(kù)數(shù)據(jù)集的算法執(zhí)行效率

圖5 模擬隨機(jī)均勻分布數(shù)據(jù)集的算法執(zhí)行效率

實(shí)驗(yàn)中數(shù)據(jù)集規(guī)模為100 M，當(dāng)k=4時(shí)，同等情況下改進(jìn)算法的效率比原有算法高。由圖4可知，當(dāng)網(wǎng)格邊長(zhǎng)為0.01時(shí)，算法的執(zhí)行效率最高，這是因?yàn)樵摂?shù)據(jù)集具有公路空間分布特性，數(shù)據(jù)經(jīng)緯度坐標(biāo)分布在18～110之間，此時(shí)網(wǎng)格中數(shù)據(jù)點(diǎn)分布適中，從而算法執(zhí)行效率最高；而對(duì)于模擬隨機(jī)均勻分布數(shù)據(jù)集，數(shù)據(jù)點(diǎn)分布沒(méi)有規(guī)律，只要保證網(wǎng)格中數(shù)據(jù)點(diǎn)的密度適中，算法就會(huì)有較高的執(zhí)行效率。因此，網(wǎng)格邊長(zhǎng)的設(shè)定對(duì)算法的執(zhí)行效率會(huì)產(chǎn)生較大影響，在實(shí)際運(yùn)用中要根據(jù)空間對(duì)象的具體分布來(lái)設(shè)定網(wǎng)格邊長(zhǎng)，一方面有利于提高算法效率，另一方面可節(jié)約網(wǎng)格索引的存儲(chǔ)空間。

3.2.3k值設(shè)定對(duì)算法的影響

公路空間數(shù)據(jù)的查詢往往涉及多個(gè)空間對(duì)象，即對(duì)于給定的q點(diǎn)，要找到與其最近鄰的多個(gè)空間對(duì)象點(diǎn)，這就需要設(shè)置算法的相關(guān)參數(shù)k。圖6為當(dāng)k取不同值時(shí)，兩種算法查詢執(zhí)行效率的變化情況。

圖6 不同k值時(shí)兩種算法的效率對(duì)比

圖6中設(shè)定的網(wǎng)格單元邊長(zhǎng)為1，當(dāng)k取不同值時(shí)，改進(jìn)算法的查詢效率均比原有算法高。隨著k值的增大，改進(jìn)算法的查詢時(shí)間增長(zhǎng)較為緩慢，查詢效率相對(duì)穩(wěn)定；而原有算法的查詢時(shí)間增長(zhǎng)較快，查詢效率降低。當(dāng)k值增大時(shí)，需要查詢的最近鄰點(diǎn)增多，輪圈訪問(wèn)網(wǎng)格的次數(shù)相應(yīng)增加，由于原有算法中輪圈半徑的更新需依賴于上次的訪問(wèn)結(jié)果，只能一圈一圈地進(jìn)行遍歷，效率較低；而改進(jìn)算法可實(shí)現(xiàn)多線程并行輪圈，每次可同時(shí)進(jìn)行多圈遍歷，從而表現(xiàn)出更高的效率。由此可見(jiàn)，改進(jìn)算法更能適應(yīng)查詢多個(gè)空間對(duì)象點(diǎn)的情況。

4 結(jié) 語(yǔ)

本文針對(duì)公路地理數(shù)據(jù)分布特點(diǎn)提出了一種倒排網(wǎng)格空間索引，通過(guò)空間位置坐標(biāo)將空間對(duì)象映射到網(wǎng)格索引中，具有更好的可并行性，且結(jié)構(gòu)簡(jiǎn)單，實(shí)現(xiàn)與維護(hù)相對(duì)比較容易?；诖耍疚膶?duì)串行輪圈kNN算法做了深入分析，以網(wǎng)格邊長(zhǎng)遞增的方式對(duì)輪圈半徑進(jìn)行更新，打破了輪圈半徑依賴上輪訪問(wèn)結(jié)果的局限，并結(jié)合多線程技術(shù)提出了可并行kNN算法，有效提高了算法的查詢效率。本文從數(shù)據(jù)集規(guī)模、網(wǎng)格邊長(zhǎng)、k值選取3個(gè)方面對(duì)比分析了兩種算法的效率，驗(yàn)證了改進(jìn)算法的高效性以及在處理大規(guī)?？臻g數(shù)據(jù)集方面的實(shí)用性。

[1] 李揚(yáng),褚春超,陳建營(yíng).我國(guó)公路交通可持續(xù)發(fā)展的模式選擇[J].公路交通科技,2012,29(12):144-147

[2] Lee K C K, Lee W C, ZHENG B H, 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

[3] 趙亮,景寧,陳犖等.面向多核多線程的移動(dòng)對(duì)象連續(xù)K近鄰查詢[J].軟件學(xué)報(bào),2011,22(8):1 805-1 815

[4] PAN J S, QIAO Y L, SUN S H. A Fast k Nearest Neighbors Classification Algorithm[J]. Ieice Transactions on Fundamentals of Electronics Communications and Computer,2004,E87A(4):961-963[5] Cheema M A, YUAN Y D, LIN X M. Circulartrip: an Effective Algorithm for Continuous kNN Queries[M]. Advances in Databases: Concepts, Systems and Applications, Springer Berlin Heidelberg,2007:863-869

[6] 宋曉宇,于程程,孫煥良,等.GRkNN:空間數(shù)據(jù)庫(kù)中組反k最近鄰查詢[J].計(jì)算機(jī)學(xué)報(bào),2010,33(12):2 229-2 238

[7] Kim Y, Shim K. Parallel Top-K Similarity Join Algorithms Using MapReduce[J]. IEEE International Conference on Data Engineering,2012,41(4):510-521

[8] 劉義,景寧,陳犖,等. MapReduce框架下基于R-樹的k-近鄰連接算法[J].軟件學(xué)報(bào),2013,24(8):1 836-1 851

[9] 杜欽生.高維空間的k最近鄰查詢及連接問(wèn)題研究[D].長(zhǎng)春:吉林大學(xué),2015

[10] 王飛,秦小麟,劉亮,等.基于數(shù)據(jù)流的k-近鄰連接算法[J].計(jì)算機(jī)科學(xué),2015,42(5):204-210

[11] Yan H, Ding S, Suel T. Inverted Index Compression and Query Processing with Optimized Document Ordering[C].Proceedings of the18th International Conference on World Wide Web,2009,4(4):401-410

[12] Cordeiro R L F, Traina A J M, Kang U, et al. Clustering Very Large Multi-dimensional Datasets with MapReduce[C]. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,2011:690-698