Computing All Skyline Probabilities for Uncertain Data

Summary: First worst-case sub-quadratic algorithm to compute skyline probabilities for all tuples in uncertain databases, removing reliance on thresholding so low-probability but consequential items are preserved. Uses space-partitioning plus dominance-counting as core techniques; experimentally validated. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1499
Venue: PODS
Year: 2009
Pagerank: 5.289545e-05
Overall Rank: 9,323 | 36.04%
DOI: 10.1145/1559795.1559837

Incoming Non-self Citations Over Time

Authors

1. Mikhail J. Atallah (Purdue University)
2. Yinian Qi (Purdue University)

BibTeX Citation

@inproceedings{atallah_pods09,
        address = {New York, NY, USA},
        series = {{PODS} '09},
        title = {{Computing All Skyline Probabilities for Uncertain Data}},
        url = {https://dl.acm.org/doi/10.1145/1559795.1559837},
        doi = {10.1145/1559795.1559837},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Atallah, Mikhail J. and Qi, Yinian},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,127	Processing of Probabilistic Skyline Queries Using MapReduce	2015	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
78	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.00036571789
359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.0002023153
683	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015005338
1,097	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00012181027
1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00011025316
1,486	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00010625076
1,605	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00010229844
1,847	Efficient Computation of Reverse Skyline Queries	2007	VLDB	9.6252055e-05
2,062	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.24085e-05
2,434	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.5839844e-05
3,139	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD	7.7188328e-05
4,037	Privacy Skyline: Privacy with Multidimensional Adversarial Knowledge	2007	VLDB	6.9431497e-05
8,345	URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases	2007	SIGMOD	5.4474663e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,672	On Dominating Your Neighborhood Profitably	2007	VLDB
2	12,464	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB
3	243	Efficient Progressive Skyline Computation	2001	VLDB
4	1,360	Efficient Computation of the Skyline Cube	2005	VLDB
5	3,139	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD
6	792	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD
7	12,127	Processing of Probabilistic Skyline Queries Using MapReduce	2015	VLDB
8	5,455	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD
9	1,097	Probabilistic Skylines on Uncertain Data	2007	VLDB
10	10,030	Skyline Queries with Noisy Comparisons	2015	PODS