基于Spark的并行反向k最近鄰查詢

楊澤雪，張 毅，李 陸，劉偉東，蔣 超

(1.東北林業(yè)大學(xué) 信息與計(jì)算機(jī)工程學(xué)院，黑龍江 哈爾濱 150040；2.黑龍江省政務(wù)大數(shù)據(jù)中心 合作交流與創(chuàng)新發(fā)展處，黑龍江 哈爾濱 150028；3.黑龍江工程學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)系，黑龍江 哈爾濱 150050)

0 引 言

隨著數(shù)據(jù)量的爆炸式增長，研究分布式環(huán)境下的并行反向k最近鄰(reverseknearest neighbor，RkNN)查詢[1]受到研究人員的關(guān)注。

目前流行的并行處理框架主要包括MapReduce和Spark。而當(dāng)前的并行RkNN查詢算法大多數(shù)都是基于Map-Reduce[2-5]框架。文獻(xiàn)[6]介紹了基于倒排網(wǎng)格索引(inver-ted grid index)的分布式RkNN查詢處理方法。文獻(xiàn)[7]在Hadoop的空間擴(kuò)展框架SpatialHadoop上進(jìn)行了分布式RkNN查詢研究，給出了基于SpatialHadoop的RkNN查詢算法，并在真實(shí)數(shù)據(jù)集上實(shí)現(xiàn)了該算法。文獻(xiàn)[8]提出了基于SpatialHadoop的RkNN查詢MRSLICE算法?；赟park框架的分布式空間查詢研究，近年來國內(nèi)外學(xué)者提出了GeoSpark[9]、SpatialSpark[10]、LocationSpark[11]等框架，這些框架可實(shí)現(xiàn)基于Spark的分布式空間范圍查詢、kNN查詢和空間連接查詢，并且通過實(shí)驗(yàn)驗(yàn)證基于Spark框架的查詢處理優(yōu)于MapReduce框架。除以上典型空間查詢之外，學(xué)者們擴(kuò)展了基于Spark框架的變體查詢研究，包括距離連接查詢[12,13]、時(shí)空連接查詢[14,15]、top-k空間連接查詢[16]、軌跡k近鄰查詢[17]、空間范圍查詢[18]、k近鄰連接查詢[19]、組k近鄰查詢[20]等。

以上研究均展示了Spark框架處理并行空間查詢的優(yōu)越性。但是，基于Spark框架的RkNN查詢研究較少，文獻(xiàn)[7]提出了基于LocationSpark的并行RkNN查詢算法，并將該算法與基于SpatialHadoop的RkNN查詢算法進(jìn)行了比較，結(jié)果顯示基于LocationSpark的并行RkNN算法明顯優(yōu)于SpatialHadoop。為此本文基于Spark框架研究并行RkNN查詢，基于Voronoi圖在空間鄰近性方面的優(yōu)良特性，在Spark框架上擴(kuò)展基于Voronoi圖的并行索引結(jié)構(gòu)Grid-Voronoi-Index，在該索引結(jié)構(gòu)上給出基于Spark的RkNN查詢處理算法SV_RkNN，進(jìn)一步提高并行RkNN的查詢效率。

1 相關(guān)定義

定義3[2]Voronoi圖：給定一個(gè)點(diǎn)集P={p1,…,pn}， 其中2

定義4[2]k級(jí)鄰接生成點(diǎn)：給定一組生成點(diǎn)P={p1,…,pn} 生成的Voronoi圖中，其中2

AGk(pi)={pj|VP(p) 與VP(pj) 有公共邊，p∈AGk-1(pi)}

定理1[21]給定數(shù)據(jù)集P的Voronoi圖VD(P)和查詢點(diǎn)q，其中q∈P， 查詢點(diǎn)q的R1NN在其1級(jí)鄰接生成點(diǎn)中。

推論1 給定數(shù)據(jù)集P的Voronoi圖VD(P)和查詢點(diǎn)q，其中q∈P，查詢點(diǎn)q的RkNN在其前k級(jí)鄰接生成點(diǎn)中。

定理2[22]給定數(shù)據(jù)集P和查詢點(diǎn)q，在點(diǎn)q處將空間區(qū)域6等分(每個(gè)部分60°)，則每個(gè)區(qū)域中查詢點(diǎn)q的RkNN只能在其k近鄰中。

