空间数据库中移动对象的连续最近邻查询研究

论文摘要

空间数据库的重要性日益增加,其应用的范围已远远超出传统的GIS(geographic information system)领域。最近邻居查找在空间数据库中占据着重要的位置。在传统的最近邻居搜索方法中查询点是静止的。由于近年来无线通讯以及追踪移动对象位置技术获得了大力发展,因此动态对象发出的查询请求成为新的研究热点。连续最近邻(CNN,continuous nearest neighbor)查询是空间数据库中一种非常重要的查询,它用来查询一给定轨迹上每个点的最近邻,作为最近邻查询的一种扩展,随着卫星定位系统和无线通讯技术的快速发展,跟踪并记录移动对象的位置成为可能,使得CNN查询成为研究的重点和难点。从空间数据库中获得数据的有效方法经常是通过使用索引来完成的。空间索引的基本思想,实际上也是所有的空间查询过程的基本思想,就是对近似的使用。这种方法可以让索引结构按照一个或多个空间码来管理对象,这些空间码是比对象本身更简单的几何对象。一个最基本的例子是外包框(围住对象的与坐标轴平行的最小矩形)。本课题分析了当前已经存在的几种连续最近邻查询方法,由于目前为止连续最近邻查询方法中最有效的算法就是2002年Tao提出的CNN算法,所以将该算法的方法进行了详细的介绍。以往的研究成果大都是针对二维空间中的连续最近邻查询的,但在现实生活中,人们周围的世界是以三维空间的形式存在的,为了弥补这个缺憾,提出了三维空间中的连续最近邻查询来满足更高的查询需求。提出了垂直平分面、分割点和邻接球的概念,并基于R树实现了三维空间中的CNN查询算法,对空间数据的海量性,利用剪枝规则和空间索引结构减少了结点的访问数量,大大的提高了查询效率。给出了核心算法的相关伪代码,结合具体实例分析了算法的执行过程,最后通过模拟实验的结果对算法的性能进行了分析。

论文目录

• 摘要
• Abstract
• 目录
• 第1章 绪论
• 1.1 研究背景和意义
• 1.2 国内外研究现状
• 1.2.1 基本概念
• 1.2.2 空间索引结构
• 1.2.3 最近邻查询
• 1.2.4 连续最近邻查询
• 1.2.5 移动对象历史轨迹的最近邻居查询
• 1.3 课题的来源及研究内容
• 1.3.1 课题来源
• 1.3.2 研究的基本内容
• 1.4 本文的组织结构
• 第2章 空间数据库相关理论简介
• 2.1 空间数据库的应用与地理信息系统
• 2.1.1 空间数据库的应用
• 2.1.2 地理信息系统
• 2.2 空间概念和数据模型
• 2.2.1 空间概念
• 2.2.2 数据模型
• 2.3 空间存储和索引
• 2.3.1 空间存储
• 2.3.2 空间索引
• 2.4 查询处理与优化
• 2.4.1 查询处理
• 2.4.2 查询优化
• 2.5 空间网络数据库
• 2.6 空间数据挖掘
• 2.7 空间数据库发展趋势
• 2.8 本章小节
• 第3章 连续最近邻查询
• 3.1 问题描述
• 3.2 相关工作
• 3.3 问题特征
• 3.4 连续最近邻查询的剪枝策略
• 3.4.1 中间结点的剪枝策略
• 3.4.2 数据点的剪枝策略
• 3.5 CNN的分裂点划分
• 3.5.1 分裂点的初始划分
• 3.5.2 分裂点的修正
• 3.6 本章小结
• 第4章 三维空间中的连续最近邻查询
• 4.1 问题的定义与描述
• 4.2 三维空间CNN查询
• 4.2.1 剪枝策略
• 4.2.2 三维空间连续最近邻查询算法及其复杂度
• 4.3 实验
• 4.4 本章小结
• 结论
• 参考文献
• 攻读硕士期间发表的论文