基于新型索引結構的反最近鄰查詢

劉潤濤 梁建創

1(哈爾濱理工大學理學院 哈爾濱 150080)2(哈爾濱理工大學信息與科學計算技術研究所 哈爾濱 150080)

隨著反最近鄰(reverse nearest neighbor, RNN)查詢[1]的概念被提出來，在日常生活中遇到的很多實際問題就能夠依據此概念得到解決，例如地理信息系統(geographical information system, GIS)、地理圍欄、決策支持以及設施定位等.而反最近鄰問題本質上就是數據集中某些點所帶來的影響集的問題，比如一家咖啡館要在某個商場開店，這就必定會對周邊的一些咖啡店或者飲品店帶來客戶上的影響，其中受影響最大的咖啡店或飲品店就是我們想要的結果，也是RNN查詢最終的目的.RNN查詢也因其廣泛的應用前景，成為一項重要的研究.

近些年來，對RNN查詢的研究已經提出了很多，但是大多數的研究是在R-樹以及其擴展的基礎上進行的，這樣也就引入了R-樹的缺點.作為空間數據庫管理系統中常用的查詢操作，RNN查詢的效率往往也與其所使用的空間數據索引結構[1-2]息息相關，對兩者的研究往往也是并行的.Korn等人[3]提出了一種RNN查詢算法，以R*-樹為基礎構造了RNN-樹(reverse nearest neighbor tree, RNN-tree)來實現查詢，但是這種方法的缺點主要在于動態情況下需要建立2個索引，而且由于存儲區域較大的重疊導致性能降低.Yang等人[4]提出了基于RDNN-樹(R-tree containing distance of nearest neighbor)的RNN查詢算法，該算法有效地避免了建立2個索引結構，提高了查詢效率.但RDNN查詢也僅僅對低維數據有效，當維數增高時，由于R*-樹的限制，其性能急劇下降.郝忠孝等人[5]提出了SRdnn-樹(SR-tree containing distance of nearest neighbor)索引結構，并給出RNN查詢算法，突破了R*-樹在高維數據空間查詢的局限性.李松等人[6]使用Voronoi圖和空間劃分區域的性質計算查詢點的反最近鄰，并與R*-樹相結合，構造了一種新的基于Voronoi圖的索引結構(Voronoi diagram-based reverse nearest neighbor query tree, VRNN-tree)，基于這種新的索引結構的RNN查詢適用于平面及復雜曲面上的數據點.王淼等人[7]提出了一種基于Delaunay圖的新型索引結構Delaunay樹用來解決反最近鄰問題，把查詢點作為Delaunay圖的一個生成點，利用Delaunay圖的生成點與其鄰接生成點之間的關系來查詢數據集中的反最近鄰.之后，Cheema等人[8]對反k最近鄰(reverseknearest neighbor query, RkNN)和反Top-k查詢進行了研究，利用基于區域修剪的算法和線性評分函數對SRTk(spatial reverse top-k)查詢進行了優化.Wang等人[9]對基于動態軌跡的反k最近鄰查詢進行了研究，提出了RkNNT(reverseknearest neighbor search over trajectories)算法來解決動態路線規劃問題.Wang等人[10]改進了傳統的基于位置查詢的反k最近鄰查詢算法，利用遞增的臨時網絡擴展樹更新道路網絡的權重變化，可以達到動態監測目標的結果.Hidayat等人[11]在影響區域的基礎上提出了影響因子的概念，同時利用新定義的修剪圓的方式去修剪空間，篩選合適的數據，從而提高RkNN查詢的效率和準確性.Guillaume等人[12]提出了一種求解RkNN查詢的近似方法，通過內在維度的特征優化剪枝操作，降低預處理成本，同時提升了在高維度時的查詢性能.Francisco等人[13]運用了分布式的思想去處理RkNN查詢，利用無共享空間云基礎架構SpatialHadoop和Location-Spark設計分布式RkNN查詢算法，提高了分布式空間數據管理系統的效率和擴展性.