2 基于Spark的索引構(gòu)建

2.1 基于Spark的索引構(gòu)建過程

為了完成并行反向k最近鄰查詢，構(gòu)建雙層索引結(jié)構(gòu)，即全局索引和局部索引，全局索引采取網(wǎng)格索引，存放在master節(jié)點(diǎn)中，全局索引通過網(wǎng)格的劃分將數(shù)據(jù)切分成各個(gè)數(shù)據(jù)塊，然后在各個(gè)數(shù)據(jù)塊上建立局部索引，局部索引采用Voronoi圖索引結(jié)構(gòu)，存儲(chǔ)在各個(gè)worker結(jié)點(diǎn)中。基于Spark的網(wǎng)格-Voronoi圖雙層索引構(gòu)建過程如圖1所示。

圖1 基于Spark的網(wǎng)格-Voronoi圖雙層索引結(jié)構(gòu)

2.2 基于Spark的雙層索引構(gòu)建算法

給定大規(guī)模數(shù)據(jù)集dataset，讀取數(shù)據(jù)文件生成dataRDD并分配到各個(gè)分區(qū)中，此時(shí)的數(shù)據(jù)分區(qū)并沒有考慮到空間數(shù)據(jù)的鄰近性，而分區(qū)的數(shù)據(jù)關(guān)系直接影響到后續(xù)查詢的性能。為此，將dataRDD重新分區(qū)，以保證數(shù)據(jù)的鄰近關(guān)系。為此建立雙層索引結(jié)構(gòu)，首先對(duì)于dataRDD每個(gè)分區(qū)的數(shù)據(jù)進(jìn)行采樣，這里選取1%的數(shù)據(jù)，將這些數(shù)據(jù)傳送到主結(jié)點(diǎn)生成網(wǎng)格索引GridIndex，然后利用網(wǎng)格索引將每個(gè)分區(qū)中的數(shù)據(jù)分配到對(duì)應(yīng)的網(wǎng)格中，對(duì)于每個(gè)分區(qū)中的數(shù)據(jù)點(diǎn)，如果該數(shù)據(jù)點(diǎn)包含在某個(gè)網(wǎng)格中，就將其分到該網(wǎng)格中，分配結(jié)果生成新的網(wǎng)格分區(qū)RDD即GridPartitionRdd，然后將GridPartitionRdd中具有相同grid_id的數(shù)據(jù)重新分配到新的分區(qū)中，也就是進(jìn)行再分區(qū)，對(duì)于每一個(gè)新的分區(qū)中的對(duì)象，分別建立Voronoi索引，形成VoronoiIndexRdd。

基于Spark的網(wǎng)格-Voronoi 圖雙層索引構(gòu)建算法如算法1所示。

算法1：Grid-Voronoi-Index-Construct

輸入：數(shù)據(jù)集dataset;

輸出：局部Voronoi圖索引，全局網(wǎng)格索引;

begin

sc←new SparkContext(conf);

dataRDD←sc.textfile(dataset);

//加載原始數(shù)據(jù)

SampleData←dataRDD.sample;//對(duì)原始數(shù)據(jù)進(jìn)行并行采樣

GridIndex←SampleData.CreateGridIndex;

//基于采樣數(shù)據(jù)，在master結(jié)點(diǎn)構(gòu)建網(wǎng)格索引

for each partition do

for each point in dataRDD do

for each grid do

If point∈grid then

GridPartitionRdd←

GridPartitionRdd∪(grid_id,point);

//將dataRDD中的點(diǎn)分配到對(duì)應(yīng)網(wǎng)格中

endif

endfor

endfor

endfor

rePartitionRdd←GridPartitionRdd.partitionBy

