基于索引的skyline算法研究

《基于索引的skyline算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、复旦大学博士学位论文基于索引的Skyline算法研究姓名：周红福申请学位级别：博士专业：计算机软件与理论指导教师：周傲英20070409中文摘要随着信息技术的不断发展和应用的不断深入，数据收集手段越来越丰富，海量存储也越来越普遍。由此，一种新的操作算子--skyline操作被引入了数据库领域，目的是要发现数据集中不被其他点支配的所有点的集合。所谓skyline操作中的支配，是指在数据集中，一个元组的每一属性值都不比另一元组相对应属性值“差”，而且必须至少有一个属性值比另一元组“好”。“差”和“好”并无统一的定义，它根据用户的选择和喜好有不同的语义。由上述定义可见，sky

2、line操作能够反映目标数据集的整体轮廓且有利于用户查询数据集中感兴趣的目标。然而，传统查询语言各种算子的语义和skyline操作的语义有明显的区别，而且即便组合前者的各种算子也不能高效地解决skyline计算问题。这促使我们必须研究新的高效算法来实现该种操作。近来，skyline计算在集中式数据库、分布式数据库、数据流及分类属性数据集上的良好应用前景，使其成为当前数据库界研究的最热点之一。受到了学术界和工业界的广泛关注。本文集中研究了基于索引的skyline算法。利用索引技术，分别解决了高维数据集中任意子空间上的skyline计算问题，查询数据集上8kyline点输出

3、数目过多的问题以及分类属性数据集上如何高效、动态地算出其skyline的问题。本文主要贡献如下：1．本文详细分析了在高维数据集中，计算其任意子空间的skyline所面临的困难，并考察了现有算法在处理该问题上的不足。一方面，基于索引的其他skyline算法无法高效处理或者根本不能处理高维空间任意子空间上的skyline计算；另一方面，非索引的skyline算法计算高维空间任意子空间上的skyline时。显得非常低效。在此基础上，本文提出了一个能高效计算高维空间中任意子空间]=skyline的方法：CSky(Counttheskyline)，该算法充分利用了一个新颖的数据结

4、构一InvertS结构的特性。Inverts特性之一是，通过对目标数据集进行排序，存放最可能为skyline点的数据于被优先扫描的位置，使得CSky能够高效、渐进地计算出子空间上的skyline；同时。该结构的特点还在于，计算目标数据集中任意子空间上的skyline都可以通过Ⅷ中文摘要至多扫描一遍该索引结构来完成。这样，CSky算法不仅拥有其他基于索引的skyline算法在计算固定数据集]=skyline时的高效，且使这种高效为所有子空间共享。另外，本文扩展了CSky算法以用来解决高维数据集上其他变异skyline查询。2．本文针对高维数据集．]：skyline)艮寸通

5、常过大这个较普遍的问题，提出了抽样计算skyline的算法：SSky(Sampletheskyline)。抽样skyline计算一方面能够更快地响应用户查询请求，另一方面便于用户从较少的返回结果中迅速地选择自己感兴趣的数据。为此，本文首先提出了高维数据集上“平和点集”的概念，它由各属性值中的最小值比数据集中其他点对应最小值“好”的那些点组成；然后，论证了“平和点集”中最大平和点和skyline点的对应关系，从而转化高维数据集上skyline计算为其任意子空间上的最大平和点计算。此外，通过扫描本文提出的Inverts结构，SSky计算查询数据集上所有子空间的最大平和点仅需

6、线性于数据集势的复杂度，为O(kn+k2‘)(≈<<礼)，文中论证了该结果。这表明SSky计算抽样skyline时，时间开销相当小。同时，理论分析和实验结果更进一步说明，SSb计算所得抽样skyline结果具有较合理的分布性。3．本文引入了分类属性数据集上两种不同的skyline计算问题：通常意义下的skyline计算和属性值间“序”动态变化时的skyline计算。首先，本文解决了通常意义下，分类属性数据集上的skyline计算问题。为此，我们先论证了分类属性集与格结构的对应关系。利用该对应关系，本文提出了一个基于格的LBS(Lattice-basedskylineal

7、gorithm)算法来高效处理分类属性数据集上的skyline计算问题。它映射目标数据集上所有数据为格结构中的点，从而转化skyline计算为遍历格中点的运算，这使得时间开销相当小，同时避免了每次skyline计算都需要扫描数据集的弊端。然后，本文考虑了分类属性集上的特点，提出了分类属性上属性值间“序”动态变化时skyline计算问题，郎同一属性，其值域上的全序关系因用户喜好不同而动态变化的情况。通过分析属性值上序动态变化和格中点位置关系调整间的对应关系，本文映射“序变化”为格结构中点的调整，进而将分类属性序动态变化时skyline计算问