面向不確定數(shù)據(jù)的概率障礙k聚集最近鄰查詢*

于嘉希，李 松，張麗平，劉 蕾

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

1 引言

最近鄰查詢[1]問(wèn)題是空間數(shù)據(jù)查詢研究的重要問(wèn)題之一，即給定一個(gè)查詢點(diǎn)和數(shù)據(jù)點(diǎn)集，求解到該查詢點(diǎn)距離最近的一個(gè)數(shù)據(jù)點(diǎn)。為了滿足不同情況下的查詢需求，近年來(lái)對(duì)最近鄰查詢的研究已擴(kuò)展到k最近鄰查詢[2]、組最近鄰查詢[3]、組障礙最近鄰查詢[4]、障礙k最近鄰查詢[5-6]、反向最近鄰查詢[7]、聚集最近鄰查詢[8]、可視最近鄰查詢[9]、不確定數(shù)據(jù)的最近鄰查詢[10]、不確定數(shù)據(jù)的反近鄰查詢[11]、不確定數(shù)據(jù)的組近鄰查詢[12]等方面。

聚集最近鄰查詢是最近鄰查詢的變體之一，在基于位置的服務(wù)中有著廣泛的應(yīng)用。給定數(shù)據(jù)點(diǎn)集P={p1,p2,…,pn}和查詢點(diǎn)集Q={q1,q2,…,qn}，通過(guò)計(jì)算數(shù)據(jù)點(diǎn)p到查詢點(diǎn)集Q的聚集距離，從而得到查詢結(jié)果。這里定義了3種聚集函數(shù)，分別為sum、max和min，聚集最近鄰的查詢結(jié)果依賴于不同的聚集函數(shù)，并且返回到查詢點(diǎn)集聚集距離最小的數(shù)據(jù)點(diǎn)。類(lèi)似的，k聚集最近鄰查詢返回聚集距離最小的k個(gè)數(shù)據(jù)點(diǎn)的集合。

在實(shí)際應(yīng)用當(dāng)中，需要考慮一些真實(shí)環(huán)境下的限制因素?？臻g數(shù)據(jù)之間往往會(huì)存在無(wú)法穿過(guò)的障礙物，例如河流、建筑物等，這時(shí)兩點(diǎn)間距離不再是歐氏距離，因此需要計(jì)算障礙距離。而隨著技術(shù)的進(jìn)步和人們對(duì)采集和獲取數(shù)據(jù)技術(shù)逐漸深入，不確定數(shù)據(jù)得到了廣泛的重視，由于原始數(shù)據(jù)的不準(zhǔn)確、處理缺失值、粗細(xì)粒度的數(shù)據(jù)集合等原因，不確定數(shù)據(jù)廣泛存在于經(jīng)濟(jì)、軍事、物流、金融、電信、氣象、地理信息等領(lǐng)域[13]。不確定數(shù)據(jù)和障礙環(huán)境下的k聚集最近鄰查詢是一個(gè)新的問(wèn)題。本文主要針對(duì)不確定數(shù)據(jù)的概率障礙k聚集最近鄰查詢問(wèn)題進(jìn)行研究，提出基于不確定Voronoi圖的概率障礙k聚集最近鄰查詢方法，返回到查詢點(diǎn)集的聚集距離最小的k個(gè)數(shù)據(jù)點(diǎn)集，并保證其概率值大于給定閾值。

2 相關(guān)工作

傳統(tǒng)的近鄰查詢問(wèn)題都是在理想的歐氏環(huán)境下進(jìn)行研究，但實(shí)際應(yīng)用當(dāng)中物體之間往往存在一些無(wú)法穿過(guò)的障礙物，因此需要考慮到障礙距離的計(jì)算。文獻(xiàn)[4]研究了障礙組最近鄰查詢問(wèn)題，通過(guò)構(gòu)造剪枝區(qū)域去剪枝對(duì)障礙距離計(jì)算沒(méi)有影響的障礙，從而減少計(jì)算量，提高查詢效率。文獻(xiàn)[5]和文獻(xiàn)[6]利用障礙Voronoi圖的特性提出剪枝策略，減少了需要處理的數(shù)據(jù)點(diǎn)個(gè)數(shù)。