R-樹的優點在于計算簡單，但是中間結點間重疊和覆蓋現象較為嚴重，為查詢操作帶來較多不必要的結點訪問，而且隨著維度的增加查詢性能也會降低.而提高查詢算法性能的方法，可以通過采用更高效的修剪規則來提高算法本身的性能，還可以通過構建更適合RNN查詢的索引結構來提升RNN查詢性能.本文針對這個問題，先定義空間物體間的4種序關系，然后利用這些序關系提出了一種新的索引結構：MBDNN-樹(index tree based on the minimum bounding square and the distance of nearest neighbor, MBDNN-tree)，這種索引結構運用了R-樹中分割數據空間的思想，將數據點集通過最近鄰距離擴展為空間物體，繼而利用其中多種序關系優化索引結構，將空間位置相近的數據盡可能地存儲在同一結點中，使得該索引結構中同層結點之間均滿足同一種序關系.運用同層結點之間滿足的序關系，給出進行RNN查詢的高效剪枝規則，再對中間結點進行較少量的簡單計算即可有效減少結點的訪問數量，從而提高查詢性能.本文利用MBDNN-樹索引結構作為存儲結構進行RNN查詢研究.

1 相關定義與定理

1.1 RNN查詢的定義

首先給出RNN查詢的定義.我們假設S是d維空間的一組數據點集，D(p,q)表示任意2點p和q之間的距離.

定義1[14].RNN查詢.假設有2維數據集S和查詢點q，RNN查詢就是找出S的子集RNNS(q)：

RNNS(q)={r∈S|?p∈S:D(q,r)≤D(r,p)}，

其中，D(q,r)是點p和點q之間的歐氏距離.

在本文中，我們采用了基于2維歐氏空間下的數據集進行論證，點與點、點與空間物體之間的距離也采用歐氏距離進行計算，對于接下來的結果可以推廣至高維空間.另外，對于接下來敘述的以2維空間數據為基礎提出的序關系，同樣可以按照其思想推廣至高維空間.

1.2 MBDNN-樹所基于的序的定義

定義2[14].在2維歐氏空間E(d)中，有1個矩形E，用其主對角線的2個頂點V和T來表示該矩形，其定義為

E=(V,T)，

其中，V=(v1,v2)，T=(t1,t2)；vi≤ti(1≤i≤2).

本文采用2種近似表示空間物體的方法：

1) 最小外包矩形(minimum bounding rectangle,MBR).以單個或數個空間物體的最小包圍矩形(邊與空間軸平行)近似表示空間物體，如圖1(a).在MBDNN-樹結構中，用MBR來構造樹的中間結點和葉子結點.

假設有n個空間物體，則每個物體對應的MBR的表示方法為

Fig.1 The two approximate expressions of space objects圖1 空間物體的2種近似表示

2) 基于最近鄰距離的最小包圍正方形(mini-mum bounding square based on nearest neighbor distance,MBSD).以自身為圓心，對應的最近鄰點之間的距離為半徑作圓，用最小包圍正方形近似表示該圓所代表的區域，如圖1(b)所示.其中該圓也稱為最小包圍圓(minimum bounding circle,MBC)(MBC可以用數據點本身和其對應的最近鄰距離表示).在MBDNN-樹索引結構中，用空間數據的MBSD來構造樹的葉子結點中包含的孩子結點.

假設有一數據集S包含n個點，每個點所對應的最近鄰距離為ddnnS(p)，則每一點對應的MBSD的表示方法為

定義3[14].點q到空間對象r的距離.假設在2維歐氏空間E(d)中，有一空間對象r(r或為MBR或為MBSD)，r由其主對角線的2個頂點a(a1,a2)和b(b1,b2)來表示，點q的坐標為(q1,q2)，則點q到空間對象r的距離定義為

(1)

其中:

從定義3中可知，當點q位于空間對象r的內部時，其距離定義為0，其余情況均為點q到該對象邊界的最小距離.而且對于定義3的MINDIST距離必定小于等于q到r的邊界上任意一點距離的平方，在歐氏距離中使用平方定義點到某一對象的距離與再開方的效果是相同的，而且在運算時還減少一次開方的過程，運算速度更快.對于定義3的基于2維歐氏空間的距離運算，易于擴展至高維空間，計算方式類似，這里不做過多陳述.

對任意2個不同的空間物體按其MBR或MBSD定義序關系:

定義4.假設存在任意2個不同物體的MBR或MBSD:Ii，Ij(i≠j)，按其2個頂點的坐標位置，只要滿足4個條件之一，即：

定義5.假設存在任意2個不同物體的MBR或MBSD：Ii，Ij(i≠j)，按其2個頂點的坐標位置，只要滿足4個條件之一，即：

定義6.假設存在任意2個不同物體的MBR或MBSD：Ii，Ij(i≠j)，按其2個頂點的坐標位置，只要滿足4個條件之一，即：

