Comparing and Aggregating Rankings with Ties

Summary: Proposes principled metrics for comparing partial rankings with ties, gives efficient algorithms to compute them, and proves constant-factor relationships among the metrics. Formulates aggregation objectives and presents a database-access-aware algorithm that reads near-minimal entries to compute top-k of a near-optimal aggregate. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1307
Venue: PODS
Year: 2004
Pagerank: 8.291138e-05
Overall Rank: 2,652 | 81.81%
DOI: 10.1145/1055558.1055568

Incoming Non-self Citations Over Time

Authors

1. Ronald Fagin (IBM)
2. Ravi Kumar (IBM)
3. Mohammad Mahdian (IBM; Massachusetts Institute of Technology)
4. D. Sivakumar (IBM)
5. Erik Vee (IBM; University of Washington)

BibTeX Citation

@inproceedings{fagin_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Comparing and Aggregating Rankings with Ties}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055568},
        doi = {10.1145/1055558.1055568},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fagin, Ronald and Kumar, Ravi and Mahdian, Mohammad and Sivakumar, D. and Vee, Erik},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,526	Ordering the Attributes of Query Results	2006	SIGMOD	0.00010491673
2,683	Mining Search Engine Query Logs via Suggestion Sampling	2008	VLDB	8.2608808e-05
3,049	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.8151597e-05
4,622	Context-Sensitive Ranking	2006	SIGMOD	6.6014783e-05
6,717	Rank aggregation with ties: Experiments and Analysis	2015	VLDB	5.795458e-05
7,642	A System for Management and Analysis of Preference Data	2014	VLDB	5.5765908e-05
11,850	Top-k Queries over Digital Traces	2019	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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
690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.0001492934

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,285	Rank Discovery From Web Databases	2013	VLDB
2	8,944	Efficient and Effective Metasearch for Text Databases Incorporating Linkages among Documents	2001	SIGMOD
3	1,844	Probabilistic Ranking of Database Query Results	2004	VLDB
4	7,286	Efficient Computation of Quantiles over Joins	2023	PODS
5	690	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
6	2,211	Relational link-based ranking	2004	VLDB
7	466	Automated Ranking of Database Query Results	2003	CIDR
8	12,386	Efficient Rank Join with Aggregation Constraints	2011	VLDB
9	7,934	Ranking Large Temporal Data	2012	VLDB
10	6,717	Rank aggregation with ties: Experiments and Analysis	2015	VLDB