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

摘要

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

目录

声明

摘要

第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 本章小结

结论

参考文献

攻读硕士期间发表的论文

致谢