文獻(xiàn)[8]研究了聚集最近鄰查詢，提出了3種利用R樹(shù)處理聚集最近鄰查詢的方法：MQM（multiple query method）、SPM（single point method）和 MBM（minimum bounding method）。這3種方法中，MBM是最優(yōu)算法。文獻(xiàn)[14]研究了路網(wǎng)環(huán)境下移動(dòng)對(duì)象的k聚集最近鄰查詢方法，通過(guò)剪枝得到候選集合的方法進(jìn)行求解。當(dāng)聚集最近鄰查詢的聚集函數(shù)為sum時(shí)，被稱(chēng)為組最近鄰查詢。文獻(xiàn)[3]給出了3種基于R樹(shù)索引的處理組最近鄰查詢的方法，分別是MQM、SPM和MBM。文獻(xiàn)[15]提出了一種基于查詢點(diǎn)集Q中兩種最遠(yuǎn)點(diǎn)構(gòu)成的橢圓及其MBR（minimum bounding rectangle）對(duì)中間節(jié)點(diǎn)進(jìn)行剪枝的方法。文獻(xiàn)[16]針對(duì)無(wú)索引數(shù)據(jù)點(diǎn)集，提出了up-ANN算法和投影剪枝算法，有效提高了組近鄰查詢效率。

以上處理聚集最近鄰查詢的方法針對(duì)的都是確定數(shù)據(jù)，而現(xiàn)實(shí)應(yīng)用中往往要處理大量的不確定數(shù)據(jù)。文獻(xiàn)[17]對(duì)不確定數(shù)據(jù)的聚集最近鄰查詢進(jìn)行研究，并提出了空間剪枝和概率剪枝兩種方法，對(duì)數(shù)據(jù)點(diǎn)集進(jìn)行剪枝，有效提高了查詢效率。文獻(xiàn)[18]基于存在不確定數(shù)據(jù)，研究了范圍查詢、最近鄰查詢、反最近鄰查詢的解決方法。文獻(xiàn)[19-20]提出了不確定數(shù)據(jù)的組最近鄰查詢方法。

已有方法無(wú)法處理不確定數(shù)據(jù)的障礙k聚集最近鄰查詢問(wèn)題，因此本文提出了基于不確定Voronoi圖的概率障礙k聚集最近鄰查詢方法。

3 基礎(chǔ)定義

本文研究位置不確定數(shù)據(jù)，并采用如下形式的不確定數(shù)據(jù)模型：給定不確定數(shù)據(jù)點(diǎn)集P={p1,p2,…,pn}，每個(gè)不確定數(shù)據(jù)在各自的不確定區(qū)域中任意分布，該區(qū)域可以為任意形狀，并以一個(gè)概率密度函數(shù)描述它在該區(qū)域內(nèi)的分布情況。本文假定不確定數(shù)據(jù)pi位于一個(gè)以Cpi為圓心，為半徑的不確定區(qū)域圓UR(pi)中。以O(shè)={O1,O2,…,On}描述障礙物集合，并假定各個(gè)障礙物之間互不相交，且障礙物與不確定數(shù)據(jù)的不確定區(qū)域互不重疊，以線段來(lái)表示障礙物。本文求解概率障礙k聚集最近鄰查詢問(wèn)題使用不確定Voronoi圖，其相關(guān)定義在文獻(xiàn)[19,21]中已經(jīng)給出，本文在文獻(xiàn)[4]提出的可視性、障礙距離等基礎(chǔ)上，提出以下定義。

定義1（不確定數(shù)據(jù)的最小障礙距離與最大障礙距離）給定不確定數(shù)據(jù)點(diǎn)集合P={p1,p2,…,pn},對(duì)于不確定數(shù)據(jù)點(diǎn)pi,pj∈P，其不確定區(qū)域半徑分別為rpi、rpj，則pi到pj的最小障礙距離為，最大障礙距離為。

定義2（障礙聚集距離）給定數(shù)據(jù)點(diǎn)集P={p1,p2,…,pn}，查詢點(diǎn)集Q={q1,q2,…,qn}，障礙集合O={O1,O2,…,On}。數(shù)據(jù)點(diǎn)p到查詢點(diǎn)集Q的障礙聚集距離定義為：

其中，disto(p,qi)代表數(shù)據(jù)點(diǎn)p到查詢點(diǎn)qi的障礙距離。f代表聚集函數(shù)sum、max或min。根據(jù)不同的聚集函數(shù)，可根據(jù)如下方式計(jì)算其相應(yīng)的聚集距離：

定義3（障礙聚集最近鄰查詢）給定數(shù)據(jù)點(diǎn)集P={p1,p2,…,pn}，查詢點(diǎn)集Q={q1,q2,…,qn}，障礙集合O={O1,O2,…,On}，障礙聚集最近鄰查詢返回到查詢點(diǎn)集的障礙聚集距離adisto-f(p,Q)最小的數(shù)據(jù)點(diǎn)，即滿足：

