空間數(shù)據(jù)庫中基于Voronoi圖的組反k最近鄰查詢*

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

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

空間數(shù)據(jù)庫中基于Voronoi圖的組反k最近鄰查詢*

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

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

為了改進現(xiàn)有的組反k最近鄰查詢算法的查詢速度與準(zhǔn)確度，提出了一種基于Voronoi圖的組反k最近鄰查詢方法（group reverse k nearest neighbor guery method based on Voronoi diagram，V_GRkNN）。該方法獲得的結(jié)果集是將這組查詢點中任意一點作為kNN的數(shù)據(jù)點集合，在實際應(yīng)用中可以用來評估一組查詢對象的影響力。該方法的特點是首先對查詢點集Q進行優(yōu)化處理，降低查詢點數(shù)量對查詢效率的負(fù)面影響；接著對數(shù)據(jù)點集P進行約減，縮小查詢搜索范圍；然后根據(jù)基于Voronoi圖的剪枝策略對候選集進行過濾；最后經(jīng)過精煉獲得GRkNN查詢的結(jié)果集。該方法在數(shù)據(jù)集處理階段很大程度上提高了查詢速度，在過濾、精煉階段利用Voronoi圖的特性提高了查詢的準(zhǔn)確性。理論研究和實驗表明，所提方法的效率明顯優(yōu)于可選的已有方法。關(guān)鍵詞：Voronoi圖；反k最近鄰；組反k最近鄰；索引結(jié)構(gòu)

1　引言

隨著基于位置服務(wù)技術(shù)的廣泛應(yīng)用，最近鄰（nearest neighbor，NN）[1]查詢成為空間數(shù)據(jù)庫查詢中的熱點問題。近年來，最近鄰查詢的研究進一步拓展到針對受限區(qū)域內(nèi)的最近鄰查詢[2]、反向最近鄰查詢[3]、組最近鄰查詢[4]、可視最近鄰查詢[5-6]、連續(xù)可視反向最近鄰查詢[7]、不確定數(shù)據(jù)集中的k最近鄰查詢[8]、強鄰近對查詢[9]、雙色數(shù)據(jù)集上的反向最近鄰查詢[10]、不確定移動對象的查詢[11]等方面，所取得的成果解決了最近鄰查詢領(lǐng)域的一系列重要問題。

k最近鄰（k nearest neighbor，kNN）查詢是空間數(shù)據(jù)庫中的最重要查詢之一。反k最近鄰（reverse k nearest neighbor，RkNN）[12]查詢是k最近鄰查詢的一個重要變體，獲得將查詢對象作為k最近鄰的數(shù)據(jù)對象集合。RkNN查詢一般用來評估查詢對象的影響力，從而反映查詢點對哪些空間數(shù)據(jù)點影響較大。由于此類查詢可以支持高級的分析和預(yù)測應(yīng)用，在實際應(yīng)用中已經(jīng)變得越來越重要。例如，在一家商場的選址工作中，需要評估該商場對附近哪些人群有影響力，該商場所吸引的顧客群就是RkNN查詢所要找的影響集。根據(jù)實際需求，有時需要對一個商業(yè)區(qū)進行影響力評估，也即查詢一組查詢對象的RkNN結(jié)果，因此文獻(xiàn)[13]提出了組反k最近鄰（group reverse k nearest neighbor，GRkNN）查詢。GRkNN查詢在空間數(shù)據(jù)庫中有著重要的實際應(yīng)用意義。

對于組最近鄰（group nearest neighbor，GNN）查詢，文獻(xiàn)[4]給出了3種算法：MQM（multiple query method）、SPM（single point method）和MBM（minimum bounding method）。其中MQM利用閾值算法的思想，增量計算查詢點集Q中每個點的NN，并在這些NN中找到最終結(jié)果。該方法對每個點進行處理，查詢點的搜索區(qū)域有很大重疊性，效率較低。SPM首先計算Q的質(zhì)心q，然后通過遍歷R-樹找到結(jié)果，利用q進行剪枝。該方法將查詢點集用一個代表點q表示，可以避免許多冗余操作，化繁為簡，較快地查詢到結(jié)果，但是只適合查詢點較聚集的情況。MBM也是通過遍歷R-樹找到結(jié)果，但利用Q的最小外包矩形（minimum bounding rectangle，MBR）進行剪枝。隨著數(shù)據(jù)集增大，該算法動態(tài)更新的時間復(fù)雜度較高。孫冬璞等人提出基于VTree索引的組最近鄰查詢的VGNN算法[14]。Li等人提出基于Q中兩種最遠(yuǎn)點構(gòu)成的橢圓及其MBR進行剪枝的GNN方法[15]。對于RkNN查詢，Stanoi等人提出了60度剪枝法，將空間劃分成6等份，然后在每個區(qū)域中，對查詢點q的第k個最近鄰以外的區(qū)域進行剪枝，未被剪枝的數(shù)據(jù)點就是RkNN查詢的候選點[16]。Tao等人提出TPL剪枝法，該方法比60度剪枝法具有更強的剪枝能力[17]。Wu等人在TPL剪枝方法的基礎(chǔ)上提出了INCH（intersections? convex hull）空間縮減法[18]。宋曉宇等人提出了組反k最近鄰查詢[13]，通過計算查詢對象的最小覆蓋圓，將圓中的對象作為一個整體來計算該組查詢點RkNN的搜索區(qū)域。該算法在查詢效率方面有待提高。

