A Tour of Lattice-Based Skyline Algorithms

M. Endres, L. Rudenko

erschienen 2018 In M. K. Habib (Eds.): Emerging Investigation in Artificial Life Research and Development, IGI Global


A Skyline query retrieves all objects in a dataset that are not dominated by other objects according to some given criteria. There exist many Skyline algorithms which can be classified into generic, index-based, and lattice-based algorithms. This chapter takes a tour through lattice-based Skyline algorithms. It summarizes the basic concepts and properties, presents high-performance parallel approaches, shows how one overcomes the low-cardinality restriction of lattice structures, and finally presents an application on data streams for real-time Skyline computation. Experimental results on synthetic and real datasets show that lattice-based algorithms outperform state-of-the-art Skyline techniques, and additionally have a linear runtime complexity.