基于新型索引结构的反最近邻查询

刘润涛 梁建创

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查询算法的分析，实验结果说明:这是一种有效的空间索引结构，且在高维空间也有较好的查询速度.下一步将研究该索引下的更多查询算法.