(GridPartitionRdd(grid_id,point)

?rePartitionRdd(grid_id,point)

//將具有相同grid_id的數(shù)據(jù)混洗到同一個(gè)分區(qū)中

for each partition do

VoronoiIndexRdd←rePartitionRdd.map

(rePartitionRdd(grid_id,point)?

VoronoiIndexRdd(grid_id,PVDi));

endfor

VoronoiIndexRdd.merge();

VoronoiIndexRdd.cache();

GridIndex.cache();

return GridIndexRdd;

return VoronoiIndexRdd;

end

3 基于Spark的并行反向k最近鄰查詢

3.1 基于Spark的并行反向k最近鄰查詢過程

基于Spark的并行反向k最近鄰查詢處理過程如圖2所示。

圖2 基于Spark并行空間反向k最近鄰查詢處理流程

該查詢方法首先載入數(shù)據(jù)集的全局網(wǎng)格索引，通過網(wǎng)格索引的檢索，查找出包含查詢點(diǎn)q的局部Voronoi圖索引，加載局部Voronoi圖索引，并啟動(dòng)任務(wù)開始執(zhí)行。然后在每個(gè)分區(qū)中執(zhí)行在基于Voronoi圖的RkNN過濾-精煉算法，找到查詢點(diǎn)q的RkNN，形成結(jié)果存儲(chǔ)在HDFS中。

3.2 基于Voronoi圖的RkNN過濾-精煉算法

給定數(shù)據(jù)集P的Voronoi圖VD(P)和查詢點(diǎn)q，基于Voronoi圖的RkNN過濾-精煉算法包含過濾和精煉兩個(gè)步驟。首先，由過濾步驟獲得可能成為結(jié)果的候選，在Voronoi圖VD(P)中定位查詢點(diǎn)q，在q處將空間劃分為6等分區(qū)域，由推論1可知，查詢點(diǎn)q的RkNN一定在其前k級(jí)鄰接生成點(diǎn)中，再由定理2可知，每個(gè)6等分區(qū)域的RkNN結(jié)果只能在其k近鄰中，因此對(duì)于每個(gè)區(qū)域，將q的前k級(jí)鄰接生成點(diǎn)放入候選集中；然后，由精煉步驟去除候選集中不能成為結(jié)果的候選，計(jì)算候選集中每個(gè)點(diǎn)p的第k個(gè)最近鄰k-thNN，如果p與k-thNN之間的距離小于p與q之間的距離，則從候選集中刪掉p，最后將6個(gè)區(qū)域的候選集合并即為最終結(jié)果。

基于Voronoi圖的RkNN過濾、精煉算法如算法2、算法3所示。

算法2： VRkNN-Filter(P,q,k)

輸入： 查詢點(diǎn)q， 數(shù)據(jù)點(diǎn)集P的Voronoi圖VD(P)， RkNN的k值;

輸出： RkNN的候選集Scnd(i);

begin

fori=1 to 6 do

Scnd(i)←?；

endfor

在VD(P)中定位查詢點(diǎn)q;

SixRegionPartition(P)；

for eachScnd(i) do

for i=1 tokdo

Scnd(i)←Scnd(i)+AGi(q)；

//將q的第i級(jí)鄰接生成點(diǎn)加入候選集中

endfor

returnScnd(i)；

end

算法3： VRkNN-Verification(P,q,k)

輸入： 查詢點(diǎn)q， 數(shù)據(jù)點(diǎn)集Voronoi圖VD(P)， RkNN的k值;

輸出： RkNN結(jié)果集result;

begin

Scnd(i)←VRkNN-Filter(P,q,k)；

Scnd←?；

result←?；

for each pointpinScnd(i) do

pk=k-th NN ofp；

if dist(p,q)>dist(p,pk) then

Scnd(i)←Scnd(i)-p；

endif

endfor

Scnd←Scnd∪Scnd(i)；

result←Scnd；

returnresult；

end

定理3 算法VRkNN-Filter(P,q,k) 和VRkNN-Verification(P,q,k) 可以正確地查找查詢點(diǎn)q的反向k最近鄰，算法VRkNN-Filter(P,q,k) 和VRkNN-Verification(P,q,k) 是可以終止的，算法的時(shí)間復(fù)雜度是O(nlogn)。

證明：(正確性)算法VRkNN-Filter(P,q,k) 首先將空間區(qū)域以查詢點(diǎn)q為中心進(jìn)行6等分，然后在每個(gè)區(qū)域中查找q的k個(gè)最近鄰，將這些結(jié)果放入候選集中，由推論1和定理2可知，算法VRkNN-Filter(P,q,k) 中的結(jié)果是正確的。算法VRkNN-Verification(P,q,k) 對(duì)候選集中的每個(gè)數(shù)據(jù)點(diǎn)進(jìn)行處理，用該點(diǎn)的第k個(gè)最近鄰與之對(duì)比，如果滿足該點(diǎn)與查詢點(diǎn)的距離大于該點(diǎn)與其第k個(gè)最近鄰的距離，則去掉該候選，逐個(gè)去除錯(cuò)誤的候選，得到正確的結(jié)果。

(可終止性)算法VRkNN-Filter(P,q,k) 對(duì)6個(gè)空間區(qū)域分別進(jìn)行for循環(huán)，循環(huán)次數(shù)為k，是有限的，為此算法2是可終止的，算法VRkNN-Verification(P,q,k) 中的for循環(huán)是針對(duì)候選集中的對(duì)象的，數(shù)據(jù)也是有限的，所以循環(huán)是可以終止的，為此算法3也是可終止的。

(時(shí)間復(fù)雜度分析)算法VRkNN-Filter(P,q,k) 計(jì)算Voronoi圖的時(shí)間復(fù)雜度為O(nlogn)，在VD(P)中定位查詢點(diǎn)q時(shí)間是O(logn)，查找k個(gè)最近鄰時(shí)間為O(klogn)， 為此算法2的時(shí)間復(fù)雜度為O(nlogn+klogn)； 算法VRkNN-Verification(P,q,k) 針對(duì)候選集中對(duì)象進(jìn)行查詢，假設(shè)候選集中對(duì)象個(gè)數(shù)為m，則查詢時(shí)間為O(mlogn)，為此算法3的時(shí)間復(fù)雜度為O(mlogn)，綜上，基于Voronoi圖的RkNN過濾-精煉算法總的時(shí)間復(fù)雜度為O(nlogn+klogn+mlogn)。 證畢。

3.3 基于Spark并行反向k最近鄰查詢算法

基于Spark的并行反向k最近鄰查詢算法SV_RkNN基本思想如下：算法包括兩個(gè)步驟，第一個(gè)步驟為過濾，第二個(gè)步驟為精煉。給定雙層索引結(jié)構(gòu)的RDD，算法首先查詢?nèi)志W(wǎng)格索引，定位查詢點(diǎn)q所在網(wǎng)格，確定對(duì)應(yīng)局部索引，在局部索引RDD所在分區(qū)執(zhí)行過濾精煉步驟。過濾步驟執(zhí)行VRkNN-Filter過濾算法，執(zhí)行過程中如果出現(xiàn)候選集中的點(diǎn)在相鄰的其它分區(qū)時(shí)，如圖1的點(diǎn)p1的某些最近鄰p2、p3在其相鄰的分區(qū)中，需要對(duì)相應(yīng)分區(qū)進(jìn)行并行處理，再次執(zhí)行VRkNN-Filter過濾算法，并將候選集進(jìn)行合并，得到最終候選集；然后在候選集所在分區(qū)中執(zhí)行VRkNN-Verification精煉算法，得到最終的并行反向k最近鄰查詢結(jié)果。算法SV_RkNN的數(shù)據(jù)流如圖3所示。

