劉 杰，陳飛輪，楊文奇

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

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

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

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

1.1 VoR-Tree

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

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

圖1 VoR-Tree平面圖

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

1.2 MQM算法

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

MQM算法（Q：查詢點(diǎn)數(shù)據(jù)集，f：?jiǎn)握{(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ù)時(shí)顯得力不從心,因此要對(duì)傳統(tǒng)算法MQM進(jìn)行改造，使其能夠并行化。改造后的MQM采用基于VoR-Tree的VR-kNN算法[5]求出每個(gè)查詢點(diǎn)的最近鄰點(diǎn)，由于VR-kNN算法在空間NN查詢方面效率高且能并行化，因此改造后的MQM算法能夠滿足空間kANN查詢效率方面的要求?；赩oR-Tree的并行kANN查詢算法偽代碼（針對(duì)k= 1的情況）如下：

基于VoR-Tree的并行kANN查詢算法（Q：查詢點(diǎn)數(shù)據(jù)集，f：?jiǎn)握{(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查詢的輸入輸出鍵值對(duì)）：

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

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

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

3 性能測(cè)試與評(píng)估

3.1 實(shí)驗(yàn)環(huán)境

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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