定義4（概率障礙k聚集最近鄰查詢）給定不確定數(shù)據(jù)點(diǎn)集合P={p1,p2,…,pn}，查詢點(diǎn)集合Q={q1,q2,…,qn}，障礙集合O={O1,O2,…,On}，閾值T，則不確定數(shù)據(jù)的概率障礙k聚集最近鄰查詢返回形如{s,prob(s)}的查詢結(jié)果。其中s為數(shù)據(jù)點(diǎn)集合的子集，由到查詢點(diǎn)集的障礙聚集距離最小的k個(gè)數(shù)據(jù)點(diǎn)組成，prob(s)為該集合成為查詢點(diǎn)集Q的障礙k聚集最近鄰集合的概率值，且prob(s)＞T,T∈(0,1],i=1,2,…,k。prob(s)計(jì)算公式為：

其中，di(r)和Di(r)分別為pi到查詢點(diǎn)集的障礙聚集距離的概率密度函數(shù)和累計(jì)分布函數(shù)。

4 基于不確定Voronoi圖的概率障礙k聚集最近鄰查詢方法

4.1 查詢點(diǎn)集處理階段

聚集最近鄰查詢的難點(diǎn)為針對(duì)多個(gè)查詢點(diǎn)求解在不同聚集函數(shù)下的聚集最近鄰點(diǎn)，因此本節(jié)通過(guò)Min_Circle(Q)算法求解查詢點(diǎn)集的最小覆蓋圓，用該最小覆蓋圓的圓心O代表查詢點(diǎn)集的分布情況，以此作為查詢點(diǎn)中心q，將問(wèn)題進(jìn)行簡(jiǎn)化，方便后文的剪枝處理階段。本文采用增量法計(jì)算查詢點(diǎn)集的最小覆蓋圓，提出算法Min_Circle(Q)。首先做出前i-1個(gè)查詢點(diǎn)的最小覆蓋圓，再加入第i個(gè)點(diǎn)，如果它在圓內(nèi)或圓周上，則什么也不做；否則取距離當(dāng)前最小覆蓋圓圓心的最遠(yuǎn)點(diǎn)qm，得到新的最小覆蓋圓。重復(fù)以上過(guò)程依次遍歷查詢點(diǎn)集，直至所有查詢點(diǎn)都在圓中（或圓周上），則該圓就是所求的最小覆蓋圓。

如圖1為求解最小覆蓋圓的示例圖。首先任取兩點(diǎn)qi、qj，以兩點(diǎn)間距離dist(qi,qj)為直徑做圓，得到當(dāng)前最小覆蓋圓O1。對(duì)于Q中的點(diǎn)，判斷它是否在當(dāng)前最小覆蓋圓內(nèi)（或圓周上）。根據(jù)判斷結(jié)果，執(zhí)行相應(yīng)語(yǔ)句，找到與當(dāng)前最小覆蓋圓圓心距離最遠(yuǎn)的查詢點(diǎn)qm，不斷擴(kuò)大最小覆蓋圓，最終使之覆蓋所有查詢點(diǎn)。所得到的圓就是覆蓋所有查詢點(diǎn)的最小覆蓋圓。

Fig.1 Example of minimum covered circle圖1 最小覆蓋圓示例圖

基于以上討論，給出算法1。

算法1 Min_Circle(Q)

4.2 過(guò)濾階段

過(guò)濾階段為了更好地過(guò)濾掉無(wú)關(guān)數(shù)據(jù)點(diǎn)，采用剪枝策略對(duì)數(shù)據(jù)點(diǎn)集P進(jìn)行剪枝處理，從而得到候選集合。為得到剪枝策略，首先給出如下定理。

定理1給定不確定數(shù)據(jù)點(diǎn)集合P={p1,p2,…,pn}，對(duì)于某一查詢點(diǎn)q，若它所在的不確定Voronoi區(qū)域生成點(diǎn)集合為M，則它的k最近鄰點(diǎn)必包含在M及M的k級(jí)鄰接生成點(diǎn)中。

證明由不確定Voronoi圖的性質(zhì)可知，若查詢點(diǎn)q落在不確定Voronoi區(qū)域UVP(pi)中，則q到生成點(diǎn)pi的距離小于q到其他生成點(diǎn)的距離。若該Voronoi區(qū)域?yàn)閱紊牲c(diǎn)Voronoi區(qū)域SUV(pi),則pi一定是q的最近鄰點(diǎn)，故其k最近鄰點(diǎn)在pi的k級(jí)鄰接生成點(diǎn)中；若該Voronoi區(qū)域?yàn)槎嗌牲c(diǎn)Voronoi區(qū)域MUV(pi,pj)，q的最近鄰點(diǎn)一定在此區(qū)域的多生成點(diǎn)中，其k最近鄰點(diǎn)一定在多生點(diǎn)的k級(jí)鄰接生成點(diǎn)中。故該定理成立。 □

