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: hf62e4e5c13e1b7e9
Venue: PODS
Year: 2004
Pagerank: 8.1063128e-05
Overall Rank: 2,709 | 81.79%
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,557	Ordering the Attributes of Query Results	2006	SIGMOD	0.00010266055
2,736	Mining Search Engine Query Logs via Suggestion Sampling	2008	VLDB	8.0758355e-05
3,105	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.6445188e-05
4,705	Context-Sensitive Ranking	2006	SIGMOD	6.4591302e-05
6,850	Rank aggregation with ties: Experiments and Analysis	2015	VLDB	5.6654235e-05
7,795	A System for Management and Analysis of Preference Data	2014	VLDB	5.4514671e-05
12,150	Top-k Queries over Digital Traces	2019	SIGMOD	4.9793485e-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.0010679641
674	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD	0.00014886692

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,108	Efficient and Effective Metasearch for Text Databases Incorporating Linkages among Documents	2001	SIGMOD
2	12,576	Rank Discovery From Web Databases	2013	VLDB
3	1,886	Probabilistic Ranking of Database Query Results	2004	VLDB
4	7,435	Efficient Computation of Quantiles over Joins	2023	PODS
5	674	Efficient Similarity Search and Classification via Rank Aggregation	2003	SIGMOD
6	2,254	Relational link-based ranking	2004	VLDB
7	474	Automated Ranking of Database Query Results	2003	CIDR
8	12,677	Efficient Rank Join with Aggregation Constraints	2011	VLDB
9	8,102	Ranking Large Temporal Data	2012	VLDB
10	6,850	Rank aggregation with ties: Experiments and Analysis	2015	VLDB