基于Voronoi图的空间数据k-最近邻查询技术的研究

摘要

空间数据查询方法是在空间数据库、空间数据挖掘、空间拓扑关系分析、智能交通和地理信息系统等领域扮演着非常重要的角色。最近邻查询方法作为空间数据查询中的一个分支，在日常生活中同样扮演着极其重要的角色。最近邻查询方法可以从数据环境上被划分为以下两类：第一类是基于欧氏空间的查询，欧氏空间又可以分为有障碍环境查询与无障碍环境查询；另一类是基于路网环境(道路网络)上的查询。在日常生活中主要的最近邻查询都是在有障碍的环境下或者是路网环境下进行的。Voronoi图是一种关于空间划分的基本数据结构。它在解决空间查询方面有很大的潜力，不仅可以应用在地理信息系统和在线地图领域，而且还可以应用到其他的一些领域。所以本文研究的重点是将Voronoi图应用于障碍环境下的最近邻查询与路网环境下的最近邻查询及其变体查询，主要研究内容包括以下几个方面：
　　首先，从传统的障碍空间下的k-最近邻查询入手，分析了传统方法的不足，提出了障碍空间中基于Voronoi图的k-最近邻查询方法。首先是利用Voronoi图的过滤功能，较大程度地减少了被查询点个数。然后根据障碍距离和邻接生成点对候选集中的对象进行第二次筛选，最后通过计算候选集合中的点得到最终的结果。
　　其次，针对已有的在路网中的反向最近邻查询方法存在的不足，提出了利用网格Voronoi图的算法，该算法具有较好的效果。该算法是把路网划分成小的网格Voronoi图区域，然后利用网格Voronoi图的过滤功能过滤掉一些不可能成为最终结果的点。最后从可能的结果集合中找到最终的查询结果。
　　最后，针对已有的在路网中的组k-最近邻查询方法存在的不足，提出了利用网格Voronoi图的算法。该算法采用了三个步骤：处理数据集、过滤过程和精炼过程。处理数据集主要是计算查询点集的质心。过滤过程主要是提前存储可能的查询结果。精炼过程主要是从可能的结果集合中找到查询结果。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 课题研究的目的及意义

1.2 国内外研究现状

1.3 课题的来源及研究内容

第2章 Voronoi图及空间索引技术概述

2.1 Voronoi图

2.2 网格Voronoi图

2.3 空间索引技术

2.4 本章小结

第3章 障碍空间中基于Voronoi图的k-最近邻查询

3.1 相关概念与定义

3.2 过滤过程

3.3 精炼过程

3.4 障碍空间中基于Voronoi图的kNN算法描述

3.5 实验分析

3.6 本章小结

第4章 一种路网环境下的反向最近邻查询方法

4.1 数据预处理阶段

4.2 基于网格Voronoi图的反向最近邻算法描述

4.3 算法实例验证分析

4.4 本章小结

第5章 一种路网环境下的组k-最近邻查询方法

5.1 处理数据集

5.2 过滤过程

5.3 精炼过程

5.4 基于网格Voronoi图的GkNN算法

5.5 动态更新对于对组k-最近邻查询的影响

5.6 算法实例验证分析

5.7 本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