定理2[22]對(duì)于不確定Voronoi單元UVP(pi)內(nèi)任意一點(diǎn)q，則對(duì)q的第k+1個(gè)最近鄰qk+1有qk+1∈AG1(p)∪AG2(p)∪…∪AGk(p)(k為整數(shù)，k≥1)，即q的第k+1個(gè)最近鄰點(diǎn)在q的最近鄰前k級(jí)生成點(diǎn)中。

定理3若某數(shù)據(jù)點(diǎn)pi在不確定Voronoi圖中的所有鄰接生成點(diǎn)都被剪枝，則pi也被剪枝。

證明若某數(shù)據(jù)點(diǎn)pi的所有鄰接生成點(diǎn)都被剪枝，說(shuō)明在其鄰接生成點(diǎn)所在層次范圍內(nèi)，已有數(shù)據(jù)點(diǎn)的障礙聚集距離小于該鄰接生成點(diǎn)，則pi不可能成為所求結(jié)果，故可被剪枝。 □

定理4對(duì)于某一不確定數(shù)據(jù)點(diǎn)p和查詢點(diǎn)q，記num(p,q)為p與q之間所有到q可視的點(diǎn)的個(gè)數(shù)，若num(p,q)≥k，則將p剪枝。

證明當(dāng)k=1時(shí)，設(shè)p與q之間經(jīng)過(guò)點(diǎn)p1，且p1與q可視，則p1到q的距離一定小于p到q的距離，故p一定不是所求，可將其剪枝；當(dāng)k＞1時(shí)，p與q經(jīng)過(guò)的數(shù)據(jù)點(diǎn)中已有超過(guò)k個(gè)與q可視，說(shuō)明這些數(shù)據(jù)點(diǎn)到q的距離一定小于q到p的距離，則p一定不是所求，可將其剪枝。 □

定理5若某一數(shù)據(jù)點(diǎn)到查詢點(diǎn)集的最小障礙聚集距離大于adistk-o-max，則可將該數(shù)據(jù)點(diǎn)剪枝。其中，adistk-o-max表示數(shù)據(jù)點(diǎn)到查詢點(diǎn)集的最大障礙聚集距離中第k小的距離。

證明以第k小的最大障礙聚集距離為半徑做圓，其圓心為查詢點(diǎn)集的中心，則不確定區(qū)域與該圓無(wú)交集的數(shù)據(jù)點(diǎn)均可剪枝。這是由于這些點(diǎn)到查詢點(diǎn)的最小障礙聚集距離已經(jīng)大于第k小的最大距離adistk-o-max，說(shuō)明在該圓范圍內(nèi)已經(jīng)至少存在k個(gè)數(shù)據(jù)點(diǎn)到查詢點(diǎn)的障礙聚集距離小于等于adistk-o-max，因此可將其剪枝。 □

過(guò)濾階段的具體剪枝規(guī)則根據(jù)不同的聚集函數(shù)有所不同，下面針對(duì)不同的聚集函數(shù)，分別給出相應(yīng)的剪枝規(guī)則。

4.2.1 聚集函數(shù)f=sum

當(dāng)聚集函數(shù)為sum時(shí)，求解到查詢點(diǎn)集的障礙距離之和最小的k個(gè)數(shù)據(jù)點(diǎn)。過(guò)濾階段采用算法1得到的中心點(diǎn)q代表查詢點(diǎn)集的分布。根據(jù)定理1至定理5，提出如下5項(xiàng)剪枝策略。

剪枝策略1只有查詢點(diǎn)中心q到生成點(diǎn)的個(gè)數(shù)小于或等于k的生成點(diǎn)才能放入候選集中。

剪枝策略2若某數(shù)據(jù)點(diǎn)pi在不確定Voronoi圖中的所有鄰接生成點(diǎn)都被剪枝，則pi也被剪枝。

剪枝策略3對(duì)于某一不確定數(shù)據(jù)點(diǎn)p和查詢點(diǎn)q，記num(p,q)為p與q之間所有到q可視的點(diǎn)的個(gè)數(shù)，若num(p,q)≥k，則將p剪枝。

剪枝策略4若某一數(shù)據(jù)點(diǎn)到查詢點(diǎn)的最小障礙距離大于distk-o-max，則可將該數(shù)據(jù)點(diǎn)剪枝。其中distk-o-max表示數(shù)據(jù)點(diǎn)到查詢點(diǎn)的最大障礙距離中第k小的距離，即distk-o-max=k-min{disto-max(q,Ci)}。

剪枝策略5用隊(duì)列H存儲(chǔ)元組(pi,disto-min(q,pi))，并按disto-min(q,pi)升序排列，使用剪枝策略4進(jìn)行剪枝。若某數(shù)據(jù)點(diǎn)p被剪枝，則p后的所有查詢點(diǎn)都被剪枝，過(guò)濾階段結(jié)束。

