Skyline: Stacking Optimal Solutions in Exact and Uncertain Worlds

Abstract In many applications involving multiple criteria optimal decision making, users may often want to make a personal trade-off among all optimal solutions for selecting one object that best fits their personal needs. As a key feature, skyline in a multi-dimensional space provides a minimal set of candidates for such purposes by removing every object that is not preferred by any (monotonic) utility/scoring function; that is, the skyline removes all objects not preferred by any user no matter how their preferences vary. Due to its impor-tance, the problem of skyline computation and its variants have been extensively studied in the database literature. In this paper, we provide a comprehensive survey of skyline com-putation techniques. Specifically, we first introduce the skyline computation algorithms on traditional (exact) data where each object corresponds to a point in a multi-dimensional space. Then, we discuss the skyline models and efficient algorithms to handle uncertain data which is inherent in many important applications. Finally, we briefly describe a few variants of the skyline (e.g., skycube, k-skyband and reverse skyline) in this paper. Key words: query processing; skyline; uncertain dat