文献类型：期刊文章

作　　者：刘润涛[1,2] 梁建创[1]

Liu Runtao;Liang Jianchuang(College of Science,Harbin University of Science and Technology,Harbin 150080;Institute of Information and Scientific Computing Technology,Harbin University of Science and Technology,Harbin 150080)

机构地区：[1]哈尔滨理工大学理学院,哈尔滨150080 [2]哈尔滨理工大学信息与科学计算技术研究所,哈尔滨150080

出　　处：《计算机研究与发展》

基　　金：国家自然科学基金项目(11871181)。

年　　份：2020

卷　　号：57

期　　号：6

起止页码：1335-1346

语　　种：中文

收录情况：AJ、BDHX、BDHX2017、CSCD、CSCD2019_2020、EI、IC、JST、PROQUEST、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：为了提高反最近邻问题的查询效率,首先给出了空间数据的最小包围正方形定义和空间数据矩形的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-树  空间数据库 索引结构 反最近邻 查询算法

分 类 号：TP311.13]