定義7.假設存在任意2個不同物體的MBR或MBSD：Ii，Ij(i≠j)，按其2個頂點的坐標位置，只要滿足4個條件之一，即：

在2維歐氏空間中，通過定義4～7，得到4種不同的空間數據間序關系.依據這4種序關系，可以對整體的空間數據或結點中包含的數據進行排序.排序算法記為Iid=Sort_MBSD(I,n,id)，其中I為記錄n個數據的MBSD的3維數組；id為標識變量，id=0,1,2,3分別表示按定義4～7對數據排序；Iid為存儲n個數據按照對應id所表示的序關系排序后的序列的3維數組，即I0,I1,I2,I3.將這4類數組另存放于數組I_id中，即有I_id={I0,I1,I2,I3}，在構建MBDNN-樹的結點時方便調用.由于每個數據在按照相對應的序關系排序之后的相對位置是一定的，當局部的數據需要再次排序時，根據每個數據所擁有的唯一標識將所需的數據從已排序的數組中提取出來，完成局部數據的排序.這樣就避免再次調用排序算法，進一步提升了時間利用率，減低時間復雜度.

同樣地，對于更高維的數據，依據上述的這種排序思想，可以定義更多的序關系來構建高維的樹形結構.

2 MBDNN-樹空間數據索引結構

針對RNN查詢的要求提出了一種新的空間數據索引結構：MBDNN-樹.該索引結構利用數據點與其最近鄰之間的距離關系，得到每個數據點的影響區域，將該影響區域用MBSD表示出來，進一步通過MBSD間的序關系進行劃分，將距離盡可能近的MBSD存放在同一個結點中，這樣在進行查詢操作時減少了對無效路徑的搜索，減少了I/O操作.

2.1 MBDNN-樹的結點構成

在MBDNN-樹中，其葉子結點和中間結點的結構為

葉子結點：(CNum,Level,MBR,OI1,MBSD1,…,OIM,MBSDM)，

中間結點：(CNum,Level,MBR,CI1,MBR1,…,CIM,MBRM)，

其中，CNum≤M表示該結點中包含孩子結點或數據項的個數，其中M為該結點中包含孩子結點或數據項的個數的最大值；Level≥1表示該結點在樹中的層數；MBR表示該結點包含的所有的數據項或孩子結點的最小包圍矩形，其x最小值為left，x最大值為right，y最小值為bottom，y最大值為top.對于葉子結點，OIi表示該結點中第i個數據點的地址，MBSDi為第i個數據點以自身為中心、以ddnnS(p)為半徑的圓的最小外包正方形，其x，y的范圍與MBR的x，y的范圍一樣.對于中間結點，CIi表示該結點中第i個孩子結點的地址，MBRi表示該孩子結點內所有最小外包矩形或正方形的最小值.

2.2 MBDNN-樹的定義

定義8.一棵MBDNN-樹定義為滿足條件的M-叉樹：

1) 如果根結點非空，則它至少含有2個孩子結點，且其所有的子樹均為MBDNN-樹.

2) 中間結點node有node.CNum棵子樹，且滿足：

當結點node位于該樹的第4k+4(k=0,1,…)層時(根結點所在的層定義為樹的第1層)，其孩子結點的MBR滿足：

其中，i=1,2,…,node.CNum-1，i

當結點node位于該樹的第4k+1(k=0,1,…)層時，其孩子結點的MBR滿足：

其中，i=1,2,…,node.CNum-1，i

當結點node位于該樹的第4k+2(k=0,1,…)層時，其孩子結點的MBR滿足：

其中，i=1,2,…,node.CNum-1，i

當結點node位于該樹的第4k+3(k=0,1,…)層時，其孩子結點的MBR滿足：

其中，i=1,2,…,node.CNum-1，i

node.CNum是結點node所包含的孩子結點的數量.

3) 中間結點仍然是一棵MBDNN-樹.

2.3 MBDNN-樹的構建

2.3.1 預處理過程

給定一個數據集S，對于其中的每一個點pi總能找到一個與其對應的最近鄰點pj(i≠j)，記兩者之間的距離為ddnnS(p)，并對每一點pi產生一個以pi為圓心、以ddnnS(p)為半徑的圓，并在這個圓的基礎上產生其最小包圍正方形，最終得到點集S中每個點的最小包圍正方形圖，如圖2所示：