圖2為f=sum情況下的概率障礙k聚集最近鄰查詢剪枝階段示例圖。在對(duì)數(shù)據(jù)點(diǎn)集P進(jìn)行剪枝時(shí)，剪枝策略1根據(jù)定理2提出，要查找q的第i+1個(gè)最近鄰只需在q最近鄰的前i級(jí)鄰接生成點(diǎn)中進(jìn)行查詢，確保了查詢點(diǎn)集的障礙k聚集最近鄰點(diǎn)一定在候選集合中，且不會(huì)包含多余的點(diǎn)，保證了過(guò)濾算法的正確性。剪枝策略2根據(jù)定理3提出，對(duì)數(shù)據(jù)點(diǎn)集進(jìn)行剪枝，若某數(shù)據(jù)點(diǎn)pi的所有鄰接生成點(diǎn)都被剪枝，則說(shuō)明在此區(qū)域中不會(huì)再有障礙聚集距離小于已獲得的障礙聚集距離，則可將其剪枝。剪枝策略3根據(jù)定理4提出，若q與pi之間存在超過(guò)k個(gè)可視的數(shù)據(jù)點(diǎn)，則可將pi剪枝。剪枝策略4根據(jù)定理5提出，通過(guò)求解第k小的最大障礙距離進(jìn)而剪枝不可能成為結(jié)果的數(shù)據(jù)點(diǎn)。剪枝策略5利用隊(duì)列H并將其元素排序，結(jié)合剪枝策略4，將不滿足查詢要求的數(shù)據(jù)一次性剪枝。

Fig.2 Example of pruning phase in case of f=sum圖2 f=sum情況下的剪枝階段示例圖

基于以上討論，給出算法2。

算法2 Sum_Can(Q,P,O,k)

4.2.2 聚集函數(shù)f=max

當(dāng)聚集函數(shù)為max時(shí)，求解使到查詢點(diǎn)集的障礙距離中最大值最小的k個(gè)數(shù)據(jù)點(diǎn)。過(guò)濾階段使用以下幾種剪枝策略對(duì)數(shù)據(jù)點(diǎn)集P進(jìn)行剪枝處理，以減少無(wú)關(guān)數(shù)據(jù)對(duì)結(jié)果計(jì)算的影響。根據(jù)定理1至定理5，提出以下4項(xiàng)剪枝策略。

剪枝策略1根據(jù)定理2，只有查詢點(diǎn)中心q到生成點(diǎn)的個(gè)數(shù)小于或等于k的生成點(diǎn)才能放入候選集中。

剪枝策略2根據(jù)定理3，若某數(shù)據(jù)點(diǎn)pi在不確定Voronoi圖中的所有鄰接生成點(diǎn)都被剪枝，則pi也被剪枝。

剪枝策略3根據(jù)定理4，對(duì)于某一不確定數(shù)據(jù)點(diǎn)p和查詢點(diǎn)q，記num(p,q)為p與q之間所有到q可視的點(diǎn)的個(gè)數(shù)，若num(p,q)≥k，則將p剪枝。

剪枝策略4根據(jù)定理5，若某一數(shù)據(jù)點(diǎn)到查詢點(diǎn)集的最小障礙聚集距離大于adistk-o-max，則可將該數(shù)據(jù)點(diǎn)剪枝。其中adistk-o-max表示第k小的最大障礙聚集距離，adistk-o-max=k-min{adisto-max(Q,pi)}。

基于以上討論，給出算法3。

算法3 Max_Can(P,Q,O,k)

4.2.3 聚集函數(shù)f=min

當(dāng)聚集函數(shù)為min時(shí)較為簡(jiǎn)單，需求解到查詢點(diǎn)集合的最小障礙距離最小的k個(gè)數(shù)據(jù)點(diǎn)。由定理1可知，給定某一查詢點(diǎn)，確定它所在的不確定Voronoi區(qū)域，則它的k近鄰點(diǎn)一定在此區(qū)域的生成點(diǎn)及其k級(jí)鄰接生成點(diǎn)中，因此在過(guò)濾階段利用不確定Voronoi圖的性質(zhì)將查詢點(diǎn)集的生成點(diǎn)及鄰接生成點(diǎn)加入候選集合Min_Candidate。f=min情況下的剪枝規(guī)則由定理1給出，首先找到查詢點(diǎn)集中心q在不確定Voronoi圖中的位置，確定其所在的不確定Voronoi區(qū)域，將該不確定Voronoi區(qū)域的生成點(diǎn)及其k級(jí)鄰接生成點(diǎn)放入候選集合。

算法4 Min_Can(P,Q,O,k)

4.3 精煉階段

