面向多维对象的RC-反k近邻查询新方法

刘大有，吕倩楠，王生生

吉林大学计算机科学与技术学院，长春130012

反 k近邻 (reverse k nearest neighbor，RkNN)查询自提出后，受到数据库界的广泛关注，它在决策支持、资源配置、数据挖掘及基于剖面的市场分析等领域有着重要的应用价值［1］.一个对象很可能从其近邻请求服务，若提供服务的对象知道哪些对象期望服务 (进行RkNN查询)，就可有针对性地采取应对措施.求助服务的对象可以是战场上的战士，危险环境下的游客等;提供服务的对象可以是各种救助人员.例如，某城市发生多起事故，救助人员或相关执法人员可通过反k近邻查询对事故现场进行及时处理.

Korn等［2］提出反近邻查询并给出一种依赖预处理的查询方法，但该方法不能有效更新数据库.Stanoi等［3］提出无需预处理的6区域剪枝法，但该方法只适于2维空间.TAO等［4］将该方法扩展到解决k＞1的情况;并且利用垂直平分线特性，提出TPL剪枝法，但当k较大时该方法计算量较大，不适于计算能力弱的设备.Singh等［5］基于对象的近邻很可能成为其反近邻的观点，提出SFT方法，但该方法结果不精确.WU等［6］提出利用垂直平分线在平面上形成凸多边形进行剪枝的方法，但该方法同样只适用于2维空间.此外，还有学者研究了连续反 k近邻 (continuous reverse k nearest neighbor，CRkNN)查询［4，7-9］.

