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: h1896a721c9ad65a9
Venue: SIGMOD
Year: 2009
Pagerank: 5.1334081e-05
Overall Rank: 9,644 | 35.36%
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,248	Threshold Query Optimization for Uncertain Data	2010	SIGMOD	5.1862157e-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.0010688884
162	Robust and Efficient Fuzzy Match for Online Data Cleaning	2003	SIGMOD	0.00027626077
245	MCDB: A Monte Carlo Approach to Managing Uncertain Data	2008	SIGMOD	0.00023188414
340	Trio: A System for Data, Uncertainty, and Lineage	2006	VLDB	0.00020548826
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020486383
371	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00019776963
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016238411
699	MYSTIQ: A system for finding more answers by using probabilities	2005	SIGMOD	0.00014645232
1,285	Streaming Pattern Discovery in Multiple Time-Series	2005	VLDB	0.00011189681
1,403	Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach	2008	SIGMOD	0.00010753743
1,551	Conditioning Probabilistic Databases	2008	VLDB	0.00010257014
2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.3988741e-05
2,509	Exploiting Shared Correlations in Probabilistic Databases	2008	VLDB	8.3500835e-05
2,549	From Complete to Incomplete Information and Back	2007	SIGMOD	8.2889756e-05
2,658	A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams	2006	SIGMOD	8.1455298e-05
2,880	KLEE: A Framework for Distributed Top-k Query Algorithms	2005	VLDB	7.8948229e-05
9,931	Sharing Aggregate Computation for Distributed Queries	2007	SIGMOD	5.0956239e-05

Semantically Similar Papers

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