ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2020, Vol. 57 ›› Issue (6): 1335-1346.doi: 10.7544/issn1000-1239.2020.20190470

• 软件技术 • 上一篇    

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

刘润涛1,2,梁建创1   

  1. 1(哈尔滨理工大学理学院 哈尔滨 150080);2(哈尔滨理工大学信息与科学计算技术研究所 哈尔滨 150080) (liurthar@163.com)
  • 出版日期: 2020-06-01
  • 基金资助: 
    国家自然科学基金项目(11871181)

Reverse Nearest Neighbor Query Based on New Index Structure

Liu Runtao1,2, Liang Jianchuang1   

  1. 1(College of Science, Harbin University of Science and Technology, Harbin 150080);2(Institute of Information and Scientific Computing Technology, Harbin University of Science and Technology, Harbin 150080)
  • Online: 2020-06-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (11871181).

摘要: 为了提高反最近邻问题的查询效率,首先给出了空间数据的最小包围正方形定义和空间数据矩形的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-树的反最近邻查询算法的查询性能有较大的提高.

关键词: MBDNN-树, 空间数据库, 索引结构, 反最近邻, 查询算法

Abstract: 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.

Key words: MSDNN-tree, spatial database, index structure, reverse nearest neighbor, query algorithm

中图分类号: