Academic
Publications
Probabilistic Skylines on Uncertain Data

Probabilistic Skylines on Uncertain Data,Jian Pei,Bin Jiang,Xuemin Lin,Yidong Yuan

Probabilistic Skylines on Uncertain Data   (Citations: 109)
BibTex | RIS | RefWorks Download
Uncertain data are inherent in some important applications. Although a considerable amount of research has been dedi- cated to modeling uncertain data and answering some types of queries on uncertain data, how to conduct advanced anal- ysis on uncertain data remains an open problem at large. In this paper, we tackle the problem of skyline analysis on un- certain 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 probabilis- tic 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 ag- gressively. 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 com- plementary to each other in performance.
Conference: Very Large Data Bases - VLDB , pp. 15-26, 2007
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...This has generated much recent research in databases [7, 11, 29, 9, 10, 26, 8, 19, 2] and other areas [22, 21] on various types of systems, data structures, and optimization problems for such uncertain data...
    • ...For 0 < 1, a-skyline of P [26] consists of all uncertain data points Pi2 P such that PSP(Pi) . A subset Q P is called an "-approximate-skyline of P if for all Pi2 Q, PSP(Pi) " and for all P j 2 Pn Q, PSP(P j) + ". In this paper, we study the problems of computing skyline probabilities, computing exact and approximate -skylines, and preprocessing P into a data structure for quickly returning an approximate skyline ...
    • ...Pei et al. [26] devise several heuristics for eciently computing See [20] and [31] for other variants of this problem...

    Peyman Afshaniet al. (Approximate) uncertain skylines

    • ...General query processing techniques have been extensively studied under the possible worlds semantics [8], [9], [13], [21], and important query types with specific semantics are explored in more depth, skyline queries [28], and heavy hitters [42]...

    Jeffrey Jesteset al. Semantics of Ranking Queries for Probabilistic Data

    • ...Several research efforts have been made to develop efficient algorithms and to introduce different variants for skyline queries [18], [19], [20], [21]...

    Katia Abbaciet al. A similarity skyline approach for handling graph queries - A prelimina...

    • ...We consider uncertain data in the possible worlds semantics model [1,13,23,36], which has been extensively adopted by the recent studies on uncertain data processing, such as [5,34,39]...

    Ming Huaet al. Ranking queries on uncertain data

    • ...The skyline analysis over uncertain data has been firstly proposed in [18] where the possible world semantics is adopted to calculate the probabilities, namely skyline probabilities, of uncertain objects not being dominated by other uncertain objects...
    • ...In [18], efficient techniques are developed to retrieve uncertain objects with skyline probabilities greater than a given threshold, while [2] provides efficient techniques to compute skyline probabilities for all objects...
    • ...Probabilistic skyline on uncertain data is first tackled by Pei et al [18] where skyline objects are retrieved based on skyline probabilities...

    Xuemin Linet al. Stochastic skyline operator

Sort by: