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: 1500
Venue: PODS
Year: 2009
Pagerank: 4.3849295e-05
Overall Rank: 9,165 | 36.25%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Mikhail J. Atallah
2. Yinian Qi

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,929	Processing of Probabilistic Skyline Queries Using MapReduce	2015	VLDB	4.1945683e-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
101	ULDBs: Databases with Uncertainty and Lineage	2006	VLDB	0.0004955674
467	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00022443768
706	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00017845469
1,179	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013457451
1,542	Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases	2008	VLDB	0.00011456321
1,586	Indexing Multi-Dimensional Uncertain Data with Arbitrary Probability Density Functions	2005	VLDB	0.00011250856
1,707	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010816111
2,308	Efficient Indexing Methods for Probabilistic Threshold Queries over Uncertain Data	2004	VLDB	9.0591406e-05
2,454	Efficient Computation of Reverse Skyline Queries	2007	VLDB	8.778281e-05
2,500	Efficient Skyline Computation over Low-Cardinality Domains	2007	VLDB	8.6457563e-05
3,632	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD	6.9009547e-05
4,509	Privacy Skyline: Privacy with Multidimensional Adversarial Knowledge	2007	VLDB	6.1270304e-05
8,372	URank: Formulation and Efficient Evaluation of Top-k Queries in Uncertain Databases	2007	SIGMOD	4.532996e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,479	On Dominating Your Neighborhood Profitably	2007	VLDB	4.1945683e-05
12,269	Efficient Skyline Evaluation over Partially Ordered Domains	2010	VLDB	4.1945683e-05
262	Efficient Progressive Skyline Computation	2001	VLDB	0.00029987552
1,575	Efficient Computation of the Skyline Cube	2005	VLDB	0.00011286884
3,632	Monochromatic and Bichromatic Reverse Skyline Search over Uncertain Databases	2008	SIGMOD	6.9009547e-05
914	Finding k-Dominant Skylines in High Dimensional Space	2006	SIGMOD	0.00015387584
11,929	Processing of Probabilistic Skyline Queries Using MapReduce	2015	VLDB	4.1945683e-05
5,695	Scalable Skyline Computation Using Object-based Space Partitioning	2009	SIGMOD	5.3681018e-05
1,179	Probabilistic Skylines on Uncertain Data	2007	VLDB	0.00013457451
9,866	Skyline Queries with Noisy Comparisons	2015	PODS	4.2675549e-05