An almost Linear I/O Algorithm for Skyline Query
Xiangquan Gui, Yuanping Zhang, Xiaohong Hao · Journal of Software · 2010
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. consider the point (hotel) in the dot line. Because that you can always find a point (hotel) in the dot line, either the price is cheaper or the distance is closer to the beach. Then, we say those points in the dot line dominate other points and can not be dominated by each other. Those points make up the result set of Skyline query. Basing on the Skyline query, the travelers can make decisions easily according to his preference from the Skyline set whose size is much smaller than that of original database. Index Terms—skyline query, skyline point, external memory algorithm I.