本研究提出一种新的RkNN查询方法，采用过滤-精炼两步式处理方法［10］，在过滤阶段采用两种新的计算量小且剪枝率高的剪枝启发式，可有效处理数据库更新，适用于任意k值、任意维的对象集，查询结果精确且计算量小.通过对4个真实数据库的仿真对比实验，发现当k＞6时基于R树结点覆盖值 (R-tree's cover-value，RC)反k近邻查询时间更短.

1 相关知识

1.1 基本定义

设多维对象集P，查询点q∉P，对象p∈P，o∈P.dist(q，p)表示q和p之间的欧几里得距离.

定义1 k近邻查询，记作kNN.p是kNN(q)的查询结果，当且仅

q的反k近邻与k近邻无直接联系［4］，如图1.对象集 P={p1，p2，p3，p4}，查询点为 q，2NN(q)={p1，p3}但 R2NN(q)={p3，p4}.

图1 近邻和反近邻的例子Fig.1 Examples of 2NN and R2NN

1.2 R树索引结构

速度是数据集查询的关键指标之一，而使用索引是提高速度的核心技术.Guttman［11］提出的R树是B树在k维空间上的扩展，由中间结点和叶结点组成.叶结点存储实际空间对象的最小边界矩形(minimum bounding rectangle，MBR)，中间结点存储其子结点的MBR.其中，实心点为数据对象、矩形为结点的MBR.我们将以图2(a)所示的2D数据空间为例进行介绍，图2(b)为对应的R树索引结构.

图2 2维数据空间和R树Fig.2 2D dataspace and corresponding R-tree

2 RC-反k近邻查询方法

对R树索引的数据集进行查询，一般采用过滤-精炼两步式处理方法［10］:过滤阶段将排除非查询结果的对象，并得到候选集;精炼阶段将进一步确认候选集中的对象，并得到精确结果集.过滤阶段是重点，因此现有的大部分反k近邻查询方法都是针对过滤阶段进行的研究.本研究在过滤阶段采用两种剪枝启发式排除非查询结果的对象，并将得到的候选集作为精炼阶段的输入.

精炼阶段有两种处理方法［6］:一是利用kNN查询，对候选对象进行kNN查询，若候选对象到第k近邻的距离不小于到q的距离，则该候选对象即为所求;二是利用 range－k(q，p)，若结果为真，则该候选对象即为所求.但这两种方法都需在精炼阶段遍历R树.本研究提出的RC-反k近邻查询方法采用TPL精炼方法［4］，可记录过滤阶段剪枝的R树结点和数据对象，对于它们不需再次访问外存，从而减少了I/O操作.

RC-反k近邻查询方法需在建立R树时为每个结点预计算cover值［12］.其中，cover值为以该结点为根的子树所包含数据对象的个数.如图2，cover(N1)=2，cover(N3)=4.该预处理过程简单，只需在插入过程中将插入路径 (从根到叶节点)上的每个R树结点的cover值加1，显然该预处理可很好地应对数据库更新.

2.1 剪枝启发式

对R树索引的数据集进行反k近邻查询时需遍历R树，又因R树存储在外存中，所以加快查询速度的关键在于减少访问R树结点的个数，降低I/O开销.若通过当前结点可判断出以该结点为根的子树不包含所求对象，则该结点被剪枝，无需继续访问该结点的子结点.下面我们将主要讨论如何对R树结点进行剪枝，即判断R树结点包含的对象并非所求.

总结反k近邻剪枝的本质:设数据对象集为P，查询点q∉P，对象p∈P，若可在P找到k个对象到p的距离小于q到p的距离，即使这些对象不是p的k近邻，但通过它们可判定q非p的k近邻，即p非q的反k近邻.

2.1.1 剪枝启发式Ⅰ

剪枝启发式Ⅰ基本思想:若数据空间中某个区域R内含n(n＞k)个对象，该区域内的对象相互接近 (即对于R中任一对象p，R中至少存在其他k个对象比q更接近p)，则R中不可能包含q的RkNN.

引理1 当结点N的cover(N)≥k+1，且mindist(N，q)＞diag(N)，则结点N被剪枝.其中，mindist(N，q)是结点N的MBR到q的最小距离，diag(N)是结点N的MBR对角线.图3为剪枝启发式Ⅰ的示意图.

图3 剪枝启发式ⅠFig.3 Pruning heuristic methodⅠ

【证】结点N中对象p到N中其他对象p'的距离为 dist(p，p')≤ diag(N)，又有 mindist(N，q)≤dist(p，q).若 diag(N)＜ mindist(N，q)，则 dist(p，p')＜dist(p，q).若N中存在≥k个数据对象到p的距离小于q到p的距离，则p非q的RkNN.

不能被剪枝启发式Ⅰ剪枝的情况有:①cover(N)≤k;②cover(N)＞k，且q和N的位置关系如图4，其中，q在浅灰色区域中;虚线长度为diag(N).

图4 当cover(N)＞k时N不被剪枝的情况Fig.4 The case that N is not pruned when cover(N)＞k

综上可知，剪枝启发式Ⅰ计算量很小，剪枝效率较高，大部分数据对象都可被剪枝启发式Ⅰ排除.如图2，当k=1时，结点N12、N2和N4都被剪枝.

2.1.2 剪枝启发式Ⅱ

剪枝启发式Ⅱ基本思想:若数据集空间中某区域R内含n(n≥k)个对象，某个数据对象p∉R到该区域的最大距离小于到q的最小距离，即R中至少存在k个对象更接近p，则p非q的RkNN.

引理2 当结点N的cover(N)≥k，且结点N和q的位置关系如图5(q处于粗实线左下方)，则图5中处于阴影部分的结点被剪枝.

图5 剪枝启发式ⅡFig.5 Pruning heuristic methodⅡ

【证】阴影部分中对象p到结点N的最远距离是dist(A，p)，线段qp交BA的延长线于点E，显然dist(q，p)＞dist(E，p)且dist(E，p)≥dist(A，p)，则dist(q，p)＞dist(A，p).又因dist(A，p)是结点N到p的最远距离，显然N中的对象到p的距离小于dist(q，p)，其中cover(N)≥k，则对于阴影内的对象至少找到k个对象比q离p近，所以阴影内的结点或对象不是q的RkNN.

为了提高剪枝启发式Ⅱ的效率，本研究以q为中心划分整个数据空间.下面以2维空间为例进行介绍.

如图6，首先将整个2维数据空间以q为中心划分为 4部分，并为每部分找出矩形 N，使cover(N)=k.然后，在每部分分别应用剪枝启发式Ⅱ，则各部分都会形成一个阴影区域，阴影区域中的对象不是q的RkNN.为达到更大的剪枝效率，形成大阴影区域，在每部分中选取离q较近的k个对象，用这k个对象形成矩形N.因为RC-反k近邻查询方法使用了基于最小距离的优先堆栈H(基于对象的近邻很可能成为它的反近邻这种直观想法)，而H中的项按照到q的最小距离从小到大排序，所以每部分的前k个数据对象即所选对象.

图6 2维空间中使用剪枝启发式ⅡFig.6 Using pruning heuristic methodⅡin 2D space

由图6可见，仅R树结点 (黑色矩形)完全属于某部分时才可使用剪枝启发式Ⅱ.当结点和N中心点的相对位置与N和q的相对位置一致时，结点或对象可被剪枝启发式Ⅱ剪枝.例如2维数据空间中结点和点的相对位置有4种情况:图6中R1、R2、R3、R4分别和点q的位置关系.图6中矩形BN和点c的相对位置关系与矩形N和点q的相对位置关系一样.

多维数据集空间划分类似于2维，设维数为d，则多维数据集可划分为2d个区域，其相对位置关系有2d种.

2.2 方法描述

过滤阶段使用基于最小距离优先的堆栈H保存即将访问但尚未访问的R树结点或数据对象.首先将R树根结点压入堆栈，每次从堆栈中取出一项e进行判断，直到堆栈为空时过滤阶段结束.本研究分两种情况对取出的项e进行判断.

考虑cover(e)＞k情况.若e可被剪枝启发式Ⅰ剪枝，则使用剪枝启发式Ⅰ剪枝;若e不能被剪枝启发式Ⅰ剪枝且e完全属于数据空间某部分，则使用剪枝启发式Ⅱ剪枝;若e不能被上述两个剪枝启发式剪枝，则将e的子结点压入堆栈，并进入下次循环.

考虑cover(e)≤k情况.①e完全属于数据空间某部分中且是数据对象若该部分尚未形成剪枝矩形，则将其插入该矩形集合，用来形成剪枝矩形;若该部分已形成剪枝矩形，且剪枝启发式Ⅱ成功，则将其插入到剪枝集合Strim;否则，需判断该数据对象到剪枝矩形的最大距离是否小于到q的距离，若小于则插入Strim，否则插入候选集Sscnd.②e完全属于某部分且是R树结点，若该部分已形成剪枝区域且可被剪枝启发式Ⅱ成功剪枝，则插入Strim.③e不完全属于某部分且是数据对象，则插入Sscnd.④若以上情况皆不是，则将e的子结点插入到堆栈H中.

RC-反k近邻查询方法过滤阶段的描述如图7.

过滤阶段结束后得到的候选集Sscnd和剪枝集合Strim作为精炼阶段的输入.在精炼阶段本研究选用TPL的精炼方法［4］，其基本原理可描述为:① 设候选集中点为p，若候选集中存在另一点p'使dist(p，p')＜dist(p，q)，则p非所求;② 设候选集中点为p，若Strim中存在点p'使得dist(p，p')＜ dist(p，q)，则p非所求;③设候选集中点为p，若Strim中存在结点 N使 得 minmaxdist(p，N) ＜ dist(p，q)(minmaxdist(p，N)代表p到N中点的最小距离的上限)，则 p非所求;④ Strim中的结点 N，若mindist(p，N)≥dist(p，q)，则可以确定p是所求;否则该候选点在这次循环中无法确定，并记录所有mindist(p，N)＜dist(p，q)的N供下次循环使用，直到候选集为空时精炼阶段结束.

