论文部分内容阅读
随着数据采集和处理技术的发展,在传感器网络监测、医学图像管理、基于位置服务等很多应用领域产生了海量的不确定数据。如今,对不确定数据的研究受到人们越来越多的重视。为了存储和表达丰富的信息,很多实际应用中的不确定数据对象包含的不确定属性不只一个(如空间位置信息的横坐标和纵坐标),它们被称为多维不确定数据。相比于针对单一维度上不确定数据的查询处理技术,由于多维不确定数据的复杂性,面向多维不确定数据的查询在时间和空间效率方面面临着更加严峻的挑战。由于查询条件的不准确性或时态约束等也会导致查询本身变得十分复杂,甚至是NP-难问题。目前,已有的查询技术无法支持高效地解决这些针对多维不确定数据的复杂查询。如何针对带有复杂查询条件的多维不确定数据进行建模以及查询处理,是目前不确定数据管理领域中亟待解决的热点问题。本文对现存的不确定数据的查询技术进行了归纳和总结,分别对Top-κ查询、最优位置选择查询和反最近邻查询等查询处理技术进行了分析和综述。针对不同类型的多维不确定数据,在Top-κ查询、最优位置选择查询和反最近邻查询等方面提出了新的模型和解决方案。这些技术可以有效地提高多维不确定数据的查询处理效率,从而支持更复杂应用环境下的查询请求。具体地,本文对多维不确定数据库上的Top-κ查询和空间查询技术进行了深入研究,主要包括模糊Top-κ查询、多阈值模糊排序查询、组最优位置选择查询以及间隔反最近邻查询。本文提出的这四种新型查询技术涵盖了多维不确定对象(数据)的查询优化的关键问题,具体工作包括以下几个方面:(1)研究了多维连续型不确定对象上的模糊Top-κ查询。在查询条件具有模糊性的情况下,模糊Top-κ查询可以找出k个概率模糊评分值最高的对象。针对多维连续型不确定对象,本文定义的模糊Top-κ查询评分函数同时兼顾了数据的不确定性和查询条件的模糊性。同时,对面向连续型多维不确定数据的模糊Top-κ查询提出了高效的查询框架,并提出了有效的降低不确定数据维度的方法从而提高了查询效率。(2)研究了基于可能世界模型的不确定对象上的多阈值模糊排序查询。模糊Top-κ查询的评分函数对每个数据对象计算统一的评分,并返回评分最高的k个对象。与模糊Top-κ查询相比,模糊排序查询的评分函数对数据对象排在每个位置分别计算评分,并每次返回排在第j(1≤j≤k)位评分最高的对象。针对多个模糊阈值下的模糊查询条件,设计了一种新的查询多阈值模糊排序查询,此查询可以综合考虑多个模糊阈值并返回固定数量的查询结果。在运用剪枝技术来提高性能的基础上,设计了高效的查询处理算法对离散型不确定数据上的多阂值模糊排序查询进行处理。(3)研究了面向空间不确定对象的组最优位置选择查询。在最优位置选择查询方面,提出一种新颖的最优位置选择查询,即,组最优位置选择查询。该查询选择最少的位置建立服务站点来覆盖给定数据库中所有的不确定对象,同时保证覆盖误差不超过某一给定阈值。本文提出了一个高效的框架以及一系列有效的算法。(4)研究了基于马尔科夫模型的间隔反最近邻查询。在时空不确定数据库上的反最近邻查询方面,针对带有马尔科夫相关性的不确定移动对象提出间隔反最近邻查询,该查询能返回长时间对查询对象保持反最近邻关系的对象。在运用空间剪枝技术和概率剪枝技术来提高效率的基础上,又提出了高效的验证方法从而大幅度地提高了间隔反最近邻查询的效率。总之,本文针对多维不确定数据的查询技术展开研究,提供高效健壮的面向多维不确定数据的新型查询技术,支持不同应用中的查询需求。大量的实验也证明了本文提出方法的有效性和高效性。