本文通過(guò)前兩個(gè)階段，對(duì)數(shù)據(jù)點(diǎn)集進(jìn)行了剪枝，移除了不可能成為查詢結(jié)果的數(shù)據(jù)點(diǎn)，并得到了候選集合。接下來(lái)在精煉階段，要對(duì)候選集合中的數(shù)據(jù)點(diǎn)進(jìn)行概率值求解，并與給定閾值進(jìn)行比較，得到結(jié)果集合。給出算法5。

算法5 POkANN(P,Q,O,k)

5 實(shí)驗(yàn)與分析

通過(guò)實(shí)驗(yàn)驗(yàn)證本文提出的POkANN方法的性能。由于本文首次對(duì)概率障礙k聚集最近鄰查詢問(wèn)題進(jìn)行研究，且現(xiàn)有的聚集最近鄰查詢算法沒(méi)有考慮障礙物存在對(duì)結(jié)果的影響，返回的查詢結(jié)果也只有一個(gè)，無(wú)法直接用于概率障礙k聚集最近鄰查詢，不能直接進(jìn)行比較，從而基于基本查詢技術(shù)，設(shè)計(jì)了兩個(gè)基本算法與本文算法進(jìn)行比較。第一個(gè)算法直接計(jì)算各個(gè)數(shù)據(jù)點(diǎn)到查詢點(diǎn)集的障礙聚集距離，計(jì)算其成為結(jié)果的概率值，返回形如{s,prob(s)}的查詢結(jié)果。其中s為數(shù)據(jù)點(diǎn)集合的子集，由到查詢點(diǎn)集的障礙聚集距離最小的k個(gè)數(shù)據(jù)點(diǎn)組成，prob(s)為該集合成為查詢點(diǎn)集Q的障礙k聚集最近鄰集合的概率值且滿足prob(s)＞T，將該算法稱(chēng)為POkANN_Basic算法。第二個(gè)算法稱(chēng)為POANN*算法，POANN*算法的主要思想是對(duì)文獻(xiàn)[12]中經(jīng)過(guò)改進(jìn)的POANN*算法加入障礙后重復(fù)調(diào)用k次來(lái)完成概率障礙k聚集最近鄰查詢?nèi)蝿?wù)。

實(shí)驗(yàn)硬件環(huán)境為AMD雙核2.2 GHz處理器，2 GB內(nèi)存，Windows 7操作系統(tǒng)，使用Visual C++6.0實(shí)現(xiàn)。不確定數(shù)據(jù)點(diǎn)集P來(lái)自真實(shí)數(shù)據(jù)集Long Beach Road（http://www.rtreeportal.org），由53 144個(gè)矩形表示數(shù)據(jù)點(diǎn)，對(duì)于每個(gè)不確定數(shù)據(jù)，其不確定區(qū)域由矩形的中心為圓心，對(duì)角線的一半為半徑形成的區(qū)域圓來(lái)表示。查詢點(diǎn)集Q為隨機(jī)生成的點(diǎn)，并隨機(jī)生成障礙集合，采用UV-index對(duì)不確定Voronoi圖進(jìn)行索引，障礙集由線段表示。本實(shí)驗(yàn)主要從k值、障礙物規(guī)模、查詢點(diǎn)集規(guī)模對(duì)查詢時(shí)間的影響及剪枝比率進(jìn)行驗(yàn)證，并將POkANN_Basic算法和POANN*算法與本文提出的POkANN算法進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果為執(zhí)行100次查詢結(jié)果取平均值得到。

圖3和圖4分別驗(yàn)證了聚集函數(shù)sum和max情況下k值對(duì)查詢時(shí)間的影響。從圖中可以看出，在其他條件不變的情況下，隨著k值的增加，由于3種算法對(duì)于障礙聚集距離和概率值的計(jì)算量增加，導(dǎo)致查詢時(shí)間逐漸增長(zhǎng)。但由于本文POkANN算法具有剪枝策略，去除了不可能成為結(jié)果的數(shù)據(jù)點(diǎn)，有效地減少了計(jì)算量，查詢時(shí)間優(yōu)于另外兩種算法。

Fig.3 Effect ofkon query time(f=sum)圖3 k值對(duì)查詢時(shí)間的影響（f=sum）

Fig.4 Effect ofkon query time(f=max)圖4 k值對(duì)查詢時(shí)間的影響（f=max）

圖5和圖6分別驗(yàn)證了聚集函數(shù)sum和max情況下障礙物個(gè)數(shù)對(duì)查詢時(shí)間的影響。從圖中可以看出，在其他條件不變的情況下，隨著障礙物個(gè)數(shù)的增加，查詢時(shí)間也隨之增加，這是由于大量的障礙聚集距離計(jì)算量所導(dǎo)致的。隨著障礙物的增加，另兩種算法的查詢時(shí)間顯著增長(zhǎng)，而本文POkANN算法優(yōu)勢(shì)在于過(guò)濾階段的剪枝策略將不可能成為查詢結(jié)果的數(shù)據(jù)點(diǎn)剪枝，有效減少了障礙聚集距離的計(jì)算量，因此POkANN算法略好于另兩種算法。

