基于MAPREDUCE的空間KANN查詢

劉 杰，陳飛輪，楊文奇

（1.江西理工大學(xué) 建筑與測繪工程學(xué)院，江西 贛州 341000）

空間NN查詢問題是GIS[1]空間分析的重要基礎(chǔ)，其中kANN查詢問題是諸如選址、資源分配、最優(yōu)決策等現(xiàn)實問題的原型。單機(jī)環(huán)境下kANN查詢問題求解的經(jīng)典算法，是先通過DF（depth-first）/BF(best-first)算法對R-Tree進(jìn)行遍歷，求解每個查詢點的NN查詢問題，然后依靠MQM、SPM、MBM算法[2]求解問題，然而當(dāng)面對大規(guī)模海量空間數(shù)據(jù)時，傳統(tǒng)做法將束手無策。開源平臺Hadoop[3]的提出，就是為了解決基于大規(guī)模海量數(shù)據(jù)集的存儲和運算資源不足的情況，特別是基于MapReduce[4]并行編程框架構(gòu)建的應(yīng)用程序。然而，HDFS分布式文件系統(tǒng)的無模式性，要求在存儲空間數(shù)據(jù)時設(shè)計一種索引，以保證較高的查詢效率。目前，針對空間NN查詢問題業(yè)內(nèi)量身而設(shè)計了VoR-Tree索引[5]，該索引能夠保證快速找到給定點的最近鄰和索引至相應(yīng)的磁盤頁面，這又為基于MapReduce并行編程框架構(gòu)建kANN查詢的并行算法提供了依據(jù)。

本文基于MapReduce并行編程框架設(shè)計了一種kANN查詢的并行算法。該算法是在空間數(shù)據(jù)集并行構(gòu)建VoR-Tree索引的基礎(chǔ)上，對傳統(tǒng)單機(jī)環(huán)境下kANN查詢的經(jīng)典算法MQM進(jìn)行并行化改造而設(shè)計出來的。它使得大規(guī)模海量空間數(shù)據(jù)集的kANN查詢移植到Hadoop集群系統(tǒng)上，提高了查詢運算的效率。

1 相關(guān)技術(shù)介紹

1.1 VoR-Tree

VoR-Tree[5]是一種R-tree[6]和Voronoi diagram[7]相融合的一種空間索引。VoR-Tree索引創(chuàng)建的過程為：給定空間數(shù)據(jù)點集P，首先建立點集P的Voronoi diagram，然后構(gòu)建數(shù)據(jù)點集P的R-tree，R-tree的每個葉子節(jié)點存儲了數(shù)據(jù)點集P的一個子集。葉子節(jié)點也包含數(shù)據(jù)點集P子集中的每個數(shù)據(jù)點額外信息的數(shù)據(jù)記錄。在點p的數(shù)據(jù)記錄中，存儲了一個指向p的每個鄰接Voronoi多邊形（VN(p)）磁盤頁面位置的指針和p的Voronoi diagram的每個頂點（V(p)）。

圖1和圖2是VoR-Tree索引的一個示例。圖1中灰色部分顯示了葉子節(jié)點N2的內(nèi)容，它包括了p4、p5、p63個點。在N2中和每個點p相關(guān)的記錄包含了p的鄰接Voronoi多邊形和按一般順序排序的頂點。這個記錄被稱為p的Voronoi記錄。在這個記錄中，點p的每個鄰接Voronoip’實際上是一個指針，該指針指向存儲p’信息（包括它的Voronoi記錄）的磁盤頁面。

圖1 VoR-Tree平面圖

圖2 VoR-Tree結(jié)構(gòu)圖

1.2 MQM算法

MQM算法[2]是單機(jī)環(huán)境下kANN查詢的經(jīng)典算法之一，它利用了BF算法對R-Tree進(jìn)行遍歷,在未滿足終止條件T> best_dist的前提下，依次找出每個查詢點的最近鄰點，比較并求出最小的聚集最近鄰距離best_dist和聚集最近鄰點best_NN，best_NN即為查詢點集Q的聚集最近鄰點。MQM算法偽代碼如下：

MQM算法（Q：查詢點數(shù)據(jù)集，f：單調(diào)函數(shù)）

/* T:global threshold;best_dist: aggregate distance of the current NN */

01.FOR each query point: ti= 0

02.T = 0; best_dist = ∞; best_NN = null //Initialization

03.WHILE (T < best_dist)

04.select the next query point qi

05.get the next nearest neighbor pj of qi//Using incremental BF NN

06.ti= |pjqi|;

07.update T; //T = f(t1，t2，…，tn)

08.compute adist(pj，Q)

09.IF adist(pj，Q) < best_dist