為了更有效地解決組反k最近鄰查詢問題，本文提出了一種高效的基于Voronoi圖[19]的組反k最近鄰查詢方法（group reverse k nearest neighbor query method based on Voronoi diagram，V_GRkNN）。該方法獲得的結(jié)果集是將這組查詢點中任意一點作為kNN的數(shù)據(jù)點集合，在實際應(yīng)用中可以用來評估一組查詢對象的影響力。該方法包括4個過程：優(yōu)化查詢點集，約減數(shù)據(jù)點集，剪枝過程，精煉過程。首先快速獲得查詢點集Q的質(zhì)心q，用質(zhì)心q近似地代表查詢點集整體即可有效地避免搜索區(qū)域頻繁重疊的情況，從而提高了查詢效率。然后對數(shù)據(jù)點集進行約減，得到初步的候選集合，再利用剪枝策略對候選集合中的點進行剪枝。最后利用公式進行排錯處理，得到精確的結(jié)果集。利用Voronoi圖的鄰接特性可以在約減數(shù)據(jù)點集階段和過濾階段有效地過濾掉大量的非候選者，快速地縮小查詢范圍，提高整個算法的查詢效率?；谝陨戏治?，本文提出的基于Voronoi圖的組反k最近鄰查詢方法在數(shù)據(jù)集處理階段很大程度上提高了查詢速度，在過濾、精煉階段利用Voronoi圖的特性提高了查詢的準(zhǔn)確性。

2　基礎(chǔ)定義與定理

Voronoi圖是組反k最近鄰查詢所使用的重要數(shù)學(xué)工具，首先給出Voronoi圖的基本定義及性質(zhì)。

定義1（Voronoi圖[19]）給定一組生成點P={p1, p2,…,pn}?R2，其中2

定義2（Voronoi圖的k級鄰接生成點[19]）給定一組生成點P={p1,p2,…,pn}?R2生成的Voronoi圖中，其中2

（1）1級鄰接生成點

AG1(pi)={pj|VP(pi)和VP(pj)有公共邊}

（2）k(k≥2)級鄰接生成點

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

由Voronoi圖的結(jié)構(gòu)及定義可得出以下基本性質(zhì)。

性質(zhì)1（最近鄰近特性[19]）生成點pi的最近鄰在pi的鄰接生成點之中。

性質(zhì)2（局域動態(tài)特性[19]）每個Voronoi棱由2個Voronoi多邊形所共享，而每個Voronoi多邊形的棱的平均數(shù)目最多是6，因此每個生成點最多有6個鄰接的生成點。

下面給出3個由Voronoi圖的基本性質(zhì)得出的定理，這些定理為界定組反k最近鄰查詢的查詢范圍提供了理論依據(jù)。

定理1[19]點q為Voronoi單元VP(pi)內(nèi)任一點，pk+1∈AGk+1(pi)，那么必存在一點 pk∈AGk(pi)使得dist (q,pk)≤dist(q,pk+1)。

定理2[19]對于Voronoi多邊形VP(pi)內(nèi)任一點q，q到pi的k級鄰接生成點的最小距離小于到任何pi的k+1級鄰接生成點的距離（k為整數(shù)，k≥1）。

定理3[19]對于Voronoi多邊形VP(pi)內(nèi)任一點q，q的第 k+1個最近鄰qk+1，有qk+1∈AG1(p)?AG2(p)?…?AGk(p)（k為整數(shù)，k≥1），即q的第k+1個最近鄰在q的最近鄰前k級鄰接生成點中。

下面給出k最近鄰查詢以及組反k最近鄰查詢的形式化定義。