圖3 SV_RkNN的數(shù)據(jù)流

由圖3可知，SV_RkNN查詢處理算法包括Filter、Flatmap、Merge、Flatmap這4次轉(zhuǎn)換，其中Filter轉(zhuǎn)換可由全局網(wǎng)格索引定位查詢點(diǎn)縮小查詢范圍，從而縮小中間生成的RDD大小，接下來的Flatmap轉(zhuǎn)換完成過濾操作，產(chǎn)生窄依賴，而Merge轉(zhuǎn)換完成再次過濾操作，產(chǎn)生寬依賴，會(huì)發(fā)生數(shù)據(jù)的混洗，但此時(shí)數(shù)據(jù)經(jīng)過過濾已經(jīng)極大縮小當(dāng)前的RDD，最后的Flatmap轉(zhuǎn)換完成精煉操作。此過程產(chǎn)生的中間RDD會(huì)在每次執(zhí)行后刪除，但索引RDD仍駐留在內(nèi)存中，重復(fù)使用的索引RDD可大幅度加速迭代的執(zhí)行。

基于Spark并行反向k最近鄰查詢算法如算法4所示。

算法4： SV_RkNN

輸入： 網(wǎng)格索引GridIndex， Voronoi圖索引VoronoiIndexRdd， 查詢點(diǎn)集q， RkNN的k值;

