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.3938681e-05
Overall Rank: 9,113 | 36.61%
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,123	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	4.3920263e-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
8,040	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	4.600049e-05
5,700	Rank aggregation with ties: Experiments and Analysis	2015	VLDB	5.365274e-05
11,557	Aggregate Queries on Sparse Databases	2020	PODS	4.1945683e-05
7,513	Ranking Large Temporal Data	2012	VLDB	4.7180617e-05
7,963	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.613363e-05
2,346	Multi-objective Query Processing for Database Systems	2004	VLDB	8.9919258e-05
10,814	GooseDB: A Database Engine that Optimally Refines Top-k Queries to Satisfy Representation Constraints	2025	VLDB	4.1945683e-05
859	So Who Won? Dynamic Max Discovery with the Crowd	2012	SIGMOD	0.00015870894
6,834	A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems	2020	VLDB	4.9117328e-05
2,385	Comparing and Aggregating Rankings with Ties	2004	PODS	8.9247846e-05