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

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

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

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

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

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

1　引言

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

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

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

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

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

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

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

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

（1）1級(jí)鄰接生成點(diǎn)

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

（2）k(k≥2)級(jí)鄰接生成點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定理5q的RkNN只在q的最近鄰的前k級(jí)鄰接生成點(diǎn)中。

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

如圖1所示，不同類型的虛線連接起來的數(shù)據(jù)點(diǎn)對(duì)象分別是q的1級(jí)、2級(jí)、3級(jí)、4級(jí)鄰接生成點(diǎn)，設(shè)p1、p2、p3、p4分別是q的1級(jí)、2級(jí)、3級(jí)、4級(jí)鄰接生成點(diǎn)中的一點(diǎn)。當(dāng)k為3時(shí)，由定理3可知，p4的第3個(gè)最近鄰在p4的前3級(jí)鄰接生成點(diǎn)中，而p是p4的第4級(jí)鄰接生成點(diǎn)，因此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ù)點(diǎn)集算法的主要思想為：根據(jù)定理5，將q的最近鄰前k級(jí)鄰接生成點(diǎn)放入候選集合Sc中，高于k級(jí)的鄰接生成點(diǎn)不可能是q的反k最近鄰，因此被剪枝。這一過程中首先生成Voronoi圖，判斷q落在Voronoi圖中的具體位置。然后根據(jù)q所在Voronoi圖中的具體位置分3種情況確定候選集合Sc的范圍：第一種情況是q在VP(p)內(nèi)部，那么Sc就是p的前k級(jí)鄰接生成點(diǎn)的集合；第二種情況是q在VP(p1)和VP(p2)公共棱上，則Sc就是 p1和p2的前k級(jí)鄰接生成點(diǎn)集合的并集；第三種情況是q在VP(p1)、VP(p2)、VP(p3)公共頂點(diǎn)上，那么Sc就是p1、p2、p3的前k級(jí)鄰接生成點(diǎn)集合的并集。基于以上討論，進(jìn)一步給出約減數(shù)據(jù)點(diǎn)集算法，如算法2所示。

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

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

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

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

3.3剪枝過程

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

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

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

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

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

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

證明 設(shè)p為候選集合中的一點(diǎn)(p∈Sc)，pi為p的1級(jí)鄰接生成點(diǎn)其中之一(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級(jí)鄰接生成點(diǎn)均被剪枝，則p被剪枝。

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

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

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

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

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

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

3.4精煉過程

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

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

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

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

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

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

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

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

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

（1）計(jì)算一組查詢對(duì)象中每個(gè)查詢點(diǎn)的反k最近鄰查詢結(jié)果；

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

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

Fig.3　Effects of k on query time圖3　k值對(duì)查詢時(shí)間的影響

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

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

Fig.4　Effects ofQon query time圖4　查詢點(diǎn)數(shù)量對(duì)查詢時(shí)間的影響

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

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

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

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

5　結(jié)束語

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

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

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

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

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

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

[14]孫冬璞,郝忠孝.基于Voronoi圖的組最近鄰查詢[J].計(jì)算機(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)域?yàn)閿?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)域?yàn)閿?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)域?yàn)閿?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)域?yàn)閿?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ù)研究項(xiàng)目).

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.