Fig.2 The MBSDs圖2 最小包圍正方形

在預處理過程中，對數據集S中的每一點p找到其對應的最近鄰，即n個點中有n對最近鄰對，也就是最近鄰近問題(all nearest neighbor problem, ANNP)[14].利用ANNP算法求得最近鄰距離后，將該距離與對應的坐標點在x軸或y軸上加減即可得到相匹配的最小包圍正方形，對n個點進行該操作后即可生成最小包圍正方形圖.生成最小包圍正方形圖算法記為Square_Graph_Create(n,S,I)，其中，將n個數據點的坐標序列存放在2維數組S中，I為存放每個點生成的最小包圍正方形的3維數組，該算法的時間復雜度為O(nlbn).

2.3.2 MBDNN-樹的生成

在構建MBDNN-樹的過程中，使用序關系將所有的數據對象進行劃分且構造相應的結點后，會產生新的中間結點.而新中間結點的MBR包含了當前結點內的所有數據對象MBSD的最小包圍矩形，則得到中間結點MBR的算法為：

算法1.Get_Middle_Node_MBR(n,I_id,MBR).

輸入：n為該中間結點所包含的矩陣的個數，I_id為存儲按照標識變量id(id=0,1,2,3)所表示的序關系排好序的序列數組的數組，即I_id={I0,I1,I2,I3}，MBR為包含輸入的所有矩形的最小包圍矩形；

輸出：最小包圍矩形MBR.

① begin

②MBR.right=max{I_id.I0.MBSD.right}；

③MBR.bottom=min{I_id.I1.MBSD.bottom}；

④MBR.left=min{I_id.I2.MBSD.left}；

⑤MBR.top=max{I_id.I3.MBSD.top}；

/*將n個矩形中對應的left，bottom的最小值賦值給中間結點的left，bottom，top，right的最大值賦值給中間結點的top，right*/

⑥ returnMBR；

⑦ end

定理1.對于構造MBDNN-樹中的一個中間結點，算法1能在有限步內正確完成中間結點最小包圍矩形的生成，且算法1的時間復雜度為O(M).

證明.略.

MBDNN-樹的生成算法是一種貪婪算法.首先，對整個空間的數據或結點中包含的數據按照定義4～7進行排序，然后對排序后的數據進行劃分，從上至下、從左至右按照定義8所給的結點的幾何分布構造索引樹的各層結點，直至要劃分的空間中有不超過結點所包含的數據個數的最大值為止.生成算法描述為：

算法2.MBDNN_Tree_Creation(n,S,b,M,head).

輸入：n個點的集合序列數組S，M是中間結點所具有的孩子結點的最多個數，b為輸入的原始數據是否經過初始化的標志，b=0是未初始化；

輸出：MBDNN-樹的根結點head.

①b=0,Level=0,id=0,I=NULL； /*初始化*/

② ifb=0 then /*預處理過程*/

③ callSquare_Graph_Create(n,S,I)；

④ fori=0 to 3 do

⑤Ii=Sort_MBSD(I,n,i)；

⑥ end for

⑦I_id={I0,I1,I2,I3}；

⑧b=1； /*預處理完成*/

⑨ end if

⑩head.MBR=Get_Middle_Node_MBR(n,I_id,MBR)；

n1×i)；

1):n)；

定理2.對于輸入包含n個矩形的中間結點，算法2能在有限步內正確完成所有中間結點最小包圍矩形的生成，且算法的時間復雜度為O(nlbn).

證畢.

3 基于MBDNN-樹的RNN查詢

從第2節的MBDNN-樹的結構中，可以得到定理3.

定理3.給定一組數據點集S和查詢點q，其中q在S之外，S中的一點p以自身為中心、以ddnnS(p)為半徑作圓，MBSD為該圓的最小包圍正方形.則有p為q的反最近鄰當且僅當q在圓C(p,ddnnS(p))的內部，且q也必定落在該圓的MBSD中.

證明.因為q是p的最近鄰當且僅當D(p,q)≤ddnnS(p)，也就意味著p到q的距離最大時，這個最大距離與p到S中它的最近鄰的距離相等.因此，若q在圓C(p,ddnnS(p))圓周內，則它就是p的新的最近鄰，即p是q的反最近鄰.由于圓C被其MBSD所包圍，因此q必定在該圓的MBSD中.

證畢.

