论文部分内容阅读
近年来,skyline查询在多目标决策、数据挖掘、数据库可视化等方面得到广泛应用。然而在高维空间环境下,skyline查询因为返回的结果集过大而不能提供有用的信息。因此,学术界提出了k-支配skyline查询的概念。它通过弱化对“支配”的定义,使数据点间更容易产生支配关系,从而使结果集的大小保持在一个合适的范围内。在静态k-支配skyline查询问题上,现有算法要么存在建立索引开销太大问题;要么在高维空间中存在过多重复计算问题。而在连续k-支配skyline查询方面,现有算法中剪枝方式和分治策略都存在删除数据点后维护困难的问题。本文通过分析现有算法存在的缺点,结合k-支配skyline查询的内在特性,分别在静态k-支配skyline查询和连续k-支配skyline查询这两个方面提出了新的算法。本文的主要贡献可以分为以下几点:(1)提出了不支配关系的概念。两个支配能力弱的数据点之间不容易发生支配关系;两个支配能力强的数据点之间也不容易发生支配关系。本文通过计算数据点的支配能力,然后使数据点只和有可能与自己互相支配的数据点进行比较,避免与不可能产生支配关系的数据点进行不必要的比较,从而节省了大量的计算时间。(2)针对建立索引和不建立索引两类算法在进行静态k-支配skyline查询上存在的问题,本文提出了一种基于简化预排序的k-支配skyline查询算法。该算法的核心思想是引入平均数据点,并通过与之比较把各个数据点按支配能力大小进行分块,之后根据支配能力值对各分块进行排序。这样的排序不仅大幅度降低了预排序的时间,而且也很大程度减少了数据点间无意义的比较。(3)提出了准skyline点的概念。在连续k-支配skyline查询问题上,由于维护传统skyline点需要很大的计算量,所以使用传统skyline点来进行剪枝并不是很好的策略。本文提出的准skyline点的概念,准skyline数据集比传统skyline数据集更易于维护,并且其能发挥传统skyline数据集所具有的剪枝效果。因此引入准skyline思想能够很大提高k-支配skyline查询效率。(4)提出了保留支配关系的方法。由于在连续k-支配skyline查询问题上,任何数据点的更新都有可能影响到数据集的k-支配skyline点。如果每次数据点更新都重新计算k-支配skyline点是效率低下的。本文通过保留数据点之间一些重要的支配关系,当数据更新时能够很快的找到需要唤醒的数据点,从而提高了算法的时间效率。最后,通过理论分析和模拟实验使本文提出的新算法和现有算法进行比较,并进一步使本文提出的新算法应用到真实数据环境中,理论论证和实验数据都显示本文提出的新算法都比国内外现有算法更加高效。