10.best_NN = pj; best_dist = adist(pj，Q); //Update current NN of Q

11.END WHILE

2 基于MapReduce的空間kANN查詢方法

2.1 基于VoR-Tree的并行kANN查詢算法

由于傳統(tǒng)單機(jī)環(huán)境下kANN查詢的經(jīng)典算法MQM在處理大規(guī)模海量空間數(shù)據(jù)時顯得力不從心,因此要對傳統(tǒng)算法MQM進(jìn)行改造，使其能夠并行化。改造后的MQM采用基于VoR-Tree的VR-kNN算法[5]求出每個查詢點的最近鄰點，由于VR-kNN算法在空間NN查詢方面效率高且能并行化，因此改造后的MQM算法能夠滿足空間kANN查詢效率方面的要求?；赩oR-Tree的并行kANN查詢算法偽代碼（針對k= 1的情況）如下：

基于VoR-Tree的并行kANN查詢算法（Q：查詢點數(shù)據(jù)集，f：單調(diào)函數(shù)）

/* T:global threshold; best_dist: aggregate distance of the current NN */

01.FOR each query point: ti= 0

02.T = 0; best_dist = ∞; best_ANN = null //Initialization

03.WHILE (T < best_dist)

04.select the next query point qi

05.get the next nearest neighbor pjof qi//Using 修改算法VR-kNN

06.ti= |pjqi|;

07.update T; //T = f(t1，t2，…，tn)

08.compute adist(pj，Q)

09.IF adist(pj，Q) < best_dist

10.best_ANN = pj; best_dist = adist(pj，Q); //Update current ANN of Q

11.END WHILE

修改算法VR-kNN如下：

01.NN(qi) = VR-1NN(qi); //Using 算法VR-1NN[5]

02.minheap H = {(NN(qi)，D(NN(qi)，qi))};

03.Visited = {NN(qi)}; counter = 1;

04.DO WHILE counter < k + 1

05.remove the first entry p from H;

06.add p into kNN(qi);

07.counter = counter + 1;

08.FOR each Voronoi neighbor of p such as p’ DO

09.IF P’ is not in Visited THEN

10.add (p’，D(p’，qi)) into H and add p’ into Visited;

11.END IF

12.END FOR

13.END WHILE

14.Output kNN(qi);

2.2 基于MapReduce的kANN查詢

利用MapReduce編程模型并行處理空間kANN查詢描述如下（表1給出了MapReduce并行處理kANN查詢的輸入輸出鍵值對）：

Map階段：讀入索引數(shù)據(jù)輸入分片（split），根據(jù)每個輸入分片中的查詢點Qi，把Qi的空間對象標(biāo)識號Qi作為key，Qi位置屬性信息Qi.P作為value，輸入鍵值對，根據(jù)基于VoR-Tree的并行kANN算法，計算出每個輸入分片中best_NN和best_dist，constant_key作為key(best_NN，best_dist)作為value，輸出鍵值對。

Reduce階段：Reduce接收Map的輸出， constant_key作為key，list({(best_ANN，best_dist)})作為value。Reduce通過比較value值中的best_dist大小來確定最小的best_dist所對應(yīng)的key值中的best_ANN。把best_ANN作為key，best_dist作為value，輸出鍵值對。best_ANN即是查詢數(shù)據(jù)集Q的聚集最近鄰點。

表1 MapReduce并行處理kANN查詢的輸入輸出鍵值對

3 性能測試與評估

3.1 實驗環(huán)境

實驗平臺是由10個節(jié)點組成的Hadoop集群，節(jié)點型號為聯(lián)想ThinkCentre 7339AL2，CPU處理器為AMD Athlon雙核，內(nèi)存為2 GB,硬盤為150 GB,操作系統(tǒng)為CentOS 6.3,Hadoop版本為1.0.3，JAVA虛擬機(jī)版本為1.7.0，NameNode和JobTracker同時位于一個節(jié)點，其余節(jié)點作為DataNode/TaskTracker。TaskTracker被配置為可以同時執(zhí)行2個Map任務(wù)和2個Reduce任務(wù)。

本文實驗使用了2種數(shù)據(jù)集，分別是真實的空間數(shù)據(jù)集（RSD）和由一個數(shù)據(jù)生成器隨機(jī)生成的模擬數(shù)據(jù)集（NRSD）。真實數(shù)據(jù)集是從COMAP[8]得到的深圳市交通網(wǎng)絡(luò)中出租車的GPS數(shù)據(jù)， RSD中大約包含180 000 000個空間數(shù)據(jù)點，本實驗從該數(shù)據(jù)集中取出1 300 000個空間數(shù)據(jù)點作為實驗數(shù)據(jù)；模擬數(shù)據(jù)集是數(shù)據(jù)生成器隨機(jī)產(chǎn)生的數(shù)據(jù)， NRSD包含450 000個空間數(shù)據(jù)點。

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