推論1.給出點p以及其所對應的圓C(p,ddnnS(p))的最小包圍正方形MBSD和一個查詢點q，若D(q,MBSD)>0，則q必然不在MBSD中，則p不是q的反最近鄰.

證明.由定理3可知，結論顯然成立.

證畢.

定理4.對于一個查詢點q(qx,qy)，1棵MBDNN-樹上的任意一個中間結點node(位于樹的第k層上)，kc=kmod 4，求出j：

(2)

node的孩子結點與查詢點q(qx,qy)的空間關系為：

1) 當kc=0，3時，對所有的i≤j，node.CIi都不包含查詢點q，即其中一定沒有查詢點q的反最近鄰.對所有的i>j，當kc=0時，若node.CIi.MBRi.left-qx>0，則node.CIi中不包含查詢點q，即其中一定沒有點q的反最近鄰；當kc=3時，若node.CIi.MBRi.bottom-qy>0，則node.CIi中不包含查詢點q，即其中一定沒有點q的反最近鄰.

2) 當kc=1，2時，對所有的i≥j，node.CIi都不包含查詢點q，即其中一定沒有查詢點q的反最近鄰.對所有的i0，則node.CIi中不包含查詢點q，即其中一定沒有點q的反最近鄰；當kc=2時，若qx-node.CIi.MBRi.right>0，則node.CIi中不包含查詢點q，即其中一定沒有點q的反最近鄰.

證明.假設當kc=0時，由j的定義可知，對所有的i≤j有qx-node.CIi.MBRi.right>0，即有0

Fig.3 The spatial relationship between point q and node’s child nodes圖3 點q與節點node的孩子結點間的空間關系

當kc取值為1,2,3時的情況與其相似，使用同樣的方法即可證明其正確性.

證畢.

3.1 剪枝規則

根據上述所給的定義及相應定理，MBDNN-樹中查詢反最近鄰時采用以下剪枝規則，剪枝過程基于MBDNN-樹的結點的幾何位置的有序性和點與最小包圍矩形的關系以及數據點集的ddnnS(p)進行.

剪枝規則1.對于一個查詢點q和一棵MBDNN樹上的任意結點node，若點q到該結點的MBR的距離D(q,MBR)>0，則該結點可以被剪枝掉.

由定理3，制定剪枝規則2.

剪枝規則2.對于一個查詢點q(qx,qy)，一棵MBDNN-樹上的任意一個中間結點node(位于樹的第k層上)，kc=kmod 4，按式(2)求出j，則有:

1) 當kc=0，3時，對所有的i≤j，node.CIi都被剪枝掉.

對所有的i>j，當kc=0時，若node.CIi.MBRi.left-qx>0，則node.CIi都被剪枝掉；當kc=3時，若node.CIi.MBRi.bottom-qy>0，則node.CIi都被剪枝掉.

2) 當kc=1，2時，對所有的i≥j，node.CIi都被剪枝掉.

對所有的i0，則node.CIi都被剪枝掉；當kc=2時，若qx-node.CIi.MBRi.right>0，則node.CIi都被剪枝掉.

剪枝規則3.對于查詢點q，當當前結點是葉子結點且點q落在其中時，對結點中的每一點p，計算其到查詢點q的距離D(q,p)，若D(p,q)>ddnnS(p)，則該數據點p被剪枝掉.

3.2 RNN查詢算法

基于3.1節的剪枝規則，我們給出RNN查詢算法.首先給出該查詢算法的思想：先根據剪枝規則1篩選出不包含查詢點的結點將其剪枝掉，對于可能包含查詢點的結點，利用MBDNN-樹中結點間的空間位置的有序性，根據剪枝規則2進行篩選，剪枝掉大量不包含查詢點的分枝，之后按順序對剩余的結點進行遞歸查詢，直至葉子結點，運用剪枝規則3進行篩選，剪枝掉不符合的數據點后，剩余的數據點即為查詢到的反最近鄰.

設查詢點q，若當前結點為葉結點，利用剪枝規則3對結點中的每一點p，計算其到查詢點的距離D(q,p)，然后與其對應的ddnnS(p)作比較，若D(p,q)≤ddnnS(p)，那么p就是q的1個反最近鄰，反之則將該點剪枝掉.若當前結點不是葉結點，則利用剪枝規則1判斷點q與當前結點的MBR的距離D(q,MBR)，如果D(q,MBR)>0，即點q沒有落在當前結點中，則當前結點直接被剪枝掉；如果落在當前結點中，根據剪枝規則2對其孩子結點進行篩選，滿足條件的將該孩子結點剪枝掉，不進行訪問.否則，遞歸調用此算法到下一層結點中查找，直至葉子結點.

