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

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

哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080

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

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

哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080

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

1　引言

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

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

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

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

2　基礎定義與定理

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

定義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圖的結構及定義可得出以下基本性質。

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

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

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

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

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

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

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

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

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

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

3.1查詢點集的優化

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

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

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

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

（可終止性）該算法中只有一個while循環，當不滿足條件時，while循環語句可以自行結束，故Process_Q算法是可終止的。

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

3.2約減數據點集

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

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

證明 由定理3可知，q是Voronoi多邊形VP(pi)內任意一點，設q的最近鄰為p，則對q的第k+1個最近鄰qk+1有qk+1∈AG1(p)?AG2(p)?…?AGk(p)(k為整數，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級的鄰接生成點。根據定理3，pj的kNN不包括p，也就是q的RkNN不包括pj。綜上所述，q的RkNN只在q的最近鄰的前k級鄰接生成點中。□

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

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

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

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

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

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

（時間復雜度分析）該算法生成Voronoi圖的時間復雜度為O(nlgn)。for循環的執行過程為k次，3個并列for循環一共執行3k次，k遠小于n，故算法2的總時間復雜度是O(nlgn)。□

3.3剪枝過程

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

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

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

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

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

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

證明 設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，則根據定理7，p被剪枝。□

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

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

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

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

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

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

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

3.4精煉過程

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

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

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

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

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

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

4　實驗與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

5　結束語

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

附中文參考文獻：

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

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

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

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

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

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

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

[19]郝忠孝.空間數據庫理論基礎[M].北京:科學出版社,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—），女，遼寧鐵嶺人，碩士，哈爾濱理工大學副教授、研究生導師，主要研究領域為數據庫理論及應用，數據挖掘，數據查詢。

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—），女，黑龍江哈爾濱人，哈爾濱理工大學碩士研究生，主要研究領域為數據挖掘，數據查詢。

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—），男，江蘇沛縣人，博士，哈爾濱理工大學副教授、研究生導師，主要研究領域為數據庫理論及應用，數據挖掘，數據查詢。

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—），女，黑龍江哈爾濱人，哈爾濱理工大學碩士研究生，主要研究領域為數據挖掘，數據查詢。

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(國家自然科學基金);the Natural Science Foundation of Heilongjiang Province under Grant No.F201302(黑龍江省自然科學基金);the Science and Technology Research Project of Heilongjiang Education Department under Grant Nos.12541128,12531z004(黑龍江省教育廳科學技術研究項目).

CNKI網絡優先出版: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.