范围最近邻查询方法研究

刘 彬，王建国

(1.泰山学院信息科学技术学院;2.泰山学院教务处，山东泰安 271021)

1 引言

最近邻(Nearest Neighbor，简称NN)查询是空间数据库中一种重要的查询类型，传统的NN查询是指查询离给定点最近的对象，称为点的最近邻(Point NN，简称PNN)查询［1］.Tao等人提出的连续最近邻(Continuous NN，简称CNN)查询［2］，可以有效地检索一条线段上所有点的最近邻，此查询的输入限定在一维线段上.

本文提出了二维情形下的最近邻查询问题——“范围最近邻”(Range NN，简称RNN)查询.在二维情形下，给定一个数据集，RNN查询检索矩形里每一个点的最近邻.RNN查询的应用比较广泛，比如在移动环境中，用户在确定查询点时，由于定位方法的原因，他们没有办法找到自己的准确位置.即使能准确定位，他们也可能由于个人原因没有办法将准确位置提供给服务商.RNN查询解决了这个问题，因为它查询的是范围的最近邻而不是点的最近邻.大量的2G/3G移动用户更适合使用这种查询，因为这些设备不支持连续最近邻，他们可以将RNN查询阐述成“寻找离城市公园最近的旅社”这样的问题.再如，一个用户当在附近走动的时候可能会持续地寻找最近邻，向服务器分别提交这些PNN查询是低效的.一个更好的方法是进行RNN查询来获得这个范围所有可能的最近邻.在这个范围内的任何PNN查询都可以在这个预先取出的集合中获得，这将节省计算和通信的代价.这说明RNN查询适用于小范围内的不同用户进行PNN查询的情形.由于空间邻近的PNN查询范围相同的R树结点.如果对这些点进行分组处理，将他们归属于不同的范围，然后进行RNN查询，在RNN的基础上找到PNN，将会提高效率.本文主要研究范围最近邻查询的性质和基本处理思想.

文章第2部分回顾CNN查询的一些相关知识;第3部分给出RNN查询的正式定义，分析查询性质，并通过一个例子描述了LNN(Line NN)算法的基本处理过程;第4部分分析LNN算法的时间复杂度;最后，提出了一些未来研究的方向.

2 相关工作

Song等人在文献［3］中第一次提出了“连续最近邻”查询的概念，一个CNN查询查找一个移动对象的最近邻，更具体地说，它查找一条线段上所有点的最近邻.为了处理CNN查询，Song提出了在线段上反复对一些取样点进行NN查询，在［2］中，Tao等人详细说明了CNN处理算法.他们证明了这条线段包含一个“分割点”的集合，其中每一个分割点有两个相同距离的最近邻对象，并且这些最近邻对象组成了CNN集合.因此，CNN问题等价于遍历R－树时找到和储存那些分割点，为了删除不必要的结点存取，他们提出了三个规则:

1)对于一中间结点E和查询线段q，删除mindist(E，q)＞SLMAXD的结点，SLMAXD是所有分割点和它的NN之间距离的最大值.

2)删除到每一个分割点s的最小距离比s和s的NN之间距离大的结点.

3)按它们的MINDIST值递增访问结点.

Tao等人将这些规则分别通过广度和深度优先搜索来实现，并更进一步推广这些算法来解决kCNN查询，kCNN查询找到的是一条线段上所有点的k个最近邻.

3 范围最近邻查询(RNN查询)

3.1 RNN查询的定义

定义1 给定一个二维空间的数据集R2，一个矩形A(边界在内)的范围最近邻(RNN)的集合可以表示为RNN(A)，即为A中每一个点的最近邻(NN)的集合.有:

NN(p)表示点p的最近邻，A称为查询范围在二维情形下为矩形，当它在零－维和1－维空间中，RNN分别变为PNN和CNN.

本文采用欧氏距离，这意味着每一个对象是一个点或者可以被一个点来代表，因此本文限定数据集合于为点数据集.

3.2 RNN查询的性质

根据定义1可知任何一个A中的对象是A的一个RNN，我们称它为内部RNN，因此我们主要是寻找外部RNN，也就是A外的RNN.

图1 引理1、2、4的证明辅助图

引理1 一个对象p成为A的一个外部RNN的充要条件是p不在A内而是A边界上的至少一个点的NN.

证明:必要条件从定义中可以看出是显然的.充分条件可以通过反证法来证明:假定p不是A边界上的任何一个点的NN，但p是一个RNN2，则p至少是A内一个点i的NN，如图1(a)，i'表示线段和 A边界的相交点.由于p不是i'的NN，则必有另一个对象p'使得比短，也就是说，，在不等式的两边加上，我们得到，这和我们的假设p是i的NN相矛盾.因此假设错误，充分条件得证.