在搭建好的Hadoop集群平臺上，對本文提出的算法進(jìn)行編碼實現(xiàn)，數(shù)據(jù)集用的是NRSD和RSD 2個數(shù)據(jù)集。為了實驗的嚴(yán)謹(jǐn)性，本文的實驗項目分別在這2個數(shù)據(jù)集上進(jìn)行。

3.2.1 節(jié)點數(shù)目對kANN查詢效率的影響

本實驗項目主要是將基于MapReduce 的VoRTree索引（MRVoR-Tree）與基于單機(jī)的VoR-Tree索引（VoR-Tree）進(jìn)行比較和分析。

針對數(shù)據(jù)集NRSD和RSD，通過改變節(jié)點數(shù)目，基于MRVoR-Tree和VoR-Tree的并行空間kANN查詢的執(zhí)行時間分別如圖3和圖4所示。

圖3 NRSD數(shù)據(jù)集執(zhí)行時間

基于MRVoR-Tree的空間kANN查詢，節(jié)點數(shù)目≤8時，隨著節(jié)點數(shù)目的增大，查詢處理效率呈近似線性提高；當(dāng)節(jié)點數(shù)目大于8時，查詢處理效率緩慢提高；當(dāng)節(jié)點數(shù)目等于1時，基于MRVoR-Tree的空間kANN查詢處理效率略高于基于單機(jī)的VoRTree。因此，本文設(shè)計的基于VoR-Tree的并行空間kANN查詢算法在分布式并行計算環(huán)境下具有很高的效率。VoR-Tree索引兼?zhèn)淞薘-tree索引和Voronoi diagram索引的優(yōu)點，在快速索引至查詢點時繼承了R-tree索引的優(yōu)勢，并搜索給定查詢點的最近鄰時不必遍歷R-tree，降低了I/O尋址開銷。

圖4 RSD數(shù)據(jù)集執(zhí)行時間

3.2.2 查詢數(shù)據(jù)集基數(shù)對kANN查詢效率的影響

針對數(shù)據(jù)集NRSD和RSD，通過改變查詢點數(shù)目，基于MRVoR-Tre并行空間kANN查詢的執(zhí)行時間分別如圖5、圖6所示。

圖5 NRSD數(shù)據(jù)集執(zhí)行時間

圖6 RSD數(shù)據(jù)集執(zhí)行時間

隨著查詢點數(shù)目的增加，查詢處理效率呈近似線性遞減。隨著空間數(shù)據(jù)規(guī)模的不斷增長，為了提高查詢處理的效率，只有不斷增加節(jié)點數(shù)目來提高查詢處理的效率。

4 結(jié) 語

本文在空間數(shù)據(jù)集并行構(gòu)建VoR-Tree空間索引的基礎(chǔ)上，首次提出了一種利用MapReduce分布式計算框架在集群環(huán)境中并行處理空間kANN查詢的方法，并詳細(xì)闡述了如何利用MapReduce并行編程模型實現(xiàn)空間kANN查詢算法。該方法充分利用了VoR-Tree空間索引在空間NN查詢上的優(yōu)勢以及Hadoop集群的并行計算和I/O能力，提高了空間kANN查詢的效率。下一步，我們將對kANN查詢當(dāng)k>1的情況以及其他空間查詢類型（RKNN、Knn、skyline等），利用Hadoop的MapReduce編程模型實現(xiàn)其高效處理。

[1]陳述彭，魯學(xué)軍，周成虎.地理信息系統(tǒng)導(dǎo)論[M].北京：科學(xué)出版社，1999

[2]Papadias D,Tao Y,Mouratidis K,et al.Aggregate Nearest Neighbor Queries in Spatial Databases[J].ACM Tods,2005,30(2):529-576

[3]Hadoop.http://hadoop.apache.org.

[4]Dean J, Ghemawat S.MapReduce:Simplified Data Processing on Large Clusters[J].OSDI,2004,137-150

[5]Sharifzadeh M, Shahabi C.VoR Tree: R-trees with Voronoi Diagrams for Efficient Processing of Spatial Nearest Neighbor Queries[J].VLDB,2010,1231-1242

[6]Guttman A.R-Trees: A Dynamic Index Structure for Spatial Searching[C].The 1984 ACM SIGMOD International Conference on Management of data，New York, USA, 1984

[7]Sack J R，Urrutia J.Voronoi Diagrams Handbook on Computational Geometry[J].Elsevier Science, 2000：201-290

[8]COMAP, the Consortium for Mathematics and Its Applications.http://www.comap.com