BSkyTree: Scalable Skyline Computation Using A Balanced Pivot Selection ∗

Skyline queries have gained a lot of attention for multi-criteria analysis in large-scale datasets. While existing sky-line algorithms have focused mostly on exploiting data dom-inance to achieve efficiency, we propose that data incom-parability should be treated as another key factor in opti-mizing skyline computation. Specifically, to optimize both factors, we first identify common modules shared by exist-ing non-index skyline algorithms, and then analyze them to develop a cost model to guide a balanced pivot point selec-tion. Based on the cost model, we lastly implement our balanced pivot selection in two algorithms, BSkyTree-S and BSkyTree-P, treating both dominance and incomparability as key factors. Our experimental results demonstrate that proposed algorithms outperform state-of-the-art skyline al-gorithms up to two orders of magnitude