论文部分内容阅读
空间数据库的研究始于20世纪70年代的地图制图与遥感图像处理领域,其目的是为了有效地利用卫星遥感资源迅速绘制出各种专题地图。随着地理信息系统、计算机辅助设计与制造、机器人、多媒体系统、数字地球、移动通信及定位服务等领域的发展,对空间数据库的研究越来越受到人们的重视。特别是基于位置的服务,为空间数据库上的数据处理带来了巨大的挑战。如何对位置服务中的对象进行高效查询处理,是决定空间数据库应用前景的关键问题之一,得到了学术界和产业界的广泛关注。目前,已有一些针对位置服务应用的空间查询处理技术的相关研究。由于测量手段的不准确性以及数据本身的性质导致某些空间应用中的查询对象具有不确定性,如何针对一些新型查询类型中具有不确定性的目标对象进行建模以及查询处理,是目前空间数据库领域中亟待解决的热点问题。 本文对空间数据管理中的不确定性现象和问题进行了归纳和总结,并对空间数据库中不确定性数据管理的研究现状进行了分析和综述。我们将空间对象的不确定性在宏观上分为位置不确定性和存在不确定性,针对这些不确定性,在索引建立,最近对查询及组近邻查询等方面提出了新的模型和解决方法,建立了一套有特色的处理框架。这些技术可以有效的提高空间数据库系统的数据管理能力和处理效率,从而支持复杂环境下的新型空间查询应用。 具体的,本文对多种不同类型的空间查询处理技术进行了深入研究。这些查询包括最近对查询、范围最近对查询、组最近邻查询及组最近组查询等,涵盖了空间数据库中面向不确定对象的数据建模、索引构建和查询优化的关键问题,主要工作包括以下几个方面: (1)研究了空间数据库中面向位置不确定对象的最近对查询问题,提出了Top-K概率最近邻查询处理算法以及概率阈值最近邻查询处理算法。对空间数据库中的位置不确定对象的特点进行了分析,建立了相应的数据模型,并提出了一种有效的聚簇索引结构。基于索引结构以及最近对查询特点,提出并证明了最近对查询过程中可采用的优化策略,并将这些优化策略有效地应用到具体的查询处理算法中,提高了概率最近对查询处理效率。 (2)研究了面向位置不确定对象的范围最近对查询问题,提出了带有两种范围约束的概率最近对查询处理算法。对空间数据库中面向位置不确定对象的范围最近对查询处理方法进行了研究。建立了基于U树结构的聚簇U树索引,提出了面向位置不确定对象范围最近对查询定义。在运用空间剪枝技术和概率剪枝技术来提高性能的基础上,设计了高效查询处理算法对带有强范围约束和弱范围约束的范围最近对查询进行高效处理,在保证查询的准确性的同时减少了磁盘访问。 (3)研究了空间数据库中面向存在不确定对象的组最近邻查询问题,提出了概率组最近邻查询处理算法。提出了基于存在不确定性的数据模型,并在此模型的基础上,设计了一种扩展式R树索引,用以大量减少概率组最近邻查询处理的时间。此外,根据存在不确定对象的特点,设计了两种基于排他概率的查询处理方法,即基于剪枝集和基于候选集的查询处理算法,从而使其即满足查询准确性要求又提高了查询处理效率。 (4)研究了约束组最近组查询问题,并分别给出了面向确定对象的基本约束组最近组查询算法和面向存在不确定对象的概率约束组最近组查询算法。根据某些特殊应用的需求,在组最近组查询的基础上给出了约束组最近组的查询语义。研究了一种基于约束聚簇的约束组最近组查询方法,并通过高效剪枝技术提高了查询效率。在面向确定对象的约束组最近组查询基础上,提出两种面向存在不确定对象的概率约束组最近组查询语义,并给出了相应查询处理方法以减少约束组最近组查询的搜索代价。 总之,本文从空间查询中涉及到的不确定对象的典型特征和挑战出发,针对空间不确定数据的查询处理技术展开研究,如索引构建、查询优化技术等,从而提供高效健壮的空间中面向不确定对象的新型查询处理技术,支持各种具有特殊要求的空间数据查询应用。本文的研究提升了用户对不确定空间信息的获知能力,为地震救援等具有特殊需求的实际应用提供了有力的支持。