Efficient Skyline Computation on Massive Incomplete Data

摘要

Incomplete skyline query is an important operation to filter out pareto-optimal tuples on incomplete data. It is harder than skyline due to intransitivity and cyclic dominance. It is analyzed that the existing algorithms cannot process incomplete skyline on massive data efficiently. This paper proposes a novel table-scan-based TSI algorithm to deal with incomplete skyline on massive data with high efficiency. TSI algorithm solves the issues of intransitivity and cyclic dominance by two separate stages. In stage 1, TSI computes the candidates by a sequential scan on the table. The tuples dominated by others are discarded directly in stage 1. In stage 2, TSI refines the candidates by another sequential scan. The pruning operation is devised in this paper to reduce the execution cost of TSI. By the assistant structures, TSI can skip majority of the tuples in phase 1 without retrieving it actually. The extensive experimental results, which are conducted on synthetic and real-life data sets, show that TSI can compute skyline on massive incomplete data efficiently.