空间数据库中基于R-树的连续最近邻查询方法研究

论文摘要

空间数据库已广泛地应用于地理信息系统（GIS）、计算机辅助设计与制造（CAD/CAM）和医学图像等多个领域。最近邻查询是空间数据库中非常重要的一种查询,例如一辆正在高速公路上行驶的汽车司机很想找到此时离他最近的加油站。连续最近邻查询是一种更复杂但是同等重要的查询,比如还是在高速公路上行驶的汽车司机,他可能想知道在某一段路途上的最近加油站,这个查询的结果就是一个包含该道路上不同路段区间及相应的最近加油站的集合。空间索引技术是空间数据库中进行高效查询的关键,连续最近邻的查询实现依赖于空间索引技术。R-树及其变体是最常用的空间索引技术,R-树是一种高度平衡的树,该树由中间结点和叶结点组成,实际数据对象的最小外包矩形存储在叶结点中,中间结点通过聚集其低层结点的外包矩形形成。本课题分析了当前已有的几种连续最近邻查询方法,其中以Y.Tao等人的基于R-树的查询算法最为有效,该算法的主要思想是寻找那些最近邻发生变化的点——分割点,只需一次遍历R-树就可以完成查询。该算法的主要缺点是结点访问量没有优化。本文主要是在该算法的基础上进行优化,提出了一条新的处理R-树中结点的规则,阐述了优化后算法的主要思想,给出了核心算法的伪代码,并结合实例分析了算法的执行过程,最后通过模拟实验的方法对两个算法进行了性能比较与分析。实验结果表明,优化后的算法在没有增加CPU代价的基础上确实减少了结点访问量,使原有算法得到了优化。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景和意义
• 1.2 国内外研究现状
• 1.3 课题的来源及研究内容
• 1.3.1 课题来源
• 1.3.2 研究的基本内容
• 1.4 本文的组织结构
• 第2章 空间索引技术概述
• 2.1 空间数据组织
• 2.1.1 空间数据的特征
• 2.1.2 空间数据模型
• 2.1.3 空间数据的目标近似
• 2.1.4 空间索引的需求
• 2.1.5 空间索引技术的分类
• 2.2 常用的空间索引技术
• 2.2.1 KD 树及其变形树
• 2.2.2 四叉树及其变形树
• 2.2.3 R-树及其变形树
• 2.3 本章小结
• 第3章 R-树的定义及其主要操作算法
• 3.1 R-树的定义
• 3.2 R-树的主要操作算法
• 3.2.1 查找算法
• 3.2.2 插入算法
• 3.2.3 删除算法
• 3.2.4 分裂算法
• 3.3 本章小结
• 第4章 连续最近邻查询及其方法
• 4.1 问题描述
• 4.2 问题特征
• 4.3 基于R-树的CNN 查询算法
• 4.3.1 中间结点的删剪和处理规则
• 4.3.2 P 中结点的处理方法
• 4.4 本章小结
• 第5章 查询算法的优化研究
• 5.1 CNN 算法的不足与改进
• 5.2 优化算法实现的主要过程
• 5.2.1 算法难点分析
• 5.2.2 算法总体思路
• 5.2.3 修剪和重排队列
• 5.2.4 算法示例
• 5.3 算法性能比较与分析
• 5.3.1 实验环境
• 5.3.2 模拟环境中的算法实现
• 5.3.3 算法性能比较
• 5.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的学术论文
• 致谢