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

来源：计算机研究与发展杂志2020年第6期北京时间：

作者：刘润涛,梁建创,

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

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