Skyline ranking for uncertain databases

Abstract

Skyline queries have been actively studied to effectively identify interesting tuples with low formulation overhead. This paper aims to support skyline queries for uncertain data with maybe confidence. Prior skyline work for uncertain data assumes that each tuple is exhaustively enumerated with all possible probabilities of alternative confidence. However, it is inappropriate to some real-life scenarios, e.g., scientific Web data or privacy-preserving data, such that each tuple is associated with a probability of existence. We thus propose novel skyline algorithms that efficiently deal with maybe uncertainty, leveraging auxiliary indexes, i.e., an R-tree or a dominance graph. We also discuss our proposed algorithms over data dependency. Our experiments demonstrate that the proposed algorithms are significantly faster than a naive method by orders of magnitude. © 2014 Elsevier Inc. All rights reserved.