Probabilistic skylines on uncertain data

TLDR

Uncertain data are common in many applications, yet advanced analysis such as skyline queries remains largely unsolved, especially for large datasets. This work addresses skyline analysis on uncertain data. We introduce a probabilistic skyline model with a p‑skyline and present two efficient algorithms—a bottom‑up method that prunes using selected instances and a top‑down method that recursively partitions and aggressively prunes subsets. Experiments on real NBA player data and synthetic benchmarks demonstrate that probabilistic skylines are valuable and that the two algorithms perform efficiently and complement each other on large datasets.

Abstract

Uncertain data are inherent in some important applications. Although a considerable amount of research has been dedicated to modeling uncertain data and answering some types of queries on uncertain data, how to conduct advanced analysis on uncertain data remains an open problem at large. In this paper, we tackle the problem of skyline analysis on uncertain data. We propose a novel probabilistic skyline model where an uncertain object may take a probability to be in the skyline, and a p-skyline contains all the objects whose skyline probabilities are at least p. Computing probabilistic skylines on large uncertain data sets is challenging. We develop two efficient algorithms. The bottom-up algorithm computes the skyline probabilities of some selected instances of uncertain objects, and uses those instances to prune other instances and uncertain objects effectively. The top-down algorithm recursively partitions the instances of uncertain objects into subsets, and prunes subsets and objects aggressively. Our experimental results on both the real NBA player data set and the benchmark synthetic data sets show that probabilistic skylines are interesting and useful, and our two algorithms are efficient on large data sets, and complementary to each other in performance.