Efficient sort-based skyline evaluation
Efficient sort-based skyline evaluation
复制标题
DOI：
10.1145/1412331.1412343
复制
发表时间：
2008-11
期刊：
影响因子：
--
通讯作者：
Ilaria Bartolini;P. Ciaccia;M. Patella
中科院分区：
文献类型：
--
作者：
Ilaria Bartolini;P. Ciaccia;M. Patella
Skyline查询计算关系中的Pareto最优元组的集合，也就是说，这些元组不受同一关系中任何其他元组的支配。虽然已经提出了几种算法来有效地评估天际线查询，他们要么需要的关系已经被索引，或必须执行的所有元组的优势测试，以确定结果。在这篇文章中，我们介绍了salsa，一种新的天际线算法，利用预排序的输入数据，以便有效地限制要读取和比较的元组的数量的想法。当skyline查询在不理解skyline语义的系统上执行时，或者当skyline逻辑在具有有限功率和/或带宽的客户端上运行时，这使得salsa也具有吸引力。我们证明，如果考虑对称排序函数，要读取的元组的数量是最小化的排序数据根据“最小坐标，”minC，标准，和性能可以进一步提高，如果数据分布是已知的，并使用非对称排序函数。合成和真实的数据集上获得的实验结果表明，莎莎一贯优于国家的最先进的顺序天际线算法，其性能可以准确地预测。
Skyline queries compute the set of Pareto-optimal tuples in a relation, that is, those tuples that are not dominated by any other tuple in the same relation. Although several algorithms have been proposed for efficiently evaluating skyline queries, they either necessitate the relation to have been indexed or have to perform the dominance tests on all the tuples in order to determine the result. In this article we introduce salsa, a novel skyline algorithm that exploits the idea of presorting the input data so as to effectively limit the number of tuples to be read and compared. This makes salsa also attractive when skyline queries are executed on top of systems that do not understand skyline semantics, or when the skyline logic runs on clients with limited power and/or bandwidth. We prove that, if one considers symmetric sorting functions, the number of tuples to be read is minimized by sorting data according to a “minimum coordinate,” minC, criterion, and that performance can be further improved if data distribution is known and an asymmetric sorting function is used. Experimental results obtained on synthetic and real datasets show that salsa consistently outperforms state-of-the-art sequential skyline algorithms and that its performance can be accurately predicted.