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

刘润涛; 梁建创

doi:10.7544/issn1000-1239.2020.20190470

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

刘润涛^1,2,
梁建创¹

¹(哈尔滨理工大学理学院哈尔滨 150080)
²(哈尔滨理工大学信息与科学计算技术研究所哈尔滨 150080) (liurthar@163.com)

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

详细信息

中图分类号: TP311.13
计量
- 文章访问数: 747
- HTML全文浏览量: 1
- PDF下载量: 261
出版历程
- 发布日期: 2020-05-31

Reverse Nearest Neighbor Query Based on New Index Structure

Liu Runtao^1,2,
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)

Funds: 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.
- MSDNN-tree /
- spatial database /
- index structure /
- reverse nearest neighbor /
- query algorithm

HTML全文

参考文献(0)

施引文献(63)

期刊类型引用(12)

1.	武家辉，李科研，陈丽新，张家诺，刘帅兵，逯鹏. 神经架构搜索技术研究综述. 计算机应用研究. 2025(01): 11-18 . 百度学术
2.	刘倩男，闫佳，刘诚. 基于改进MobileNetV3的岩石薄片分类研究. 电脑知识与技术. 2025(07): 26-28 . 百度学术
3.	吴艳灵，汤宝平，邓蕾，付豪. 低通筛选优化神经架构搜索的风电齿轮箱边缘侧故障诊断方法. 机械工程学报. 2025(07): 361-372 . 百度学术
4.	宋玉红，沙行勉，诸葛晴凤，许瑞，王寒. RR-SC:边缘设备中基于随机计算神经网络的运行时可重配置框架. 计算机研究与发展. 2024(04): 840-855 . 本站查看
5.	蒋鹏程，薛羽. 基于排序得分预测的演化神经架构搜索方法. 计算机学报. 2024(11): 2522-2535 . 百度学术
6.	刘威，郭直清，王东，刘光伟，姜丰，牛英杰，马灵潇. 改进鲸鱼算法及其在浅层神经网络搜索中的权值阈值优化. 控制与决策. 2023(04): 1144-1152 . 百度学术
7.	鞠翰文，邓扬，李爱群. 桥梁结构挠度-温度-车辆荷载监测数据相关性模型. 振动与冲击. 2023(06): 79-89 . 百度学术
8.	丁熠，郑伟，耿技，邱泸谊，秦志光. 基于多层级并行神经网络的多模态脑肿瘤图像分割框架. 中国图象图形学报. 2023(07): 2182-2194 . 百度学术
9.	王上，唐欢容. 一种基于混合粒子群优化算法的深度卷积神经网络架构搜索方法. 计算机应用研究. 2023(07): 2019-2024 . 百度学术
10.	朱光辉，祁加豪，朱振南，袁春风，黄宜华. 渐进式深度集成架构搜索算法研究. 计算机学报. 2023(10): 2041-2065 . 百度学术
11.	钟运琴，朱月琴，焦守涛. 边缘大数据分析预测建模方法研究. 高技术通讯. 2022(10): 1067-1075 . 百度学术
12.	包振山，秘博闻，张文博. 基于人工经验网络架构为初始化的NAS算法. 北京工业大学学报. 2021(08): 854-862 . 百度学术