Efficient sort-based skyline evaluation

摘要: Skyline queries compute the set of Pareto-optimal tuples in a relation, that is, those are not dominated by any other tuple same relation. Although several algorithms have been proposed for efficiently evaluating skyline queries, they either necessitate relation to indexed or perform dominance tests on all order determine result. In this article we introduce salsa, novel algorithm exploits idea presorting input data so as effectively limit number be read and compared. This makes salsa also attractive when executed top systems do understand semantics, logic runs clients with limited power and/or bandwidth. We prove that, if one considers symmetric sorting functions, is minimized according “minimum coordinate,” minC, criterion, performance can further improved distribution known an asymmetric function used. Experimental results obtained synthetic real datasets show consistently outperforms state-of-the-art sequential its accurately predicted.