1(哈尔滨理工大学理学院 哈尔滨 150080);2(哈尔滨理工大学信息与科学计算技术研究所 哈尔滨 150080) (liurthar@163.com)
出版日期: 2020-06-01基金资助:国家自然科学基金项目(11871181)Reverse Nearest Neighbor Query Based on New Index Structure
Liu Runtao1,2, Liang Jianchuang11(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-01Supported by:This work was supported by the National Natural Science Foundation of China (11871181).摘要/Abstract
摘要： 为了提高反最近邻问题的查询效率，首先给出了空间数据的最小包围正方形定义和空间数据矩形的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-树的反最近邻查询算法的查询性能有较大的提高.
参考文献
相关文章 15
| [1] | 闫玮, 张兴军, 纪泽宇, 董小社, 姬辰肇. 基于持久性内存的单向移动B+树[J]. 计算机研究与发展, 2021, 58(2): 371-383. |
| [2] | 张丽平,刘蕾,郝晓红,李松,郝忠孝. 障碍空间中基于Voronoi图的组反k最近邻查询研究[J]. 计算机研究与发展, 2017, 54(4): 861-871. |
| [3] | 李玮,张大方,谢鲲,黎文伟,何杰. 一种面向闪存键值存储的矩阵索引布鲁姆过滤器[J]. 计算机研究与发展, 2015, 52(5): 1210-1222. |
| [4] | 冷芳玲, 刘金鹏, 王志刚, 陈昌宁, 鲍玉斌, 于戈, 邓超. BSP模型下基于边聚簇的大图划分与迭代处理[J]. 计算机研究与发展, 2015, 52(4): 960-971. |
| [5] | 李松,张丽平,郝忠孝. 动态数据集环境下的强邻近对查询[J]. 计算机研究与发展, 2015, 52(3): 749-759. |
| [6] | 秦志光,王士雨,赵洋,熊虎,吴松洋. 云存储服务的动态数据完整性审计方案[J]. 计算机研究与发展, 2015, 52(10): 2192-2199. |
| [7] | 杨泽雪, 郝忠孝,. 空间数据库中的组障碍最近邻查询研究[J]. , 2013, 50(11): 2455-2462. |
| [8] | 刘俊岭, 于 戈, 孙焕良,. 空间数据库中主题相关区域查询[J]. , 2012, 49(10): 2171-2180. |
| [9] | 王金宝, 高 宏, 李建中, 杨东华,. RB树：一种支持空间近似关键字查询的外存索引[J]. , 2012, 49(10): 2142-2152. |
| [10] | 张德胜, 冯登国, 陈 驰,. 一种面向空间数据库矢量数据的授权模型与实现方法[J]. , 2011, 48(8): 1524-1533. |
| [11] | 陈坤杰 孙未未 朱 良 刘未末. 空间数据库中一种自适应的缓存替换策略[J]. , 2011, 48(10): 1927-1934. |
| [12] | 廖浩均, 韩冀中, 方金云,. 空间数据库中全局最近邻查询处理方法[J]. , 2011, 48(1): 86-93. |
| [13] | HF-Tree:一种闪存数据库的高更新性能索引结构. 通信作者：孟小峰(xfmeng@ruc.edu.cn)[J]. , 2010, 47(5): 832-840. |
| [14] | 刘润涛, 郝忠孝,. 基于多序的空间数据索引结构——MOIS-树[J]. , 2010, 47(5): 849-857. |
| [15] | 郝忠孝, 王玉东, 何云斌,. 空间数据库平面线段近邻查询问题研究[J]. , 2008, 45(9): 1539-1545. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4207
