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: 1703
Venue: PODS
Year: 2016
Pagerank: 4.3896568e-05
Overall Rank: 9,111 | 36.68%
DOI: 10.1145/2902251.2902308

Incoming Non-self Citations Over Time

Authors

1. Ronald Fagin

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,121	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	4.3878169e-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	Pagerank
5,689	Rank aggregation with ties: Experiments and Analysis	2015	VLDB	5.3706419e-05
8,042	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	4.5956381e-05
11,561	Aggregate Queries on Sparse Databases	2020	PODS	4.1905499e-05
7,512	Ranking Large Temporal Data	2012	VLDB	4.7135369e-05
7,966	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.6089395e-05
2,351	Multi-objective Query Processing for Database Systems	2004	VLDB	8.9836468e-05
10,819	GooseDB: A Database Engine that Optimally Refines Top-k Queries to Satisfy Representation Constraints	2025	VLDB	4.1905499e-05
854	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00015879917
6,816	A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems	2020	VLDB	4.9115662e-05
2,384	Comparing and Aggregating Rankings with Ties	2004	PODS	8.9177815e-05