基于并行kNN的公路地理數據查詢優化方法

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

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

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

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

常規索引往往是通過記錄的存儲地址來確定屬性值，而倒排索引[11]則是根據屬性值來尋找記錄位置。在MapReduce框架[12]下，有些學者提出通過可并行的倒排索引結構處理海量文本數據的方法。基于此，在海量空間數據處理的過程中，也可有效利用數據的空間特性劃分空間區域網格，并通過相應的映射函數處理空間對象坐標屬性值，從而得到空間對象在網格單元中的具體位置。為了進一步管理空間對象和維護其與網格單元的位置關系，本文將空間網格索引與倒排索引相結合，提出了一種新的倒排網格索引；并針對海量公路空間數據，在倒排網格索引的基礎上，重點探討了基于輪圈的kNN算法在處理大規模公路空間數據集方面的應用。

1 基于輪圈的kNN算法

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

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

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

表1 符號定義表

圖1 輪圈算法解析圖

2 改進的可并行kNN算法

基于輪圈的kNN算法是一種串行執行算法，執行過程中需根據每次輪圈訪問的結果確定下一次輪圈的畫圓半徑。本文結合并行計算、分布式存儲等技術，對基于輪圈的kNN算法進行了適當改進，實現了可并行化，從整體上提升了算法查詢性能，使其在大規模空間數據查詢中具有更強的適應性。對基于輪圈的kNN算法的改進思路為：

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

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

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

圖2 改進算法執行實例圖

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

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

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

3.1 實驗數據

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

表2 實驗空間數據集說明

3.2 實驗結果與分析

3.2.1 算法效率對比

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

圖3 不同數據規模算法執行效率

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

3.2.2 網格邊長的設置對算法的影響

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

圖4 海南公路基礎數據庫數據集的算法執行效率

圖5 模擬隨機均勻分布數據集的算法執行效率

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

3.2.3k值設定對算法的影響

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

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

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

4 結 語

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

[1] 李揚,褚春超,陳建營.我國公路交通可持續發展的模式選擇[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] 趙亮,景寧,陳犖等.面向多核多線程的移動對象連續K近鄰查詢[J].軟件學報,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:空間數據庫中組反k最近鄰查詢[J].計算機學報,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].軟件學報,2013,24(8):1 836-1 851

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

[10] 王飛,秦小麟,劉亮,等.基于數據流的k-近鄰連接算法[J].計算機科學,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