定義3（k最近鄰查詢[8]）給定數(shù)據(jù)集 P={p1, p2,…,pn}和查詢點q，當(dāng)且僅當(dāng)一個對象 p∈P滿足{pkth∈P|dist(q,p)≤dist(q,pkth)

定義4（組反k最近鄰查詢[13]）給定一組查詢點集Q={q1,q2,…,qn}和一個數(shù)據(jù)點集P={p1,p2,…,pm}，當(dāng)一個對象p∈P在P上的kNN結(jié)果包括Q中的任意一個時，p就是GRkNN(Q,P,k)的一個結(jié)果，具體定義形式為：GRkNN(Q,P,k)={?q∈Q,?p∈P|q∈kNN(p,k,P)}。

3　基于Voronoi圖的組反k最近鄰查詢

3.1查詢點集的優(yōu)化

為了快速地對一組查詢點進行組反k最近鄰查詢，首先需要對這組查詢點集進行優(yōu)化處理。在這一過程中，通過計算獲得查詢點集Q的質(zhì)心q(x,y)，并用質(zhì)心q近似地代表查詢點集整體。這里，查詢點集是一組鄰近的查詢對象，因此用質(zhì)心q可以近似地代表查詢點集，這樣就可以避免搜索區(qū)域頻繁重疊的情況，從而有效地提高查詢效率。

基于以上討論，進一步給出查詢點集的優(yōu)化算法，如算法1所示。

定理4算法Process_Q(Q,μ,ξ)是正確的、可終止的，其時間復(fù)雜度為O(n)。

證明（正確性）Process_Q算法中while語句滿足條件時不斷地調(diào)用兩個迭代公式，當(dāng)dist(q,Q)收斂到最小值ξ時，while循環(huán)結(jié)束，此時得到的坐標(biāo)就是所求的質(zhì)心q的坐標(biāo)。故該算法能正確地求出查詢點集Q的質(zhì)心q(x,y)。

（可終止性）該算法中只有一個while循環(huán)，當(dāng)不滿足條件時，while循環(huán)語句可以自行結(jié)束，故Process_Q算法是可終止的。

（時間復(fù)雜度分析）該算法過程中只有一個while循環(huán)，因此該算法的時間復(fù)雜度和while循環(huán)的時間復(fù)雜度是同等級的。設(shè)查詢點集中的查詢點數(shù)目為n，則while循環(huán)的最壞時間復(fù)雜度為O(n)。因此Process_Q算法的時間復(fù)雜度為O(n)。□

3.2約減數(shù)據(jù)點集

在約減數(shù)據(jù)點集這一過程中，基于Voronoi圖的定理1、2、3給出定理5，根據(jù)定理5約減掉不可能成為候選者的數(shù)據(jù)點，獲得初步的候選集。這一過程有效地縮減了數(shù)據(jù)點的數(shù)量，也就是縮小了查詢范圍，進而提高了查詢速度。

定理5q的RkNN只在q的最近鄰的前k級鄰接生成點中。

證明 由定理3可知，q是Voronoi多邊形VP(pi)內(nèi)任意一點，設(shè)q的最近鄰為p，則對q的第k+1個最近鄰qk+1有qk+1∈AG1(p)?AG2(p)?…?AGk(p)(k為整數(shù)，k≥1），即q的第k+1個最近鄰在p的前k級鄰接生成點中。則顯然有qk∈AG1(p)?AG2(p)?…?AGk-1(p)，即q的第k個最近鄰在 p的前k-1級鄰接生成點中。故p的第k級及高于k級的鄰接生成點中不可能存在q的kNN。若pj∈AGn(p)（n>k），即pj是p的高于k級的鄰接生成點。反過來同理，p是pj的高于k級的鄰接生成點。根據(jù)定理3，pj的kNN不包括p，也就是q的RkNN不包括pj。綜上所述，q的RkNN只在q的最近鄰的前k級鄰接生成點中?！?/p>

如圖1所示，不同類型的虛線連接起來的數(shù)據(jù)點對象分別是q的1級、2級、3級、4級鄰接生成點，設(shè)p1、p2、p3、p4分別是q的1級、2級、3級、4級鄰接生成點中的一點。當(dāng)k為3時，由定理3可知，p4的第3個最近鄰在p4的前3級鄰接生成點中，而p是p4的第4級鄰接生成點，因此p4的3NN不包括p。由于q位于VP(p)內(nèi)，從而q也不是 p4的3NN，即q的反3NN不可能是p4。同理，q的反3NN更不可能是p5,p6,…,pn。

Fig.1　Example of theorem 5圖1　基于定理5的示例

本節(jié)提出的約減數(shù)據(jù)點集算法的主要思想為：根據(jù)定理5，將q的最近鄰前k級鄰接生成點放入候選集合Sc中，高于k級的鄰接生成點不可能是q的反k最近鄰，因此被剪枝。這一過程中首先生成Voronoi圖，判斷q落在Voronoi圖中的具體位置。然后根據(jù)q所在Voronoi圖中的具體位置分3種情況確定候選集合Sc的范圍：第一種情況是q在VP(p)內(nèi)部，那么Sc就是p的前k級鄰接生成點的集合；第二種情況是q在VP(p1)和VP(p2)公共棱上，則Sc就是 p1和p2的前k級鄰接生成點集合的并集；第三種情況是q在VP(p1)、VP(p2)、VP(p3)公共頂點上，那么Sc就是p1、p2、p3的前k級鄰接生成點集合的并集?；谝陨嫌懻?，進一步給出約減數(shù)據(jù)點集算法，如算法2所示。

定理6算法Reduction_P(Q,P,k)能正確地求出候選集合Sc，是可終止的，其時間復(fù)雜度為O(nlgn)。

證明（正確性）該算法首先生成Voronoi圖并判斷q落在Voronoi圖中的具體位置。如果q在VP(p)內(nèi)部，那么首先獲得q的最近鄰p，再將p的一級鄰接生成點集加入Sc中，最后根據(jù)定理5，for循環(huán)執(zhí)行k次將p的前k級鄰接生成點集加入Sc中。如果q在VP(p1)和VP(p2)公共邊上，那么q的最近鄰就變成了{(lán)p1,p2}，然后同樣重復(fù)k次for循環(huán)將{p1,p2}的前k級鄰接生成點集的并集加入Sc中。如果q在VP(p1)、VP(p2)、VP(p3)公共頂點上，那么q的最近鄰就變成了{(lán)p1,p2,p3}，然后根據(jù)定理5同樣重復(fù)k次for循環(huán)將{p1,p2,p3}的前k級鄰接生成點集的并集加入Sc中，故算法是正確的。

（可終止性）該算法首先生成Voronoi圖，因為數(shù)據(jù)點集中的數(shù)據(jù)點的個數(shù)是一定的，所以生成Voronoi圖這一過程是可終止的。然后算法中的3個for循環(huán)都是可終止的，故該算法是可終止的。

（時間復(fù)雜度分析）該算法生成Voronoi圖的時間復(fù)雜度為O(nlgn)。for循環(huán)的執(zhí)行過程為k次，3個并列for循環(huán)一共執(zhí)行3k次，k遠(yuǎn)小于n，故算法2的總時間復(fù)雜度是O(nlgn)?！?/p>

3.3剪枝過程

這一過程的主要工作是對候選集Sc進行過濾，剪枝掉大量的非候選者，獲取更精確的候選集合。首先利用Voronoi圖的鄰接特性給出3個高效的剪枝策略，再根據(jù)剪枝策略對候選集Sc中的數(shù)據(jù)點進行判斷，若滿足條件則被剪枝，Sc中剩下的未被剪枝的數(shù)據(jù)點構(gòu)成更精確的候選集。下面以定理形式給出3個剪枝策略及相關(guān)證明。

定理7令 p∈AGn(NN(q))，即數(shù)據(jù)點 p在q的最近鄰的第n級鄰接生成點中。令p到q的路徑上經(jīng)過的數(shù)據(jù)點個數(shù)不得大于n。將p與查詢點q之間的若干路徑上的數(shù)據(jù)點總個數(shù)記作sumcount(p,q)，如果sumcount(p,q)≥k，則數(shù)據(jù)點p被剪枝。

證明 設(shè)p到查詢點q的路徑上經(jīng)過的數(shù)據(jù)點為pi，當(dāng)k為1時，顯然dist(p,pi)小于dist(p,q)，即p的最近鄰可能是pi而一定不是q。當(dāng)k大于1時，如果pi的個數(shù)大于或等于k個，即sumcount(p,q)≥k，那么p的kNN可能包括pi中的1到k個，但是一定不包括q?！?/p>

如圖2所示，數(shù)據(jù)點p7在查詢點q的最近鄰的第3級鄰接生成點中。滿足p7到q的路徑上經(jīng)過的數(shù)據(jù)點個數(shù)不大于3的路徑一共3條，分別是{q,p1,p3, p7}、{q,p2,p4,p7}、{q,p2,p5,p6,p7}。 p7與查詢點q之間的3條路徑上的數(shù)據(jù)點總數(shù)sumcount(p,q)為6，那么當(dāng)k等于6時，p7的6NN有可能包括{p1,p2,p3,p4,p5, p6}，而一定不包括q。當(dāng)k小于6時，p7的kNN可能包含{p1,p2,p3,p4,p5,p6}中的1個到k個，而一定不包括q。綜上所述，當(dāng)sumcount(p,q)大于或等于k時，p的kNN查詢結(jié)果不包括q，即q的RkNN查詢結(jié)果一定不是p，故數(shù)據(jù)點p被剪枝。

Fig.2　Example of theorem 7圖2　基于定理7的示例

定理8若 p∈AGn(NN(q))被剪枝，那么 p的1級鄰接生成點 pi∈Sc滿足 pi∈AGn+1(NN(q))條件的也被剪枝。

證明 設(shè)p為候選集合中的一點(p∈Sc)，pi為p的1級鄰接生成點其中之一(pi∈AG1(p))，且pi在候選集中(pi∈Sc)。如果p被剪枝，即sumcount(p,q)≥k，那么sumcount(pi,q)≥k+1。由于sumcount(pi,q)大于k，則根據(jù)定理7，p被剪枝?！?/p>

定理9若 p∈Sc且它的1級鄰接生成點均被剪枝，則p被剪枝。

證明 設(shè)p為候選集合中的一點(p∈Sc)，a為p的1級鄰接生成點其中之一(a∈AG1(p))，且a是p到q路徑上經(jīng)過的點。若p的1級鄰接生成點均被剪枝，顯然a也被剪枝，即sumcount(a,q)≥k，那么一定有sumcount(p,q)≥k+1。由于sumcount(p,q)大于k，則根據(jù)定理7，p被剪枝?！?/p>

本節(jié)提出的剪枝算法的主要思想為：通過定理7、定理8、定理9這3個剪枝策略，獲得剪枝后更精確的候選集Sc′。在上一過程的基礎(chǔ)上，通過算法1和算法2求得查詢點集Q的質(zhì)心q以及初步的候選集合Sc，接下來根據(jù)定理7判斷Sc中的數(shù)據(jù)點p是否應(yīng)該被剪枝，若p∈AGn(NN(q))被剪枝，再根據(jù)定理8，對p的1級鄰接生成點pi∈Sc滿足pi∈AGn+1(NN(q))條件的也被剪枝。最后根據(jù)定理9對Sc中剩下的數(shù)據(jù)點進行判斷，若p∈Sc且它的1級鄰接生成點均被剪枝，則p被剪枝。通過對候選集Sc進行過濾，剪掉不可能成為候選者的數(shù)據(jù)點，獲得范圍更小的候選集?；谝陨嫌懻?，給出剪枝算法如算法3所示。

定理10算法Filter(P,Q,k)能正確地剪枝不可能成為結(jié)果的數(shù)據(jù)點，求出剪枝后更精確的候選集合Sc′，是可終止的，其時間復(fù)雜度為O(n)，其中n為數(shù)據(jù)集中數(shù)據(jù)點的個數(shù)。

證明（正確性）該算法的輸入是通過算法1獲得的查詢點集的質(zhì)心q，以及通過算法2獲得的候選集合Sc。算法對候選集合中的每一個數(shù)據(jù)點p進行判斷，求出它到q的若干條路徑上經(jīng)過的數(shù)據(jù)點總和，若sumcount不小于k，則根據(jù)定理7對p進行剪枝。再根據(jù)定理8對滿足條件的pi剪枝。最后根據(jù)定理9對候選集中剩下的數(shù)據(jù)點進行判斷，符合條件的p被剪枝。由于已經(jīng)證明出定理7、定理8、定理9的正確性，故該算法是正確的。

（可終止性）該算法中有兩個嵌套for循環(huán)。因為Sc中的候選點數(shù)目是有限的，所以第一個for循環(huán)可以自行終止。第二個for循環(huán)的執(zhí)行過程為6次，也是可終止的，故該算法是可終止的。

（時間復(fù)雜度分析）Filter(P,Q,k)算法中有兩個嵌套的for循環(huán)。第一個for循環(huán)執(zhí)行的次數(shù)取決于Sc中的候選點數(shù)目，在最壞情況下Sc中的候選點數(shù)目為n（n為數(shù)據(jù)集中數(shù)據(jù)點的數(shù)目），因此第一個for循環(huán)在最壞情況下執(zhí)行n次。第二個for循環(huán)的執(zhí)行過程為6次，故總共執(zhí)行6n次。從而該算法的時間復(fù)雜度在最壞情況下是O(n)。□

3.4精煉過程

精煉過程的主要工作是對剪枝后的候選集Sc′進行排錯處理，根據(jù)反kNN的定義對候選集Sc′中的數(shù)據(jù)點p進行判斷，若滿足定義的條件，則p為正確的結(jié)果，若不滿足條件，則被剪枝。最后得到正確的組反k最近鄰的結(jié)果集。

本節(jié)提出的精煉算法的主要思想為：由反kNN的定義可知，如果數(shù)據(jù)點p滿足dist(q,p)>dist(p,pkth)，則p不可能是q的反k最近鄰。根據(jù)這一條件對候選集中的數(shù)據(jù)點逐一進行判斷。具體過程為：首先通過調(diào)用算法1、算法2、算法3分別求得查詢點集Q的質(zhì)心q，初始的候選集Sc以及剪枝后的候選集合Sc′。然后對候選集合Sc′中的每一個數(shù)據(jù)點p，尋找它的第k個最近鄰，記作pkth。如果p到q的距離大于 p到 pkth的距離，則說明q不可能是 p的k最近鄰，也就是p不可能是q的反k最近鄰查詢的結(jié)果，將其剪枝，最后得到精確的結(jié)果集。由以上論述可得出基于Voronoi圖的組反k最近鄰查詢算法如下。

定理11算法V_GRkNN(Q,P,k)是正確的、可終止的，其時間復(fù)雜度為O(nlgn)。

證明（正確性）該算法首先調(diào)用的算法1、算法2、算法3均是正確的。然后尋找p的第k個最近鄰，若候選集中的點p到q的距離大于p到pkth的距離，則說明p不可能是q的反k最近鄰查詢的結(jié)果，將其剪枝。最后得到的未被剪枝的候選集中的數(shù)據(jù)點就是組反k最近鄰查詢的結(jié)果，故該算法是正確的。

（可終止性）該算法首先調(diào)用的算法1、算法2、算法3均是可終止的。在語句5的for循環(huán)中，因為候選集中數(shù)據(jù)點的個數(shù)是有限的，所以for循環(huán)是可自行終止的。語句7中的for循環(huán)是從1循環(huán)到k，其中k是GRkNN查詢的k值，是有限的，因此該for循環(huán)也是可終止的，故該算法是可終止的。

（時間復(fù)雜度分析）該算法執(zhí)行算法1的時間復(fù)雜度為O(n)；執(zhí)行算法2的時間復(fù)雜度為O(nlgn)；執(zhí)行算法3在最壞情況下的時間復(fù)雜度為O(n)；執(zhí)行嵌套for循環(huán)的最壞時間復(fù)雜度為O(kn)，其中k是組反k最近鄰查詢的k值，故該算法的時間復(fù)雜度為O(nlgn+(k+2)n)，化簡為O(nlgn)?！?/p>

4　實驗與分析

通過實驗對本文算法V_GRkNN進行性能評估。為了驗證算法的有效性，將本文提出的基于Voronoi圖的V_GRkNN方法分別與文獻(xiàn)[13]提出的FCINCH算法以及一種基本算法進行實驗比較。把這種基本算法稱作GRkNN算法。

GRkNN算法的主要思想為：將現(xiàn)有的針對一個查詢對象的RkNN查詢算法應(yīng)用到一組查詢對象的情況中，也就是對一組對象中的每個對象成員進行RkNN查詢，所有查詢結(jié)果的并集就是GRkNN查詢的結(jié)果。具體算法步驟如下：

（1）計算一組查詢對象中每個查詢點的反k最近鄰查詢結(jié)果；

（2）求出所有查詢結(jié)果的并集，得到GRkNN查詢的結(jié)果。

實驗平臺配置如下：2.0 GHz CPU，4 GB內(nèi)存，500 GB硬盤，Windows 7操作系統(tǒng)，用Microsoft Visual Studio 2005實現(xiàn)。本文使用的數(shù)據(jù)集是Nav Tech公司提供的真實數(shù)據(jù)集，該數(shù)據(jù)集用于汽車上GPS設(shè)備的導(dǎo)航系統(tǒng)，包括洛杉磯市中心道路系統(tǒng)上的將近79 800個節(jié)點對象[20]。n表示數(shù)據(jù)點集的規(guī)模，查詢點集Q是在數(shù)據(jù)點集空間內(nèi)隨機抽出的m個點的集合。本文使用的是Voronoi圖的索引結(jié)構(gòu)VTree，VTree索引的每個節(jié)點最多包含24個索引項。實驗測試的指標(biāo)為算法的查詢時間，并取執(zhí)行100次查詢的平均值。分別測試k值、查詢點數(shù)量、數(shù)據(jù)點集大小對算法查詢時間的影響以及k值對候選者數(shù)量的影響。

Fig.3　Effects of k on query time圖3　k值對查詢時間的影響

如圖3所示，首先分析k值對查詢時間的影響。實驗采用真實數(shù)據(jù)集，規(guī)模為79 800，查詢點的數(shù)量為10。圖3給出了3個算法的查詢時間隨著k值變化的對比結(jié)果。隨著k值的不斷變大，3個算法的查詢時間均呈上升趨勢，其中GRkNN算法的上升趨勢顯著，V_GRkNN以及FCINCH算法上升趨勢比較平緩。由于GRkNN算法需要對每一個查詢點計算它的RkNN，這樣就造成了搜索區(qū)域頻繁重疊的情況，從而降低了查詢速度。FCINCH算法通過計算查詢對象的最小覆蓋圓，將圓中的對象作為一個整體來計算該組查詢點RkNN的搜索區(qū)域，有效地縮小了查詢區(qū)域，但是時間復(fù)雜度略高。而本文的V_GRkNN算法分別對查詢點集和數(shù)據(jù)點集進行了預(yù)處理，縮小了查詢范圍，同時利用Voromoi圖的特性進行高效的剪枝和精煉，故算法的時間復(fù)雜度比FCINCH算法較低一些。當(dāng)k為1時，V_GRkNN算法的CPU執(zhí)行時間比FCINCH略長，因為V_GRkNN在生成Voronoi圖過程中需要花費時間，但是隨著k的變大，該算法的優(yōu)勢明顯。由以上討論可得出，總體上V_GRkNN算法的查詢時間比FCINCH算法略短一些。

圖4給出了查詢點數(shù)量對查詢時間的影響。實驗設(shè)定k值為10，數(shù)據(jù)點集的規(guī)模設(shè)置為79 800。從圖中可以看出3個算法的查詢時間都是隨著查詢點個數(shù)的增多而逐漸增加。其中GRkNN算法的查詢時間上升趨勢明顯，因為需要對每一個查詢點計算它的RkNN，當(dāng)查詢點數(shù)量成倍數(shù)增長時，該算法所用的查詢時間也成倍數(shù)增長。而FCINCH和V_GRkNN算法的查詢時間的上升趨勢較為平緩，因為算法中都有對查詢點集的處理過程，所以當(dāng)查詢點數(shù)量成倍數(shù)增長時，對算法的性能影響不大。在優(yōu)化查詢點集階段V_GRkNN算法的時間復(fù)雜度低于FCINCH算法，因此V_GRkNN算法的性能優(yōu)于FCINCH算法。

Fig.4　Effects ofQon query time圖4　查詢點數(shù)量對查詢時間的影響

接下來分析k值對候選者數(shù)量的影響，設(shè)定實驗規(guī)模為79 800，查詢點數(shù)量為20。如圖5所示，隨著k值從1增加到20，V_GRkNN算法得到的候選者數(shù)量最少，說明V_GRkNN算法的剪枝過程更優(yōu)化。GRkNN算法的性能最低，因為它的候選集是對每一個查詢點計算其搜索區(qū)域，但是當(dāng)查詢點距離較近時，會產(chǎn)生搜索區(qū)域頻繁重疊，這樣每個查詢點的候選集合就會有很多重復(fù)。而V_GRkNN算法首先對數(shù)據(jù)點集進行約減，排除大量的非候選點，然后利用基于Voronoi圖的3個剪枝策略對候選集進行過濾，這樣便較大程度地減少了候選者的數(shù)量。綜上所述，V_GRkNN算法在剪枝階段性能優(yōu)于另外兩種算法。

Fig.5　Effects of k on candidates number圖5　k值對候選者數(shù)量的影響

Fig.6　Effects of dataset scale on query time圖6　數(shù)據(jù)點集大小對查詢時間的影響

圖6給出了數(shù)據(jù)點集規(guī)模的變大對算法查詢時間的影響。從圖中可以看出，隨著數(shù)據(jù)點集規(guī)模的變大，3個算法的查詢時間都呈上升趨勢。GRkNN算法沒有數(shù)據(jù)點集的約減和剪枝過程，因而性能最低。FCINCH算法在計算搜索區(qū)域時，因為沒有對數(shù)據(jù)點集進行約減處理，所以隨著數(shù)據(jù)點集的增大，計算過程所用時間變多。而本文的V_GRkNN算法首先對數(shù)據(jù)點集進行約減處理，利用Voronoi圖的特性可以約減掉大量的非候選點，隨著數(shù)據(jù)點集的變大，對算法性能影響不大。因此如圖6所示，V_GRkNN算法的上升趨勢比較平緩。綜上所述，V_GRkNN算法在約減數(shù)據(jù)點集方面優(yōu)于其他算法。

5　結(jié)束語

本文利用Voronoi圖的性質(zhì)和相應(yīng)的剪枝規(guī)則，提出了處理組反k最近鄰查詢的方法，解決了針對空間數(shù)據(jù)庫的組反k最近鄰查詢的問題。GRkNN查詢分為4個過程：處理查詢點集，約減數(shù)據(jù)點集，剪枝過程，精煉過程。首先求出查詢點集Q的質(zhì)心q，由于這組查詢點的鄰近性，用質(zhì)心q代表整個查詢點集；然后根據(jù)定理對數(shù)據(jù)集進行約減得到初步的候選集；再利用剪枝規(guī)則對候選集進行過濾；最后通過精煉算法去掉錯誤的候選者，獲得正確的結(jié)果集。理論研究和實驗表明，所提算法具有較好的性能。未來的研究重點主要集中在障礙空間下的組反k最近鄰查詢方面。

[1]Roussopoulos N,Kelly S,Vincent F.Nearest neighbor queries[C]//Proceedings of the 1995 ACM SIGMOD International Conference on Management of Data,San Jose,USA, May 22-25,1995.New York:ACM,1995:71-79.

[2]Zhang Liping,Zhao Jiqiao,Li Song,et al.Research on methods of construction of Voronoi diagram and nearest neighbor query in constrained regions[J].Computer Science,2014,41(9):220-224.

[3]Tao Yulei,Yiu M L,Mamoulis N.Reverse nearest neigh-bor search in metric spaces[J].IEEE Transactions on Knowledge Data Engineering,2006,18(9):1239-1252.

[4]Papadias D,Shen Qiongmao,Tao Yufei,et al.Group nearest neighbor queries[C]//Proceedings of the 20th International Conference on Data Engineering,Los Alamitos,USA,Mar 30-Apr 2,2004.Piscataway,USA:IEEE,2004:301-312.

[5]Samna N,Eqemen T,Zhang Rui.Incremental evaluation of visible nearest neighbor queries[J].IEEE Transactions on Knowledge Engineering,2010,22(4):665-681.

[6]Cao Yunjun,Zheng Baihua,Chen Cencai,et al.Visible reverse k-nearest neighbor query processing in spatial databases[J].IEEE Transactions on Knowledge Engineering, 2009,21(8):1314-1327.

[7]Yang Zexue,Hao Zhongxiao.Continuous visible reverse nearest neighbor queries in spatial databases[J].Journal of Southwest Jiaotong University,2012,47(3):451-457.

[8]Zhang Ying,Lin Xuemin,Zhu Gaoping,et al.Efficient rank based kNN query processing over uncertain data[C]//Proceedings of the 26th International Conference on Data Engineering,Long Beach,USA,Mar 1-6,2010.Piscataway,USA: IEEE,2010:28-39.

[9]Li Song,Zhang Liping,Hao Zhongxiao.Strong neighborhood pair query in dynamic dataset[J].Journal of Computer Research and Development,2015,52(3):749-759.

[10]Wang Li,Qin Xiaolin,Shi Changyue.Bichromatic reverse nearest neighbor queries in indoor space[J].Journal of Frontiers of Computer Science and Technology,2015,9(3):310-320.

[11]Li Jiajia,Wang Botao,Wang Guoren,et al.A survey of query processing techniques over uncertain mobile objects[J]. Journal of Frontiers of Computer Science and Technology, 2013,7(12):1057-1072.

[12]Wu Wei,Yang Fei,Chan Cheeyong,et al.Continuous reverse k-nearest-neighbor monitoring[C]//Proceedings of the 9th International Conference on Mobile Data Management, Beijing,Apr 27-30,2008.Piscataway,USA:IEEE,2008: 132-139.

[13]Song Xiaoyu,Yu Chengcheng,Sun Huanliang,et al.GRkNN: group reverse k-nearest-neighbor query in spatial databases [J].Chinese Journal of Computers,2010,33(12):2229-2238.

[14]Sun DongPu,Hao Zhongxiao.Group nearest neighbor queries based on Voronoi diagrams[J].Journal of Computer Research and Development,2010,47(7):1244-1251.

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

[16]Stanoi I,Agrawal D,Elabbadi A.Reverse nearest neighborqueries for dynamic databases[C]//Special Interest Group on Management of Data Workshop on Research Issues on Data Mining and Knowledge Discovery,Dallas,USA,2000:44-53.

[17]Tao Yufei,Papadias D,Lian Xiang.Reverse kNN search in arbitrary dimensionality[C]//Proceedings of the 30th International Conference on Very Large Data Bases,Toronto, Canada,Aug 31-Sep 3,2004.San Fransisco,USA:Morgan Kaufmann Publishers Inc,2004:744-755.

[18]Wu Wei,Yang Fei,Chan Cheeyong,et al.FINCH:evaluating reverse k-nearest-neighbor queries on location data[J].Proceedings of the VLDB Endowment,2008,1(1):1056-1067.

[19]Hao Zhongxiao.Spatial databases theoretical basis[M].Beijing:Science Press,2013.

[20]Kolahdouzan M,Shahabi C.Voronoi-based K nearest neighbor search for spatial network databases[C]//Proceedings of the 30th International Conference on Very Large Data Bases, Toronto,Canada,Aug 31-Sep 3,2004.San Fransisco,USA: Morgan Kaufmann Publishers Inc,2004:840-851.

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

[2]張麗平,趙紀(jì)橋,李松,等.Voronoi圖的構(gòu)建與受限區(qū)域內(nèi)的最近鄰查詢方法研究[J].計算機科學(xué),2014,41(9):220-224.

[7]楊澤雪,郝忠孝.空間數(shù)據(jù)庫中連續(xù)可視反向最近鄰查詢[J].西安交通大學(xué)學(xué)報,2012,47(3):451-457.

[9]李松,張麗平,郝忠孝.動態(tài)數(shù)據(jù)集環(huán)境下的強鄰近對查詢[J].計算機研究與發(fā)展,2015,52(3):749-759.

[10]王麗,秦小麟,施常月.室內(nèi)雙色數(shù)據(jù)集上的反向最近鄰查詢[J].計算機科學(xué)與探索,2015,9(3):310-320.

[11]李佳佳,王波濤,王國仁,等.不確定移動對象的查詢處理技術(shù)研究綜述[J].計算機科學(xué)與探索,2013,7(12):1057-1072.

[13]宋曉宇,于程程,孫煥良,等.GRkNN：空間數(shù)據(jù)庫中組反k最近鄰查詢[J].計算機學(xué)報,2010,33(12):2229-2238.

[14]孫冬璞,郝忠孝.基于Voronoi圖的組最近鄰查詢[J].計算機研究與發(fā)展,2010,47(7):1244-1251.

[19]郝忠孝.空間數(shù)據(jù)庫理論基礎(chǔ)[M].北京:科學(xué)出版社,2013.

ZHANG Liping was born in 1976.She received the M.S.degree from Harbin University of Science and Technology. Now she is an associate professor at Harbin University of Science and Technology.Her research interests include database theory and application,data mining and data query.

張麗平（1976—），女，遼寧鐵嶺人，碩士，哈爾濱理工大學(xué)副教授、研究生導(dǎo)師，主要研究領(lǐng)域為數(shù)據(jù)庫理論及應(yīng)用，數(shù)據(jù)挖掘，數(shù)據(jù)查詢。

LIU Lei was born in 1990.She is an M.S.candidate at Harbin University of Science and Technology.Her research interests include data mining and data query.

劉蕾（1990—），女，黑龍江哈爾濱人，哈爾濱理工大學(xué)碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)挖掘，數(shù)據(jù)查詢。

LI Song was born in 1977.He received the Ph.D.degree from Harbin University of Science and Technology.Now he is an associate professor at Harbin University of Science and Technology.His research interests include database theory and application,data mining and data query.

李松（1977—），男，江蘇沛縣人，博士，哈爾濱理工大學(xué)副教授、研究生導(dǎo)師，主要研究領(lǐng)域為數(shù)據(jù)庫理論及應(yīng)用，數(shù)據(jù)挖掘，數(shù)據(jù)查詢。

YU Jiaxi was born in 1991.She is an M.S.candidate at Harbin University of Science and Technology.Her research interests include data mining and data query.

于嘉希（1991—），女，黑龍江哈爾濱人，哈爾濱理工大學(xué)碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)挖掘，數(shù)據(jù)查詢。