Fig.5 Effect of the number of obstacles on query time(f=sum)圖5 障礙物個(gè)數(shù)對(duì)查詢時(shí)間的影響（f=sum）

Fig.6 Effect of the number of obstacles on query time(f=max)圖6 障礙物個(gè)數(shù)對(duì)查詢時(shí)間的影響（f=max）

圖7和圖8分別驗(yàn)證了聚集函數(shù)sum和max情況下查詢點(diǎn)集規(guī)模的變化對(duì)查詢時(shí)間的影響。從圖中可以看出，在其他條件不變的情況下，隨著查詢點(diǎn)數(shù)量的增加，3種算法的查詢時(shí)間都有所增加，這是由于查詢點(diǎn)的增加，導(dǎo)致了障礙聚集距離的計(jì)算量增大，數(shù)據(jù)點(diǎn)要分別計(jì)算到各個(gè)查詢點(diǎn)的障礙聚集距離。本文POkANN算法在查詢點(diǎn)集處理階段需要計(jì)算查詢點(diǎn)集的最小覆蓋圓，需要消耗一部分的查詢時(shí)間，因此在查詢點(diǎn)較少時(shí)，查詢時(shí)間多于POANN*算法，但隨著查詢點(diǎn)數(shù)量的增加，其優(yōu)勢(shì)逐漸顯現(xiàn)出來(lái)，在過(guò)濾階段，通過(guò)剪枝策略將不可能成為結(jié)果的數(shù)據(jù)點(diǎn)剪枝，因此會(huì)有效地減少障礙聚集距離的計(jì)算量。

Fig.7 Effect of query data set size on query time(f=sum)圖7 查詢點(diǎn)集規(guī)模對(duì)查詢時(shí)間的影響（f=sum）

Fig.8 Effect of query data set size on query time(f=max)圖8 查詢點(diǎn)集規(guī)模對(duì)查詢時(shí)間的影響（f=max）

6 結(jié)束語(yǔ)

本文提出了基于不確定Voronoi圖的概率障礙k聚集最近鄰查詢算法（POkANN）。結(jié)合聚集最近鄰查詢的特點(diǎn)，本文算法分為3個(gè)階段：首先通過(guò)求解最小覆蓋圓處理查詢點(diǎn)集；再通過(guò)不同的剪枝策略處理相應(yīng)聚集函數(shù)下的數(shù)據(jù)點(diǎn)集，得到候選集合；最后對(duì)候選集合中的數(shù)據(jù)進(jìn)行精煉，并與給定閾值進(jìn)行比較，返回結(jié)果集。通過(guò)實(shí)驗(yàn)進(jìn)行驗(yàn)證，本文算法具有較好的性能。未來(lái)的研究重點(diǎn)主要集中在以下兩點(diǎn)：

（1）存在級(jí)不確定數(shù)據(jù)k聚集最近鄰查詢問(wèn)題；（2）不確定數(shù)據(jù)的可視聚集最近鄰查詢問(wèn)題。

[1]Ling Ping,Rong Xiangsheng,Dong Yongquan.Clusteringbased nearest neighbor searching[J].Journal of Computers,2013,8(8):2085-2092.

[2]Kim H I,Chang J W.k-nearest neighbor query processing algorithms for a query region in road networks[J].Journal of Computer Science and Technology,2013,28(4):585-596.

[3]Papadias D,Shen Qiongmao,Tao Yufei,et al.Group nearest neighbor queries[C]//Proceedings of the 20th International Conference on Data Engineering,Boston,Mar 30-Apr 2,2004.Washington:IEEE Computer Society,2004:301-312.

[4]Yang Zexue,Hao Zhongxiao.Group obstacle nearest neighbor query in spatial database[J].Journal of Computer Research and Development,2013,50(11):2455-2462.

[5]Gu Yu,Yu Ge,Yu Xiaonan.Efficient method forknearest neighbor searching in obstructed spatial databases[J].Journal of Information Science&Engineering,2014,30(5):1569-1583.

[6]Yu Xiaonan,Gu Yu,Zhang Tiancheng,et al.A method forknearest-neighbor queries obstructed spaces[J].Chinese Journal of Computers,2011,34(10):1917-1925.

[7]Safar M,Ibrahimi D,Taniar D.Voronoi-based reverse nearest neighbor query processing on spatial networks[J].Multimedia Systems,2009,15(5):295-308.

