基于最近邻距离的空间数据索引及其查询算法研究

发布时间：2023-04-20 23:00

　　随着大数据信息时代的到来,海量化的空间数据如何处理成为一个难题,由此空间数据库技术应运而生,在GIS、地理围栏、决策支持以及设施定位等方面得到了大量的应用。其中最近邻查询和反最近邻查询作为其中最重要的操作,也是该领域学者们的研究重点。本文针对空间数据索引算法的研究主要包括三个部分:新型空间数据索引结构研究、基于新型索引结构的反最近邻查询算研究以及最近邻查询算法研究。首先,针对反最近邻问题,利用最小包围正方形和空间数据矩形间序关系的特性,提出了新的空间数据索引结构--基于最小包围正方形和最近邻距离的索引树(index tree based on the minimum bounding square and the distance of nearest neighbor,MBDNN-tree)。该索引结构利用MBSD和多种序关系良好的性质,在构建索引结构时可以将空间数据对应的MBSD分为不同的层次,每个层次(结点)都包含着空间距离相对接近的MBSD,减少了结点之间的重叠面积和无效路径的访问,从而优化其性能。通过此方式给出了新的空间数据索引结构:MBDNN-树,并给出了该树的生成算法以及...

【文章页数】：68 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 课题来源及研究背景与意义
        1.1.1 课题来源
        1.1.2 课题研究背景与意义
    1.2 空间数据索引及查询的国内外研究现状
        1.2.1 空间数据索引结构的研究现状
        1.2.2 反最近邻查询的研究现状
        1.2.3 最近邻查询的研究现状
    1.3 本文研究内容
第2章 相关基础知识
    2.1 空间数据索引技术
        2.1.1 空间数据
        2.1.2 空间数据近似表示方法
        2.1.3 空间索引方法
    2.2 反最近邻查询相关定义与性质
        2.2.1 相关定义
        2.2.2 相关性质
    2.3 最近邻查询相关定义
    2.4 空间数据间序关系
    2.5 基于测量距离的约束条件
    2.6 本章小结
第3章 基于最近邻距离的空间索引结构-MBDNN树
    3.1 MBDNN-树的结点构成
    3.2 MBDNN-树的定义
    3.3 MBDNN-树的构建
        3.3.1 预处理过程
        3.3.2 MBDNN-树的生成
    3.4 MBDNN-树的更新算法
        3.4.1 MBDNN-树的插入算法
        3.4.2 MBDNN-树的删除算法
    3.5 本章小结
第4章 基于MBDNN-树的反最近邻查询算法
    4.1 相关定理与推论
    4.2 剪枝规则
    4.3 反最近邻查询算法
    4.4 实验对比与分析
    4.5 本章小结
第5章 基于MBDNN-树的最近邻查询算法
    5.1 相关定义与定理
    5.2 剪枝规则
    5.3 最近邻查询算法
    5.4 实验对比与分析
        5.4.1 最近邻查询算法查询时间测试
        5.4.2 最近邻查询算法访问结点测试
    5.5 本章小结
结论
参考文献
攻读学位期间发表的学术论文
致谢



本文编号：3795328