下面給出偽代碼形式描述的RNN查詢算法.

算法3.MBDNN_Search(head,q)./*基于MSDNN-樹的RNN查詢算法*/

輸入：MBDNN-樹的根結點head、查詢點q；

輸出：查詢點q的反最近鄰集合Q.

①Q←NULL； /*初始化查詢點q的反最近鄰集合*/

② ifD(q,head.MBR)>0 then

③ return NULL；

④ else ifhead不是葉子結點then

⑤k=Levelmod 4； /*判斷該層對應序關系*/

⑥ 按照式(2)求j； /*運用二分法確定j*/

⑦ ifk=0 or 3 then

⑧ fori=j+1 tohead.CNumdo

⑨ if (k=0 andhead.CIi.MBRi.left-qx≤0) or (k=3 andnode.CIi.MBRi.bottom-qy≤0) then

⑩ callMBDNN_Search(head.CIi,q)；

定理5.對于有n個數據的MBDNN-樹和查詢點q，MBDNN_RNNSearch(head,q)算法能在有限步內完成關于查詢點q的RNN查詢，算法3的時間復雜度在最壞的情況下為O(max(lbM×(n-M)/M(M-1),n))，最好的情況下為O(Mlbn).

證明.算法的正確性和可終止性顯然成立，不予證明.時間復雜度分析：算法3最壞情況是對所有中間結點做出判斷，求出j的值，即求一次j需要O(lbM)次比較，中間結點總共有1+M+M2+…+MlogMn-2=(MlogMn-1-1)/(M-1)=(n-M)/M(M-1)個，即所花費的時間為O(lbM×(n-M)/M(M-1))；葉子結點總共有Mk-1=MlogMn-1=n/M個，每個葉子結點包含M個數據項，計算每個數據到查詢點q的距離需要常數次判斷，總計需要n/M×M=n次，即總共花費的時間為O(n).因此，時間復雜度在最壞的情況為O(max(lbM×(n-M)/M(M-1),n)).最好的情況是查詢判斷查詢點q落在當前結點下的某個孩子結點中需要常數次比較，一棵MBDNN-樹高度為logMn，則所需時間為logMn.

證畢.

本節對基于MBDNN-樹的RNN查詢進行了研究，根據RNN查詢的性質[11]，在任意的2維數據空間下，對數據集中任意一個查詢點q其反最近鄰最多含有6個，在更高維的情況下，其反最近鄰的最大個數也是一個固定的值，這個值除了跟數據空間的維數相關，也跟所用的距離函數有關.在實際應用中我們不僅僅需要探討與反最近鄰之間的影響，可能還需要知道與反k最近鄰之間的影響，這樣就需要對反k最近鄰的查詢，基于本文的研究，可以推廣至反k最近鄰查詢，這也是下一步的研究工作.

4 實驗結果與分析

將本文給出的基于MBDNN-樹的RNN查詢算法——MBDNN算法與文獻[12]中的VRNN算法、文獻[13]中的RDT算法進行比較，雖然后2個算法一般用于反k最近鄰查詢，但對于反最近鄰同樣適用.在本實驗中取k=1作為RNN.實驗環境為：

1) 硬件環境.1.5 GHz CPU、4 GB內存、100 GB以上硬盤的個人計算機.

2) 軟件環境.Windows 10 Professional操作系統，用Visual Studio 2012編程實現.

3) 測試項目.

① 本測試針對MBDNN算法在不同M的取值情況下，進行RNN查詢時所花費的時間，如表1所示，以及VRNN算法與MBDNN算法在不同數據量級下查詢時間效率，如表2所示，其中M=30，數據集維數選擇在2維.

Table 1 Query Time Performance for Reverse Nearest Neighbor Query on MBDNN-tree with Different M表1 MBDNN-樹RNN查詢在不同M值下的查詢時間

② 鑒于VRNN算法是基于R*-樹的算法，依舊受R*-樹在高維空間的限制，本次測試是在低維數據集下對MBDNN算法、VRNN算法和RDT算法的比較，分別對比了三者在不同數據分布情況下查詢過程中訪問結點的次數，如圖4～6所示，M=10，數據維數選擇在2維.