Group Reverse k Nearest Neighbor Query Based on Voronoi Diagram in Spatial Databases?

ZHANG Liping+,LIU Lei,LI Song,YU Jiaxi
College of Computer Science and Technology,Harbin University of Science and Technology,Harbin 150080,China

E-mail:zhanglptg@163.com

To overcome the limitation of query objects in group reverse k nearest neighbor(GRkNN)query,this paper proposes the group reverse k nearest neighbor query method based on Voronoi diagram(V_GRkNN).The proposed method finds data points that take any point in the query objects set as one of their k nearest neighbors.In the practical application,V_GRkNN query can be used to evaluate the influence of a group of query objects.Firstly,the query points set Q is optimized in order to reduce the effect of the query points number on query efficiency,the data points set P is pruned to reduce the searching ranges.And then according to the pruning strategies based on Voronoi diagram,the candidate set is filtered.Finally,a refinement process is used to get the query ? s final results.The V_GRkNN method greatly improves the query speed and efficiency.Theoretical research and experiments show that the efficiency of the proposed V_GRkNN method obviously outperforms other algorithms.

Voronoi diagram;reverse k nearest neighbor;group reverse k nearest neighbor;index structure

2015-08,Accepted 2015-10.

10.3778/j.issn.1673-9418.1508004

A

TP311.13

*The National Natural Science Foundation of China under Grant No.61370084(國家自然科學(xué)基金);the Natural Science Foundation of Heilongjiang Province under Grant No.F201302(黑龍江省自然科學(xué)基金);the Science and Technology Research Project of Heilongjiang Education Department under Grant Nos.12541128,12531z004(黑龍江省教育廳科學(xué)技術(shù)研究項目).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-20,http://www.cnki.net/kcms/detail/11.5602.TP.20151020.1041.008.html

ZHANG Liping,LIU Lei,LI Song,et al.Group reverse k nearest neighbor query based on Voronoi diagram in spatial databases.Journal of Frontiers of Computer Science and Technology,2016,10(10)：1365-1375.