Optimal Aggregation Algorithms for Middleware [Extended Abstract]
Summary: Introduces TA, proved instance-optimal for top-k under any monotone aggregation on every database with only constant-size buffers. Gives optimal variants when random access is costly/impossible and contrasts TA's deterministic worst-case optimality and low memory vs. Fagin's Algorithm. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Ronald Fagin (IBM)
- 2. Amnon Lotem (University of Maryland)
- 3. Moni Naor (Weizmann Institute of Science)
BibTeX Citation
@inproceedings{fagin_pods01,
address = {New York, NY, USA},
series = {{PODS} '01},
title = {{Optimal Aggregation Algorithms for Middleware [Extended Abstract]}},
url = {https://dl.acm.org/doi/10.1145/375551.375567},
doi = {10.1145/375551.375567},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Fagin, Ronald and Lotem, Amnon and Naor, Moni},
year = {2001}
}Incoming Citations (Sorted by Pagerank)
Showing 44 of 244 citing papers.
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 |
|---|---|---|---|---|
| 108 | Optimizing Multi-Feature Queries for Image Databases | 2000 | VLDB | 0.00033228866 |
| 170 | Combining Fuzzy Information from Multiple Systems | 1996 | PODS | 0.00027376361 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,702 | Best Position Algorithms for Top-k Queries | 2007 | VLDB |
| 2 | 1,519 | Top-k Query Evaluation with Probabilistic Guarantees | 2004 | VLDB |
| 3 | 2,596 | A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams | 2006 | SIGMOD |
| 4 | 551 | On Computing Correlated Aggregates Over Continual Data Streams | 2001 | SIGMOD |
| 5 | 5,719 | Optimal and General Out-of-Order Sliding-Window Aggregation | 2019 | VLDB |
| 6 | 3,500 | Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions | 2007 | SIGMOD |
| 7 | 3,241 | Optimal and Approximate Computation of Summary Statistics for Range Aggregates | 2001 | PODS |
| 8 | 860 | Aggregation and Ordering in Factorised Databases | 2013 | VLDB |
| 9 | 12,308 | Optimal Top-k Generation of Attribute Combinations based on Ranked Lists | 2012 | SIGMOD |
| 10 | 8,029 | Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation | 2011 | VLDB |