论文部分内容阅读
随着信息技术的飞速发展,各行各业都迎来了大数据时代。面对如此庞大的数据量,数据管理系统显得尤其重要。数据查询处理技术作为数据管理系统中最重要的组成部分之一,可以快速地、直观地反映数据的各种特性,为用户的决策提供参考和帮助。目前为止,数据管理系统中最常见的查询有Skyline查询、最近邻查询、Top-k查询、聚集查询、Join查询、相似性查询等。其中,Skyline查询是一种重要的多维度偏好查询,在多维度决策、个性化推荐、数据挖掘等领域有着广泛的应用。Skyline查询处理问题已经得到了国内外学者的广泛关注,并将其扩展到许多不同的环境中。然而,现有的研究工作在基于空间划分的Skyline查询处理、不完整数据上的Skyline查询处理、不确定数据上的Skyline查询处理和G-Skyline查询处理等方面仍有许多不足。因此,本文主要在这四个方面进行研究,成果如下:
首先,本文研究了基于空间划分的Skyline查询处理问题。Skyline查询处理算法大致分成两类:一类是基于索引的,另一类则不需要索引结构。尽管基于索引的Skyline查询处理算法效率很高,但是索引结构的构建面临维度灾难问题,所需时间和空间代价巨大。目前最优的非索引Skyline查询处理算法是基于空间划分框架。然而,现有的基于空间划分的Skyline查询处理算法忽略了均匀划分对空间划分框架的重要性,降低了算法性能。为此,本文提出了基于空间划分的Skyline查询处理算法VMPSP。VMPSP算法通过构造虚拟中点作为划分点对集合进行递归划分,使得划分更加均匀,降低划分次数和检验点与空间划分树中Skyline点的比较次数,提高了计算Skyline的效率。本文分析了算法的时间复杂度并通过实验验证了算法的高效性。
其次,本文研究了不完整数据上的Skyline查询处理问题。数据的不完整性是实际应用中非常普遍的现象。然而,现有不完整数据上Skyline查询的定义存在严重缺陷,只关注数据点之间相同有效维度上的比较,忽略了缺失属性的问题,使得查询结果集可能为空或存在异常点,无法为用户的决策提供参考。为了克服此问题,本文利用概率模型提出了不完整数据上的概率Skyline查询处理的问题定义。通过返回k个成为Skyline的概率最大的点保证结果集大小和有效性。计算出数据点成为Skyline的概率的必要因素是确定所有不完整数据点的概率密度函数。为此,本文分别在独立的、正相关的和负相关的数据分布上构建了不完整数据模型,并利用有效属性值估计出不完整数据点的概率密度函数。为了高效地进行概率Skyline计算,本文针对三种数据分布分别提出了高效的概率Skyline查询算法SPISkyline,SPCSkyline和SPASkyline。这些算法利用裁剪策略、概率计算的优化策略和排序技术加速了概率Skyline计算。本文分析了算法时间复杂度并用实验验证了算法的高效性和可行性。
再次,本文研究了不确定数据上的Skyline查询处理问题。数据的不确定性在实际应用中普遍存在,不确定数据上的Skyline查询处理问题也得到了广泛的研究。然而,列分布式环境下不确定数据上的Skyline查询处理问题却仍未引起研究人员的关注。基于此,本文提出了三个通讯高效的列分布环境下不确定数据上的Skyline查询处理算法ASR,IASR和FSLR。在预处理阶段,服务器上的记录在每个维度上都被组织成排序的数据列并支持顺序访问和随机访问。ASR算法交替利用顺序访问和随机访问循环地检索所有排序的数据列,不断更新不确定对象的概率上界和下界,直到所有的不确定对象都已检测出是否存在Skyline结果中为止。IASR算法是在ASR基础上,通过提前终止循环访问来提高算法效率。FSLR算法先利用代价小的顺序访问获得宽松的概率上界和下界,然后再利用代价大的随机访问进一步缩紧概率上界和下界。通过此访问顺序,FSLR能够减少代价大的随机访问的次数,从而提高算法效率。本文分析了算法的通讯复杂度并用实验验证了算法的高效性。
最后,本文研究了G-Skyline查询处理问题。G-Skyline是一种基于点集的Skyline查询处理,旨在检索出所有优化点集为用户的决策提供参考。然而,随着数据维度的增高,G-Skyline结果集所包含的点集会越来越多,导致用户很难从如此庞大的结果集中选择满意的点集。因此,本文提出了k-支配G-Skyline查询,是传统的G-Skyline查询结果的一个更具有代表性的子集。由于k-支配不具有传统支配关系的传递性,导致现有的G-Skyline查询处理方法无法直接应用于计算k-支配G-Skyline查询问题。基于此,本文提出了一个两阶段k-支配G-Skyline算法。第一阶段尽可能多地裁减掉永远都不会出现在k-支配G-Skyline查询结果集中的点并用剩余的点构造lk-支配图。第二阶段利用已经构造好的lk-支配图搜索出所有的k-支配G-Skyline点集。本文提出两种搜索算法SM-P和SM-G,SM-P算法通过单个点来生成新的候选点集,而SM-G则通过祖先点集来生成新的候选点集。本文分析了算法时间复杂度并用实验验证了算法的高效性。
首先,本文研究了基于空间划分的Skyline查询处理问题。Skyline查询处理算法大致分成两类:一类是基于索引的,另一类则不需要索引结构。尽管基于索引的Skyline查询处理算法效率很高,但是索引结构的构建面临维度灾难问题,所需时间和空间代价巨大。目前最优的非索引Skyline查询处理算法是基于空间划分框架。然而,现有的基于空间划分的Skyline查询处理算法忽略了均匀划分对空间划分框架的重要性,降低了算法性能。为此,本文提出了基于空间划分的Skyline查询处理算法VMPSP。VMPSP算法通过构造虚拟中点作为划分点对集合进行递归划分,使得划分更加均匀,降低划分次数和检验点与空间划分树中Skyline点的比较次数,提高了计算Skyline的效率。本文分析了算法的时间复杂度并通过实验验证了算法的高效性。
其次,本文研究了不完整数据上的Skyline查询处理问题。数据的不完整性是实际应用中非常普遍的现象。然而,现有不完整数据上Skyline查询的定义存在严重缺陷,只关注数据点之间相同有效维度上的比较,忽略了缺失属性的问题,使得查询结果集可能为空或存在异常点,无法为用户的决策提供参考。为了克服此问题,本文利用概率模型提出了不完整数据上的概率Skyline查询处理的问题定义。通过返回k个成为Skyline的概率最大的点保证结果集大小和有效性。计算出数据点成为Skyline的概率的必要因素是确定所有不完整数据点的概率密度函数。为此,本文分别在独立的、正相关的和负相关的数据分布上构建了不完整数据模型,并利用有效属性值估计出不完整数据点的概率密度函数。为了高效地进行概率Skyline计算,本文针对三种数据分布分别提出了高效的概率Skyline查询算法SPISkyline,SPCSkyline和SPASkyline。这些算法利用裁剪策略、概率计算的优化策略和排序技术加速了概率Skyline计算。本文分析了算法时间复杂度并用实验验证了算法的高效性和可行性。
再次,本文研究了不确定数据上的Skyline查询处理问题。数据的不确定性在实际应用中普遍存在,不确定数据上的Skyline查询处理问题也得到了广泛的研究。然而,列分布式环境下不确定数据上的Skyline查询处理问题却仍未引起研究人员的关注。基于此,本文提出了三个通讯高效的列分布环境下不确定数据上的Skyline查询处理算法ASR,IASR和FSLR。在预处理阶段,服务器上的记录在每个维度上都被组织成排序的数据列并支持顺序访问和随机访问。ASR算法交替利用顺序访问和随机访问循环地检索所有排序的数据列,不断更新不确定对象的概率上界和下界,直到所有的不确定对象都已检测出是否存在Skyline结果中为止。IASR算法是在ASR基础上,通过提前终止循环访问来提高算法效率。FSLR算法先利用代价小的顺序访问获得宽松的概率上界和下界,然后再利用代价大的随机访问进一步缩紧概率上界和下界。通过此访问顺序,FSLR能够减少代价大的随机访问的次数,从而提高算法效率。本文分析了算法的通讯复杂度并用实验验证了算法的高效性。
最后,本文研究了G-Skyline查询处理问题。G-Skyline是一种基于点集的Skyline查询处理,旨在检索出所有优化点集为用户的决策提供参考。然而,随着数据维度的增高,G-Skyline结果集所包含的点集会越来越多,导致用户很难从如此庞大的结果集中选择满意的点集。因此,本文提出了k-支配G-Skyline查询,是传统的G-Skyline查询结果的一个更具有代表性的子集。由于k-支配不具有传统支配关系的传递性,导致现有的G-Skyline查询处理方法无法直接应用于计算k-支配G-Skyline查询问题。基于此,本文提出了一个两阶段k-支配G-Skyline算法。第一阶段尽可能多地裁减掉永远都不会出现在k-支配G-Skyline查询结果集中的点并用剩余的点构造lk-支配图。第二阶段利用已经构造好的lk-支配图搜索出所有的k-支配G-Skyline点集。本文提出两种搜索算法SM-P和SM-G,SM-P算法通过单个点来生成新的候选点集,而SM-G则通过祖先点集来生成新的候选点集。本文分析了算法时间复杂度并用实验验证了算法的高效性。