輸出： 查詢集q的RkNN結(jié)果集合result;

begin

Grid_idArray←GridIndexQuery(q);

//查詢網(wǎng)格索引，確定查詢點(diǎn)q所在網(wǎng)格，將對(duì)應(yīng)grid_id記錄在Grid_idArray中

VoronoiIndexRdd←

VoronoiIndexRdd.Filter(grid_id);

//根據(jù)Grid_idArray中的值確定相應(yīng)局部索引

//過濾步驟

for the partition of VoronoiIndexRdd do

CandidateSetRDD←

VoronoiIndexRdd.flatmap(array?

VoronoiIndexRdd.VRkNN-Filter(P,qi,k));

Flag=0;

for each pointpin CandidateSetRDD do

ifpis in the neighboring partition do

flag=1;

partition←FINDPartition(P,p)

endif

endfor

endfor

if flag=1 do

for each partition do

CandidateSetRDD←

VoronoiIndexRdd.Flatmap(array?

VoronoiIndexRdd.VRkNN-Filter(P,q,k));

endfor

CandidateSetRDD.Merge();

endif

//精煉步驟

for the partition of CandidateSetRDD do

VerificationSetRDD←

CandidateSetRDD.Flatmap(array?

CandidateSetRDD.VRkNN-Verification (P,q,k));

result.Initialize;

result←VerificationSetRDD.reduce();

endfor

returnresult;

end

定理4 算法SV_RkNN的過濾步驟可以返回所有的結(jié)果(完備性)，且算法SV_RkNN的精煉步驟返回的結(jié)果是正確的(正確性)。

證明：(完備性)SV_RkNN算法的過濾步驟可以產(chǎn)生所有的候選。因?yàn)樗惴ǖ倪^濾步驟分成兩個(gè)階段，第一個(gè)階段確定包含查詢點(diǎn)所在的分區(qū)，執(zhí)行一次VRkNN-Filter過濾算法，過濾掉不可能成為候選的對(duì)象，根據(jù)定理3可知，過濾掉的對(duì)象不可能成為候選。第二個(gè)階段根據(jù)對(duì)象是否在其它的分區(qū)中，確定并行處理的分區(qū)，并再次進(jìn)行VRkNN-Filter過濾處理，得到其它分區(qū)中的所有候選，并將所有候選合并為候選集，根據(jù)定理3可知，過濾掉的對(duì)象不可能成為候選，由此可知候選集中的對(duì)象包含了所有的結(jié)果，算法是完備的。

(正確性)SV_RkNN算法的精煉步驟不會(huì)刪掉真正的結(jié)果并且不會(huì)返回的不是實(shí)際RkNN的結(jié)果。首先，算法對(duì)候選集中對(duì)象所在分區(qū)進(jìn)行處理，執(zhí)行VRkNN-Verification精煉算法，對(duì)候選集中的所有對(duì)象進(jìn)行處理，刪除錯(cuò)誤的候選，根據(jù)定理3可知，刪除的候選是不可能成為真正的結(jié)果，保證了結(jié)果的正確性?？梢岳梅醋C法來證明結(jié)果集中不會(huì)返回不是實(shí)際RkNN的結(jié)果。假設(shè)結(jié)果集中返回的點(diǎn)p不是實(shí)際RkNN的結(jié)果，則p的kNN中一定不包含查詢點(diǎn)q，即p與q之間的距離一定大于p與其第k最近鄰之間的距離，而這樣的點(diǎn)在算法中一定會(huì)被刪除，不能成為結(jié)果，所以與假設(shè)相矛盾，由此證明結(jié)果集中不會(huì)返回不是實(shí)際RkNN的結(jié)果。證畢。

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)是在一個(gè)包含4個(gè)節(jié)點(diǎn)的Spark分布式集群上進(jìn)行，它由1個(gè)master節(jié)點(diǎn)和3個(gè)worker節(jié)點(diǎn)組成，每臺(tái)機(jī)器的硬件配置都是：CPU型號(hào)為Intel CORE i5-104002.9 GHz六核處理器，內(nèi)存為8 GB，硬盤1 TB。操作系統(tǒng)是64 位 Ubuntu16.04，Hadoop版本為2.7.1，JDK版本為1.7，Spark版本為2.0.1。