③ 本測試針對高維空間數據集，鑒于RDT算法在高維數據集上有著較好的改進，本文的MBDNN算法與VRNN算法同該算法進行比較，對比了三者在不同數據分布情況下查詢時的CPU性能與I/O性能，如圖7～9所示，M=10，數據維數選擇在11維.

Table 2 Comparison of Query Time for MBDNN Algorithm and VR Algorithm表2 MBDNN算法與VR算法的查詢對比

Fig.4 Query performance comparison for 2D uniform distribution data set圖4 2維均勻分布數據集查詢性能對比

Fig.5 Query performance comparison for 2D Gaussian distribution data set圖5 2維高斯分布數據集查詢性能對比

Fig.6 Query performance comparison for 2D group distribution data set圖6 2維群分布數據集查詢性能對比

Fig.7 Query performance comparison for 11D uniform distribution data set圖7 11維均勻分布數據集查詢性能對比

Fig.8 Query performance comparison for 11D Gaussian distribution data set圖8 11維高斯分布數據集查詢性能對比

Fig.9 Query performance comparison for 11D group distribution data set圖9 11維群分布數據集查詢性能對比

以上實驗所需數據分別用不同大小的數據集進行測試，數據來源由人工隨機生成均勻分布、高斯分布和群分布的數據集，其數量級分別為10 000,20 000,30 000,…,100 000.數據測試結果如表1所示.

通過實驗數據可以得到3個結論：

1) MBDNN算法的查詢速度會隨著M值的變化而發生改變，如表1所示.由前面算法分析可知，M一方面影響樹中孩子結點的數量，另一方面影響樹的高度.當數據量級不變時，M值越大，樹的高度越小，中間結點的訪問數量也會減小；反之，M值越小，樹的高度越大，中間結點的訪問數量也會隨之增大.但是當樹的高度一定時，M值的增大也會造成中間結點的增多.而當M值一定時，數據量級越大，樹的高度也就越大，中間結點的數量則呈指數級增長，而訪問的中間結點的數量越多，花費的時間也就越多.如表1所示，不同M值與數據量級的變化產生的樹的高度同上述分析一致，以及兩者對MBDNN算法查詢時間長短的影響也是一致的，由此可知，根據數據量級確定合適的M值，可以最大化地提高查詢效率.表2的實驗結果表明，在2維數據集中，MBDNN算法的查詢時間明顯比VRNN算法所消耗的時間要少，而且隨著數據量級的增大，兩者的區別更加明顯.

2) 從圖4～6的數據可以得知，在低維空間數據集下，即使采用不同的數據分布類型，MBDNN算法的性能均比VRNN算法、RDT算法要好，且在不同規模的數據集下，數據集的規模越大，兩者的差距越明顯，MBDNN算法能夠減少更多的對無效結點的訪問，加快了查詢速度，但是三者的查詢性能也隨著數據集的增多逐漸趨近于穩定.

3) 從圖7～9中可以得知，數據集在高維的情況下，MBDNN-樹的RNN查詢性能仍然有較好的查詢性能.在11維空間數據集下，VRNN算法由于本質是基于R*-樹的，在數據維數較高時其性能依舊受到很大的限制.從圖7～9中可以看出VRNN算法在查詢時所需要的I/O操作以及消耗的CPU時間均比其他2種算法要多，而且隨著數據量的增大這種情況變得更加糟糕，相較而言RDT算法和MBDNN算法則有較好的表現.

而MBDNN算法也因MBDNN-樹良好的結構在查詢時有更少的I/O操作，其基于各類序關系的劃分以及MBSD良好的特性，減低了無效路徑的查詢，降低了CPU耗時.綜上所述，MBDNN-樹在低維空間以及高維空間都有較高的RNN查詢效率.

5 結 論

本文基于對RNN查詢的研究，提出了一種新的空間數據索引結構MBDNN-樹以提升其查詢效率.該索引結構運用了R-樹中分割數據空間的思想，將數據點集通過最近鄰距離擴展為最小包圍正方形，繼而利用其中多種序關系優化索引結構，減少不同結點間的交疊問題，減少無效訪問路徑和無效訪問結點，已達到提高RNN查詢性能的目的.通過對MBDNN-樹的定義、構造算法以及相關的RNN查詢算法的分析，實驗結果說明:這是一種有效的空間索引結構，且在高維空間也有較好的查詢速度.下一步將研究該索引下的更多查詢算法.