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

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

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

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

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

1 基于輪圈的kNN算法

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

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

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

表1 符號定義表

圖1 輪圈算法解析圖

2 改進的可并行kNN算法

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

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

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

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

圖2 改進算法執(zhí)行實例圖

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

3 可并行kNN算法的驗證與分析

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

3.1 實驗數(shù)據(jù)

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

表2 實驗空間數(shù)據(jù)集說明

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

3.2.1 算法效率對比

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

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

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

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

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

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

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

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

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

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

圖6 不同k值時兩種算法的效率對比

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

4 結(jié) 語

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

[1] 李揚,褚春超,陳建營.我國公路交通可持續(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] 趙亮,景寧,陳犖等.面向多核多線程的移動對象連續(xù)K近鄰查詢[J].軟件學(xué)報,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最近鄰查詢[J].計算機學(xué)報,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é)報,2013,24(8):1 836-1 851

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

[10] 王飛,秦小麟,劉亮,等.基于數(shù)據(jù)流的k-近鄰連接算法[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