基于平面线段的反向最近邻查询问题研究

论文摘要

随着遥感、地理信息系统、计算机技术和通信技术的飞速发展,空间数据库技术不断走向成熟,目前已经在不同行业中得到广泛的应用。空间查询作为空间数据库不可缺少的重要组成部分,其查询效率成为空间数据库性能的瓶颈。反向最近邻查询技术作为空间数据库空间查询的一个重要技术,它具有很重要的理论和应用价值,一直是相关领域专家研究的重点。反向最近邻是在最近邻查询的基础上提出来的,目前空间数据库反向最近邻查询的查询粒度都是基于一维的数据点,这对于能被抽象为点的空间物体,对其进行反向最近邻查询能达到较好的效果,但对于一些空间物体,如航线、高速铁路等,按点的反向最近邻查询方法对其进行反向最近邻查询,其结果达不到一定的准确度。本课题主要从两个方面来研究基于平面线段的反向最近邻查询:1.对基于R树索引结构的平面线段最近邻查询方法进行了研究,将平面线段间最近距离的计算转化为点与线段间的距离来计算,以一条线段的两个端点在另一条线段的直接影响区域中的情况来划分两条线段间的位置关系,并根据两条线段的内倾与外倾关系,分为四种情况来计算线段到线段的最近距离。2.对基于平面线段的反向最近邻查询方法进行了研究,给出了平面线段反向最近邻相关定义,在分析了两种反向最近邻查询方法的索引结构基础之上,提出了一种新的索引结构Reverse-Circle-Distance-tree（Rcd-tree）,由Rcd-tree索引结构的特点,提出了平面线段反向最近邻查询定理、过滤策略和查询方法,另外给出了基于Rcd树平面线段反向最近邻查询算法的描述,并通过对算法的时间复杂度进行实验分析,实验结果证明该方法能实现平面线段的反向最近邻查询。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题研究背景
• 1.2 国内外研究现状
• 1.3 课题研究的目的和意义
• 1.3.1 课题研究的目的
• 1.3.2 课题研究的意义
• 1.4 课题来源及主要研究内容
• 1.4.1 课题来源
• 1.4.2 主要研究内容
• 第2章 空间数据库基础知识
• 2.1 空间数据特征
• 2.1.1 时空特征
• 2.1.2 多维特征
• 2.1.3 多尺度性
• 2.1.4 海量数据特征
• 2.2 空间数据模型
• 2.2.1 空间关系
• 2.2.2 空间数据类型
• 2.3 空间数据组织与管理
• 2.3.1 空间数据管理方式
• 2.3.2 空间数据引擎
• 2.3.3 空间数据组织
• 2.4 空间数据索引技术
• 2.4.1 空间检索
• 2.4.2 目标近似
• 2.4.3 查询优化处理
• 2.5 常用的空间索引技术
• 2.5.1 k-d 树
• 2.5.2 四叉树
• 2.5.3 R 树
• *树'>2.5.4 R^*树
• 2.6 本章小结
• 第3章 平面线段最近邻查询
• 3.1 空间数据点与线段在R 树中的存储
• 3.1.1 R 树及其特点
• 3.1.2 点在R 树中的存储
• 3.1.3 线段在R 树中的存储
• 3.2 平面线段间最近距离
• 3.2.1 点到线段的最近距离
• 3.2.2 线段不相交时的位置关系
• 3.2.3 线段到线段的最近距离
• 3.3 线段最近邻查询算法
• 3.3.1 两条线段不相交时位置关系的算法
• 3.3.2 查询线段与被查询线段的最近距离算法
• 3.3.3 在R 树中查询线段的最近邻算法
• 3.4 本章小结
• 第4章 平面线段反向最近邻查询
• 4.1 平面线段反向最近邻相关定义
• 4.2 Rcd 树索引结构
• 4.2.1 Rcd 树的设计思想
• 4.2.2 Rcd 树的结构
• 4.3 基于Rcd 树的平面线段反向最近邻查询
• 4.3.1 基于Rcd 树的平面线段反向最近邻查询定理
• 4.3.2 Rcd 树索引结构的特点
• 4.3.3 剪枝策略
• 4.3.4 查询方法
• 4.4 本章小结
• 第5章 平面线段反向最近邻查询算法
• 5.1 查询算法
• 5.2 插入算法
• 5.3 删除算法
• 5.4 算法分析
• 5.5 实验结果
• 5.6 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