實(shí)驗(yàn)中使用二維點(diǎn)數(shù)據(jù)來測(cè)試所提出的SV_RkNN算法，實(shí)驗(yàn)數(shù)據(jù)來自于OpenStreetMap的3個(gè)數(shù)據(jù)集，這些數(shù)據(jù)集可以在SpatialHadoop官網(wǎng)[23]下載。數(shù)據(jù)集具體包括：Lakes、Parks和Roads。數(shù)據(jù)集詳情見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)測(cè)試構(gòu)建索引性能，實(shí)驗(yàn)在不同分布數(shù)據(jù)集上分別比較本文創(chuàng)建索引算法GV-Index和文獻(xiàn)[2]中基于Map-Reduce的Voronoi-based算法(稱為MR_VD)的性能。

采用上述3個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，對(duì)比GV-Index算法和MR_VD算法構(gòu)建索引耗時(shí)，實(shí)驗(yàn)結(jié)果如圖4所示。由圖4可知，對(duì)于每個(gè)數(shù)據(jù)集來說，GV-Index算法的構(gòu)建索引耗時(shí)明顯少于MR_VD算法的耗時(shí)，這是因?yàn)镾park基于內(nèi)存計(jì)算的特點(diǎn)，可以在內(nèi)存中進(jìn)行數(shù)據(jù)緩存，節(jié)省了時(shí)間。

圖4 數(shù)據(jù)集大小對(duì)索引構(gòu)建耗時(shí)的影響

實(shí)驗(yàn)測(cè)試算法總的執(zhí)行時(shí)間，即算法響應(yīng)時(shí)間。實(shí)驗(yàn)在不同分布數(shù)據(jù)集上分別比較SV_RkNN算法和文獻(xiàn)[7]中基于LocationSpark的RkNN算法(稱為LS_RkNN)和文獻(xiàn)[7]中的基于Spatial Hadoop的RkNN算法(稱為SH_RkNN)的性能。

首先采用上述3個(gè)真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，取k=5，分析數(shù)據(jù)集規(guī)模對(duì)算法的查詢時(shí)間的影響。圖5給出了SV_RkNN算法、LS_RkNN算法和SH_RkNN算法的響應(yīng)時(shí)間隨數(shù)據(jù)集大小的變化關(guān)系。由圖5可知，數(shù)據(jù)集的大小對(duì)3種算法的響應(yīng)時(shí)間的影響不大，算法具有較好的穩(wěn)定性。這是因?yàn)?，兩種算法均采用了索引結(jié)構(gòu)，而索引能夠使得數(shù)據(jù)的查詢范圍縮小在限定的范圍內(nèi)，為此數(shù)據(jù)量的大小對(duì)響應(yīng)時(shí)間的影響不大。但是，SV_RkNN算法的響應(yīng)時(shí)間明顯少于LS_RkNN算法和SH_RkNN算法，這主要是因SV_RkNN方法進(jìn)行RkNN查詢時(shí)，基于雙層索引結(jié)構(gòu)，通過全局索引的過濾確定局部分區(qū)，可以避免訪問不必要的數(shù)據(jù)分區(qū)，只需在相關(guān)的數(shù)據(jù)分區(qū)內(nèi)執(zhí)行VRkNN查找，基于Voronoi圖的性質(zhì)3，一個(gè)點(diǎn)的Voronoi近鄰最多為6，因此VRkNN中的kNN及每個(gè)候選點(diǎn)的第k個(gè)NN的查詢分別只需訪問6k個(gè)數(shù)據(jù)點(diǎn)，明顯縮短了響應(yīng)時(shí)間，效果較好。

圖5 數(shù)據(jù)集大小對(duì)響應(yīng)時(shí)間的影響

