Optimal Score Aggregation Algorithms

Summary: Introduces the 10-line Threshold Algorithm for top-k over voters×candidates with monotone score aggregators (e.g., mean/median) in the sorted-access + random-access model, minimizing data accesses. Proves instance-optimality—optimal in every case—earning the Godel Prize. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1702
Venue: PODS
Year: 2016
Pagerank: 5.2978375e-05
Overall Rank: 9,251 | 36.54%
DOI: 10.1145/2902251.2902308

Incoming Non-self Citations Over Time

Authors

1. Ronald Fagin (IBM)

BibTeX Citation

@inproceedings{fagin_pods16,
        address = {New York, NY, USA},
        series = {{PODS} '16},
        title = {{Optimal Score Aggregation Algorithms}},
        url = {https://dl.acm.org/doi/10.1145/2902251.2902308},
        doi = {10.1145/2902251.2902308},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Fagin, Ronald},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,172	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.3092396e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,528	Aggregate Queries on Sparse Databases	2020	PODS
2	6,717	Rank aggregation with ties: Experiments and Analysis	2015	VLDB
3	8,029	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB
4	7,934	Ranking Large Temporal Data	2012	VLDB
5	8,281	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
6	2,932	Multi-objective Query Processing for Database Systems	2004	VLDB
7	11,041	GooseDB: A Database Engine that Optimally Refines Top-k Queries to Satisfy Representation Constraints	2025	VLDB
8	743	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD
9	6,786	A Unified Optimization Algorithm For Solving “Regret-Minimizing Representative” Problems	2020	VLDB
10	2,652	Comparing and Aggregating Rankings with Ties	2004	PODS