An almost Linear I/O Algorithm for Skyline Query

Abstract

Skyline query processing has recently received a lot of attention in database community. Even though there existed several algorithms in the field of skyline query, none of them has linear I/O complexity. In this paper, the existed algorithms have been summarized, and a new kind of external memory skyline query algorithm has been presented. Moreover, the reliability of algorithm has been validated from experiments and theory, the I/O complexity and the inner memory complexity of the algorithm is both almost linear.