An almost linear I/O algorithm for skyline query

作者：Gui Xiangquan^*; Zhang Yuanping; Hao Xiaohong

来源：Journal of Software, 2010, 5(2): 235-242.

DOI：10.4304/jsw.5.2.235-242

• Database community
• External memory
• External memory algorithms
• I/O-complexity
• Memory complexity
• Skyline point
• Skyline query

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.

• 出版日期2010