引理1告诉我们查询A的外部RNN和查询A边界上每个点的NN是等价的，A的边界包含四条线段，因此，这个问题就可以转化为查找一条线段L上所有点的NN，这些NN称为L的线段最近邻(LNN).

证明:假定L上有一个点i，L的NN是p且p'是i的第二最近邻(如图1(b))，设s表示，t表示，取L上一个小线段

引理2 线段L可以被划分为有限数量的小线段，小线段上的每一个点有相同的NN.，则它上面的所有点的NN为p，因为它们到p的距离总是比s+小，并且它们到p'后其他对象的距离总是比大.由于L的长度是有限的且这个小线段有固定的长度t－s，因此这些小线段的数量是有限的.

引理3 如果任何两个邻近的小线段有不同的NN，那么，所有的小线段都有不同的NN.

通过对前面引理的证明，引理3是比较明显的，它说明了一个对象最多可以成为一条小线段的NN.

引理4 设e1，e2，…表示从左到右所有小线段的末端点，p1，p2，…表示每条小线段的NN.那么，对任意i＜j，有pi·x＜pj·x，其中p·x表示对象p在L上的投影值.

证明:通过反证法来证明这个引理.如果引理不成立，则至少两个相邻的小线段违背这个规则，假设是和，存在·x(见图2c).因此，pk在的垂直平分线的左边，而在右边，那么L上ek左边的点离比离pk近，反之亦然.这就与是的NN且pk是的NN相矛盾，引理成立.

3.3 算法处理过程

在这些引理的基础上，下面通过一个例子来说明LNN算法的基本思想.首先通过对象p在L上的投影值来决定要处理的对象的顺序，如图1所示，处理顺序为p1，p2，p3，p4，p5(在两个或更多个对象有相同投影值的情况下，只保留离L最近的对象).然后，计算每个对象所对应的小线段，如果一个对象没有相应的小线段，这意味着这个对象不是一个LNN.这些小线段的端点可以通过L和每一对连续对象的垂直平分线的交点来计算获得.在图1中，最初e1=L.min是p1对应小线段的左端点，当处理p2时，e2作为p2的左端点(也是p1的右端点);然而，当p3被处理时的垂直平分线与L相交在e2左边某个地方的一个点，这意味着p2没有对应的小线段，因为p1或 p3比p2到L上的任何一点要近.因此p2不是一个LNN，故被移除.这样p1和p3成为连续的对象，p3对应小线段的左端点即被重新计算，由于位于e2的左端，说明上的点距p3比距p1更近，因此e2被移除.接着处理p4，并得到e3作为p4相应小线段左端点.最后处理p5，但的垂直平分线没有与L相交，这意味着p5没有小线段，不是一个LNN.由于p4是保留的最右边对象，它的小线段的右端点为e4=L.max，这样所有点被处理完.得到结果:p1，p3和p4是LNN，相应的小线段是和.

图2 LNN查询示例

4 算法性能分析

LNN算法处理过程分为两个阶段，第一阶段是通过对查询对象的排序来决定对象的处理顺序，第二阶段是扫描对象并计算对应小线段的端点.

排序可以使用快速排序方法［4］，在最好情况下花费O(nlogn)的时间代价，在最坏情况下花费O(n2)的时间代价，平均时间代价通过推算可以得知为O(nlogn);在扫描过程中需要计算小线段的端点，假设每次计算的时间为c(c为任意常数)，则整个扫描时间为cn，因此扫描过程的时间代价为O (n).如果程序由两部分(两组语句或者两段代码)顺序组成，我们只需要考虑其中开销较大的部分，因此LNN算法的时间复杂度是O(nlogn).

5 结束语

文章提出范围最近邻(RNN)查询作为点最近邻(PNN)和连续最近邻(CNN)查询的扩展，并在2D空间中分析了查询的性质，提出了算法基本思想并作了性能分析.未来的工作将致力于动态数据集中范围最近邻查询的研究.

［1］N.Roussopoulos，S.Kelley，F.Vincent.Nearest neighbor queries［A］.Proc.of the ACM SIGMOD Intl.Conf.on Management of Data［C］.New York:ACM，1995.

［2］Y.Tao，D.Papadias，Q.Shen.Continuous nearest neighbor search［A］.In Proc.of 28th Intl.Conf.on Very Large Data Bases (VLDB)［C］.Hong Kong:VLDB Endowment，2002.

［3］Z.Song，N.Roussopoulos.K－Nearest Neighbor Search for Moving Query Point［A］.Proc.Symp.Spatial and Temporal Databases［C］.Berlin:Springer，2001.

［4］(美)Clifford A.Shaffer.数据结构与算法分析(Java版)［M］.北京:电子工业出版社，2001.