然后采用真實(shí)數(shù)據(jù)集Parks 和Roads進(jìn)行實(shí)驗(yàn)，分析k值的變化對(duì)SV_RkNN算法、LS_RkNN算法和SH_RkNN算法響應(yīng)時(shí)間的影響。實(shí)驗(yàn)選取k=1、5、10、15、20和30，實(shí)驗(yàn)結(jié)果分別如圖6和圖7所示。由圖6和圖7可知，k值的變化對(duì)SV_RkNN算法和LS_RkNN算法的影響明顯小于k值的變化對(duì)LS_RkNN算法的影響。這是因?yàn)?，隨著k值的增大，候選數(shù)量明顯增加，每一個(gè)分節(jié)點(diǎn)處理的數(shù)據(jù)量變大，SH_RkNN算法基于Spatial Hadoop，采取磁盤存儲(chǔ)策略，讀取大量的候選集需要多次的磁盤訪問，增加了輸入輸出操作的代價(jià)。而SV_RkNN算法和LS_RkNN算法基于Spark，采用基于內(nèi)存計(jì)算的策略，減少了磁盤訪問的時(shí)間，查詢過程中使用的數(shù)據(jù)直接可用，因此相對(duì)于k值的增大而言相應(yīng)的執(zhí)行時(shí)間變化不大。而對(duì)比SV_RkNN算法和LS_RkNN算法，由于LS_RkNN需要執(zhí)行KNN查詢(K遠(yuǎn)大于k)，隨著k值的增大，候選數(shù)量明顯增加，而對(duì)于SV_RkNN算法，kNN及每個(gè)候選點(diǎn)的第k個(gè)NN的查詢?cè)L問的數(shù)量分別為6k，因此隨著k值的增大，SV_RkNN算法的性能優(yōu)于LS_RkNN算法。

圖6 Parks數(shù)據(jù)集k值變化對(duì)響應(yīng)時(shí)間的影響

圖7 Roads數(shù)據(jù)集k值變化對(duì)響應(yīng)時(shí)間的影響

最后采用真實(shí)數(shù)據(jù)集Parks進(jìn)行實(shí)驗(yàn)，取k=5，分析不同的計(jì)算節(jié)點(diǎn)數(shù)量對(duì)SV_RkNN算法、LS_RkNN算法和SH_RkNN算法響應(yīng)時(shí)間的影響。實(shí)驗(yàn)選取節(jié)點(diǎn)個(gè)數(shù)分別為1、2、3、4，實(shí)驗(yàn)結(jié)果如圖8所示。由圖8可知，LS_RkNN算法的響應(yīng)時(shí)間隨著節(jié)點(diǎn)個(gè)數(shù)的增加而減少，并且隨著節(jié)點(diǎn)數(shù)量越來越多，響應(yīng)時(shí)間的減少幅度變小，這是因?yàn)楣?jié)點(diǎn)數(shù)量的增加會(huì)增加節(jié)點(diǎn)之間的通信和調(diào)度時(shí)間，而且隨著節(jié)點(diǎn)數(shù)量的增加，響應(yīng)時(shí)間的減小幅度逐漸降低。但是，隨著節(jié)點(diǎn)數(shù)量的增加，SV_RkNN算法和SH_RkNN算法的響應(yīng)時(shí)間基本沒有改變，而SV_RkNN算法的性能優(yōu)于SH_RkNN算法，這是因?yàn)?，通過全局索引確定分區(qū)后，RkNN的查找只在確定的分區(qū)進(jìn)行，也就是說，由查詢q的位置和k的值，可確定RkNN的查找通常在一個(gè)分區(qū)中進(jìn)行，響應(yīng)時(shí)間與節(jié)點(diǎn)的個(gè)數(shù)無關(guān)。

圖8 節(jié)點(diǎn)個(gè)數(shù)的變化對(duì)響應(yīng)時(shí)間的影響

5 結(jié)束語

本文對(duì)基于Spark框架的并行反向k最近鄰查詢進(jìn)行研究，基于Voronoi圖的良好特性，構(gòu)建了基于網(wǎng)格-Voronoi圖的雙層索引機(jī)構(gòu)，給出了索引構(gòu)建算法，并在此索引結(jié)構(gòu)上實(shí)現(xiàn)了基于Spark的并行反向k近鄰查詢，提出SV_RkNN算法，并通過真實(shí)數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)，將SV_RkNN與基于LocationSpark的RkNN算法和基于SpatialHadoop的RkNN算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果驗(yàn)證了SV_RkNN相對(duì)比較算法具有更好的查詢性能和較好的穩(wěn)定性。下一步計(jì)劃研究基于Spark框架的空間連接查詢，通過索引結(jié)構(gòu)的改進(jìn)，提高查詢的性能。