Ranking Distributed Probabilistic Data

Summary: Top-k ranking for distributed probabilistic data, using the expected rank across possible worlds as the criterion. Designs both communication- and computation-efficient algorithms to obtain the global top-k with minimum data transfer. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4194
Venue: SIGMOD
Year: 2009
Pagerank: 5.2711481e-05
Overall Rank: 9,425 | 35.34%
DOI: 10.1145/1559845.1559885

Incoming Non-self Citations Over Time

Authors

1. Feifei Li (Florida State University)
2. Ke Yi (Hong Kong University of Science and Technology)
3. Jeffrey Jestes (Florida State University)

BibTeX Citation

@inproceedings{li_sigmod09,
        title = {{Ranking Distributed Probabilistic Data}},
        author = {Li, Feifei and Yi, Ke and Jestes, Jeffrey},
        series = {{SIGMOD} '09},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1559845.1559885},
        url = {https://dl.acm.org/doi/10.1145/1559845.1559885},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,044	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	5.3253644e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010828372
158	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00028199923
238	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.0002369322
331	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020936658
337	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020783399
359	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.0002023153
550	Distributed Top-K Monitoring	2003	SIGMOD	0.0001663758
683	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00015005338
1,252	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011483752
1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00011025316
1,520	Conditioning Probabilistic Databases	2008	VLDB	0.00010510496
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05
2,460	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB	8.5505905e-05
2,514	From Complete to Incomplete Information and Back	2007	SIGMOD	8.4818577e-05
2,596	A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams	2006	SIGMOD	8.3627764e-05
2,813	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	8.0975254e-05
9,718	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.2323504e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	550	Distributed Top-K Monitoring	2003	SIGMOD
2	9,194	Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain Data	2023	VLDB
3	7,177	Distributed Top-N Query Processing with Possibly Uncooperative Local Systems	2003	VLDB
4	3,049	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD
5	10,657	A Rank-Based Approach to Recommender System’s Top-K Queries with Uncertain Scores	2025	SIGMOD
6	12,403	On Pruning for Top-K Ranking in Uncertain Databases	2011	VLDB
7	1,363	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD
8	1,844	Probabilistic Ranking of Database Query Results	2004	VLDB
9	3,823	Ranking Continuous Probabilistic Datasets	2010	VLDB
10	1,327	A Unified Approach to Ranking in Probabilistic Databases	2009	VLDB