[8]Papadias D,Tao Yufei,Mouratidis K,et al.Aggregate nearest neighbor queries in spatial databases[J].ACM Transactions on Database Systems,2005,30(2):529-576.

[9]Nutanong S,Tanin E,Zhang Rui.Incremental evaluation of visible nearest neighbor queries[J].IEEE Transactions on Knowledge and Data Engineering,2010,22(5):665-681.

[10]Liu Wenyuan,Du Ying,Chen Zijun.Nearest neighbor queries with range constrained on uncertain data[J].Journal of Chinese Computer Systems,2012,33(6):1189-1194.

[11]Lian Xiang,Chen Lei.Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data[J].The VLDB Journal,2009,18(3):787-808.

[12]Lian Xiang,Chen Lei.Probabilistic group nearest neighbor queries in uncertain databases[J].IEEE Transactions on Knowledge and Data Engineering,2008,20(6):809-824.

[13]Zhou Aoying,Jin Cheqing,Wang Guoren,et al.A survey on the management of uncertain data[J].Chinese Journal of Computers,2009,32(1):1-16.

[14]Chen Wen.K-aggregate nearest neighbor query method of moving objects in road networks[J].International Journal of Database Theory andApplication,2016,9(4):151-160.

[15]Li Hongga,Lu Hua,Huang Bo,et al.Two ellipse-based pruning methods for group nearest neighbor queries[C]//Proceedings of the 13th International Workshop on Geographic Information System,Bremen,Nov 4-5,2005.New York:ACM,2005:192-199.

[16]Luo Yanmin,Chen Hanxiong,Furuse K,et al.Efficient mthods in finding aggregate nearest neighbor by projectionbased filtering[C]//LNCS 4707:Proceedings of the 2007 International Conference on Computational Science and Its Applications,Kuala Lumpur,Aug 26-29,2007.Berlin,Heidelberg:Springer,2007:821-833.

[17]Lian Xiang,Chen Lei.Probabilistic group nearest neighbor queries in uncertain databases[J].IEEE Transactions on Knowledge and Data Engineering,2008,20(6):809-824.

[18]Yiu M L,Mamoulis N,Dai Xiangyuan,et al.Efficient evaluation of probabilistic advanced spatial queries on existentially uncertain data[J].IEEE Transactions on Knowledge and Data Engineering,2009,21(1):108-122.

[19]Sun Dongpu,Hao Xiaohong,Gao Shuang,et al.Probabilistic group nearest neighbor queries based on uncertain Voronoi diagram[J].Journal of Beijing University of Agriculture,2013,28(4):73-75.

[20]Chen Mo,Jia Zixi,Gu Yu,et al.Group nearest neighbor queries over existentially uncertain data[J].Journal of Chinese Computer Systems,2012,33(4):684-687.

[21]Chen R,Xie Xike,Yiu M L,et al.UV-diagram:a Voronoi diagram for uncertain data[C]//Proceedings of the 26th International Conference on Data Engineering,Long Beach,Mar 1-6,2010.Washington:IEEE Computer Society,2010:796-807.

[22]Zhang Liping,Liu Lei,Li Song.Group reverseknearest neighbor query based on voronoi diagram in spatial databases[J].Journal of Frontiers of Computer Science and Technology,2016,10(10):1365-1375.

附中文參考文獻(xiàn)：

[4]楊澤雪,郝忠孝.空間數(shù)據(jù)庫(kù)中的組障礙最近鄰查詢研究[J].計(jì)算機(jī)研究與發(fā)展,2013,50(11):2455-2462.

[6]于曉楠,谷峪,張?zhí)斐?等.一種障礙空間中的反k最近鄰查詢方法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(10):1917-1925.

[10]劉文遠(yuǎn),杜穎,陳子軍.不確定數(shù)據(jù)上范圍受限的最近鄰查詢算法[J].小型微型計(jì)算機(jī)系統(tǒng),2012,33(6):1189-1194.

[13]周傲英,金澈清,王國(guó)仁,等.不確定性數(shù)據(jù)管理技術(shù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào),2009,32(1):1-16.

[19]孫冬璞,郝曉紅,高爽,等.基于不確定Voronoi圖的概率組最近鄰查詢[J].北京農(nóng)學(xué)院學(xué)報(bào),2013,28(4):73-75.

[20]陳默,賈子熙,谷峪,等.面向存在不確定對(duì)象的組最近鄰查詢方法[J].小型微型計(jì)算機(jī)系統(tǒng),2012,33(4):684-687.

[22]張麗平,劉蕾,李松,等.空間數(shù)據(jù)庫(kù)中基于Voronoi圖的組反k最近鄰查詢[J].計(jì)算機(jī)科學(xué)與探索,2016,10(10):1365-1375.