图7 RC-反k近邻查询方法过滤阶段算法描述Fig.7 Algorithm of RC-RkNN in the filter step

3 实验分析

为分析算法的执行性能，我们通过仿真对比本研究所提出的RC-反k近邻查询方法与TPL方法的查询结果.仿真实验在双核2.8 GHz处理器、1 GB内存和Microsoft Windows XP professional操作系统的PC机上完成.RC-反k近邻查询方法和TPL方法使用C语言实现.数据采自美国Long Beach地理位 置 LB(http://www.census.gov/geo/www/tiger)、地势图数据 Hypsogr(http://www.rtreeportal.org)、美国国家浮标中心的三维海浪方向测量Wave(从 http://www.ndbc.noaa.gov)和图像四维彩色直方图 Color(http://www.cs.cityu.edu.hk/～ taoyf/ds.html)数据集，其信息如表1.本研究使用Spatial-DataGenerator数据生成器(http://www.rtreeportal.org/software/SpatialDataGenerator.zip)，生成遵循 U-niform分布和Zipf分布的数据集.其中，Uniform数据集中每个对象的坐标都规范在［0，10 000］;Zipf数据集服从1个偏离系数为0.8的Zipf分布.以上所有数据集中每个数据对象的坐标在每一维上都是独立的，各数据集都使用R*树索引［10］，每个结点的大小设定为1 kbytes.

表1 实验使用的真实数据集的统计信息Table 1 Statistics of real datasets

实验主要评估数据分布、k值、数据维数及数据基数对查询效果的影响.每种查询方法都进行400次 (这400次查询的查询点是属于数据集空间的400个点)，结果取其平均值.

首先研究k值对查询效果的影响.图8显示不同k值下，RC-反k近邻查询方法和TPL方法在各真实数据集中的查询耗时.其中，查询耗时分为过滤阶段的耗时和精炼阶段耗时;a是RC-反k近邻查询方法的剪枝启发式Ⅰ的剪枝率.由图8可见，当k＞6时，所有数据集中RC-反k近邻查询方法的查询时间均小于TPL方法，且因RC-反k近邻查询方法的剪枝启发式Ⅰ和k值几乎无关，所以RC-反k近邻查询方法过滤阶段耗时变化幅度很小.图8中的百分比验证剪枝启发式Ⅰ可减掉大部分数据对象，且剪枝启发式Ⅰ的计算量相当小，这正是导致RC-反k近邻查询方法耗时较短的原因.

图9显示数据空间维数对查询结果的影响.设k=8，数据集包含104个数据对象，分别用2维和3维Uniform和Zipf数据集进行实验.由图9可见，RC-反k近邻查询方法和TPL方法的查询耗时随数据集维数的增加而增加.这是因为当维数增加时，R*树效率变低 (同层R*树结点的MBR相互重叠比较大［4］).由图9柱状图上方所标a值可见，RC-反k近邻查询方法中的剪枝启发式Ⅰ对Zipf数据集比Uniform数据集更有效.

图8 不同k值下RC-反k近邻查询方法和TPL方法查询耗时比较Fig.8 Time consuming of querying by using RC-RkNN and TPL for different k values

图9 当k=8时，2维、3维Uniform和Zipf数据集查询耗时Fig.9 Time consuming of querying for Uniform datasets and Zipf datasets in 2D and 3D when k=8

图10 为相同数据分布、相同数据维数和不同基数数据集的查询耗时.设k=8，且2维Uniform和Zipf数据集分别包含1×104、2×104、3×104和4×104个数据对象.可见，随着数据集基数的增加，查询耗时也增加.这是因为当数据集的基数增加时，R*树高度亦增加［10］.

图10 不同数据基的Uniform和Zipf数据集查询耗时Fig.10 Costs of querying Uniform and Zipf datasets in different sizes

结 语

本研究提出RC-反k近邻查询解决方法，采用过滤-精炼两步式处理方法，在过滤阶段提出两种计算量较小的剪枝启发式，并在精炼阶段使用TPL精炼方法.RC-反k近邻查询方法在k＞6时执行的速度比较快，且该方法易于扩展解决连续RkNN问题.今后的工作将主要集中于解决运动轨迹的RkNN问题.

［1］高云君.时空数据库查询处理关键技术研究［D］.杭州:浙江大学，2008.

［2］Korn F，Muthukrishnan S.反近邻查询的影响集［C］//ACM数据管理国际会议论文集.达拉斯 (美国):ACM计算机协会，2000:201-212.(英文版)

［3］Stanoi I，Agrawal D，Abbadi A E.动态数据库的反近邻查询［C］//ACM SIGMOD数据挖掘和知识发现国际会议论文集.达拉斯 (美国):ACM计算机协会，2000:44-53.(英文版)

［4］TAO Yu-fei，Papadias D，LIAN Xiang，等.多维反 k近邻查询［J］.超大型数据库国际期刊，2007，16(3):293-316.(英文版)

［5］Singh A，Ferhatosmanoglu H，Tosun A.高维反近邻查询［C］//第12届信息和知识管理国际会议论文集.新奥尔良 (美国):计算机协会，2003:91-98.(英文版)

［6］WU Wei，YANG Fei，CHAN Chee-Yong，等.Finch:评估位置数据的反k近邻查询［C］//超大型数据库国际会议论文集.奥克兰 (新西兰):超大型数据库有限公司，2008，1(1):1056-1067.(英文版)

［7］Benetis R，Jensen C S，Karciauskas G，等.移动对象的近邻和反近邻查询［C］//国际数据库工程与应用会议论文集.［s.l.］:［s.n.］，2002:44-53.(英文版)

［8］Cheema M A，LIN Xue-min，ZHANG Ying，等.更新滞后:连续管治反k近邻的有效技术［C］//超大型数据库会议论文集.里昂 (法国):超大型数据库有限公司，2009，2:1138-1149.(英文版)

［9］XIA Tian，ZHANG Dong-hui.连续反近邻查询的管治［C］//第22届数据挖掘国际会议论文集.华盛顿:IEEE计算机协会，2006:77-86.(英文版)

［10］张明波，陆 锋，申排伟，等.R树家族的演变和发展［J］.计算机学报，2005，28(3):289-300.

［11］Guttman A.R树:空间搜索的动态索引结构［C］//ACM SIGMOD数据管理国际会议论文集.纽约:计算机协会，1984:47-57.(英文版)

［12］Güting R H，Behr T，XU Jian-qiu.移动对象轨迹的有效k近邻查询［J］.超大型数据库国际期刊，2010，19(5):687-714.(英文版)

Abstract:1000-2618(2011)05-0416-EA

† This work was supported by the National Natural Science Foundation of China(60773099，60973088).

［1］GAO Yun-jun.Research on Key Techniques of Query Processing in Spatio-temporal Databases［D］.Hangzhou:Zhejiang University，2008.(in Chinese)

［2］Korn F，Muthukrishnan S.Influence sets based on reverse nearest neighbor queries［C］//Proceeding of the ACM SIGMOD International Conference on Management of Data.Dallas(USA):Association for Computing Machinery，2000:201-212.

［3］Stanoi I，Agrawal D，Abbadi A E.Reverse nearest neighbor queries for dynamic databases［C］//Proceeding of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.Dallas(USA):Association for Computing Machinery，2000:44-53.

［4］TAO Yu-fei，Papadias D，LIAN Xiang，et al.Multidimensional reverse kNN search［J］.The International Journal on Very Large Data Bases，2007，16(3):293-316.

［5］Singh A，Ferhatosmanoglu H，Tosun A.High dimensional reverse nearest neighbor queries［C］//The 12th International Conference on Information and Knowledge Management.New Orleans(USA):Association for Computing Machinery，2003:91-98.

［6］WU Wei，YANG Fei，CHAN Chee-yong，et al.Finch:evaluating reverse k-nearest-neighbor queries on location data［C］//Proceeding of Very Large Data Bases.Ackland(New Zealand):Very Large Data Boses Endowent Inc，2008，1(1):1056-1067.

［7］Benetis R，Jensen C S，Karciauskas G，et al.Nearest neighbor and reverse nearest neighbor queries for moving objects［C］//Proceedings of International Database Engineering and Applications Symposium.［s.l.］:［s.n.］，2002:44-53.

［8］Cheema M A，LIN Xue-min，ZHANG Ying，et al.Lazy updates:an efficient technique to continuously monitoring reverse kNN［C］//Proceeding of the VLDB Endowment.Lyon(France):Very Large Data Boses Endowent I，2009，2:1138-1149.

［9］XIA Tian，ZHANG Dong-hui.Continuous Reverse Nearest Neighbor Monitoring［C］//Proceedings of the 22th International Conference on Data Engineering.Washington:IEEE Computer Society，2006:77-86.

［10］ZHANG Ming-bo，LU Feng，SHEN Pai-wei，et al.The evolvement and progress of R-tree family［J］.Chinese Journal of Computers，2005，28(3):289-300.(in Chinese)［11］Guttman A.R-trees:a dynamic index structure for searching［C］//Proceedings of the ACM SIGMOD International Conference on Management of data.New York:Association for Computing Machinery，1984:47-57.

［12］Güting R H，Behr T，XU Jian-qiu.Efficient k-nearest neighbor search on moving object trajectories［J］.The International Journal on Very Large Data Bases，2010，19(5):687-714.