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

Reverse Nearest Neighbor Query Based on New Index Structure

为了提高反最近邻问题的查询效率,首先给出了空间数据的最小包围正方形定义和空间数据矩形的4种序的定义.依据这些定义,提出了一种新的空间数据索引结构——基于最小包围正方形和最近邻距离的索引树(index tree based on the minimum bounding square and the distance of nearest neighbor,MBDNN-tree),该索引结构运用了R-树中分割空间数据的思想,将数据点用其基于最近邻距离的最小包围正方形表示,记为MBSD(minimum bounding square based on nearest neighbor distance),利用多种序关系对原始点集进行划分,从上至下、从左至右地按照结点几何分布以及对应的序关系构造树的各层结点.对建立MBDNN-树所需要的预处理过程以及构造过程的算法进行了详细描述和证明分析,给出了MBDNN-树的性质.在此基础上,给出了MBDNN-树进行反最近邻查询的剪枝规则,进而给出了MBDNN-树进行反最近邻查询的算法及其算法分析.反最近邻查询算法利用了MBDNN-树中同层结点之间的几何有序性,有效地减少了结点的访问数量,从而提高了查询效率.最后对基于此结构的反最近邻查询算法进行实验分析.实验表明:基于MBDNN-树的反最近邻查询算法的查询性能有较大的提高.

To improve the efficiency of reverse nearest neighbor query,firstly the definition of the minimum bounding square based on nearest neighbor distance(MBSD)for spatial data and the definitions of four orders for spatial data are given.Then a new spatial data index structure—the index tree based on the minimum bounding square and the distance of nearest neighbor(MBDNN-tree)is proposed according to these definitions.The new index structure uses the idea of dividing spatial data in the R-tree,to construct the nodes on each level of an MBDNN-tree according to nodes geometric distribution and the corresponding order relation of nodes,by dividing the original data set in defined orders from top to bottom,and from left to right by using its MBSD to represent data.And then the detailed description and proof analysis are made for the algorithms in the preprocessing and constructing procedures used for creating an MBDNN-tree.The properties of an MSDNN-tree are obtained.Then the pruning rules for reverse neighbor query on an MBDNN-tree are set up,and further the reverse neighbor query algorithm on an MBDNN-tree is presented.The geometric orders among the nodes on the same level of an MBDNN-tree are used to reduce the visited node number of an MBDNN-tree for the reverse neighbor query so that the algorithm s query efficiency is greatly improved.Finally,the reverse nearest neighbor query algorithm based on this structure is analyzed experimentally.Experiments show that the reverse nearest neighbor query algorithm based on MBDNN-tree has better query performance.