基于R-树的最近邻查询研究

论文摘要

最近邻查询是空间数据查询领域中最重要的查询技术之一,在地理信息系统（GIS）,计算机辅助设计与制造（CAD/CAM）,智能识别系统,多媒体的应用等各个方面都有广泛的应用。同时随着科学技术的快速发展,对最近邻查询的效率的要求也越来越高,本文从研究最常用的空间索引技术R-树出发,对R-树的查找算法、插入算法、删除算法等进行了探讨,给出了相应的伪代码,并运用相关的性质对R-树的各种算法过程进行优化。本文研究的是最近邻查询中两个应用较广泛的方面,K最近邻（KNN）查询和障碍最近邻查询（ONN）。在KNN中我们研究了静态的K最近邻查询和动态的K最近邻查询,并给出了相应的算法、伪代码和算法解释。然后我们把空间数据索引技术R-树应用到KNN的查询算法中,运用最小距离（MINDIST）和最小最大距离（MINMAXDIST）来对R树的结点进行排序和剪枝,建立了用于查询的剪枝规则。并给出了基于R-树的K最近邻查询算法,给出了剪枝过程的策略和算法的伪代码。在对障碍最近邻的研究中,把实际应用中的障碍看作多边形。并给出了求解多边形可视点的算法,然后只需考虑障碍多边形的可视点,过滤掉了大部分障碍点,再运用R-树的查询知识对这些可视点进行分类,并求出其最短路径,所得的最短路径就是所求的点与点之间的障碍距离。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究的目的与意义
• 1.2 国内外研究现状分析
• 1.2.1 基于R-树的空间索引现状
• 1.2.2 最近邻查询现状
• 1.3 课题来源
• 1.4 本文主要研究内容
• 第2章 空间数据库索引R-树
• 2.1 R-树的定义
• 2.2 R-树的相关算法
• 2.2.1 R-树的查找算法
• 2.2.2 R-树的插入算法
• 2.2.3 R-树的删除算法
• 2.2.4 R-树的算法总结
• 2.3 R-树索引的优化
• 2.4 本章小结
• 第3章 基于R-树的K 最近邻查询
• 3.1 前言
• 3.2 静态KNN 的查询算法
• 3.3 动态KNN 的查询
• 3.4 R-树的KNN 查询算法
• 3.4.1 排序和剪枝过程
• 3.4.2 K 最近邻分支界限算法
• 3.5 本章小结
• 第4章 基于R-树的障碍最近邻（ONN）查询
• 4.1 ONN 简介
• 4.2 相关工作
• 4.3 可视点的算法
• 4.3.1 基本概念
• 4.3.2 算法描述
• 4.3.3 时间复杂度分析
• 4.4 计算{p, q}之间的最短障碍距离（ONN）
• 4.4.1 寻找{p, q}的障碍路径定义
• 4.4.2 根据R-树来计算{p, q}之间的障碍最近邻
• 4.5 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