DBScholar

Back to papers

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)

Paper ID
h3bbb91e1e77f20ee
Venue
PODS
Year
2001
Pagerank
0.0010679641
Overall Rank
5 | 99.97%
DOI
10.1145/375551.375567

Incoming Non-self Citations Over Time

Authors

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 50 of 245 citing papers.

Rank Citing Paper Year Venue Pagerank
51 Efficient Query Evaluation on Probabilistic Databases 2004 VLDB 0.00042936299
81 XRANK: Ranked Keyword Search over XML Documents 2003 SIGMOD 0.00036346781
194 Milvus: A Purpose-Built Vector Data Management System 2021 SIGMOD 0.00025636725
217 Efficient IR-Style Keyword Search over Relational Databases 2003 VLDB 0.00024465994
270 BLINKS: Ranked Keyword Searches on Graphs 2007 SIGMOD 0.00022599109
290 ObjectRank: Authority-Based Keyword Search in Databases 2004 VLDB 0.00021955068
293 Bidirectional Expansion For Keyword Search on Graph Databases 2005 VLDB 0.00021943678
315 Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems 2018 PODS 0.00021246
474 Automated Ranking of Database Query Results 2003 CIDR 0.00017672562
507 Supporting Incremental Join Queries on Ranked Inputs 2001 VLDB 0.00017101297
524 Supporting Top-k Join Queries in Relational Databases 2003 VLDB 0.00016909926
555 SageDB: A Learned Database System 2019 CIDR 0.00016506678
565 Distributed Top-K Monitoring 2003 SIGMOD 0.00016296423
576 Quality and Efficiency in High Dimensional Nearest Neighbor Search 2009 SIGMOD 0.00016121388
671 Foundations of Preferences in Database Systems 2002 VLDB 0.00014929237
674 Efficient Similarity Search and Classification via Rank Aggregation 2003 SIGMOD 0.00014886692
715 Data Integration with Uncertainty 2007 VLDB 0.00014559092
739 PathSim: Meta Path-Based Top-K Similarity Search in Heterogeneous Information Networks 2011 VLDB 0.00014333298
817 Finding k-Dominant Skylines in High Dimensional Space 2006 SIGMOD 0.00013672764
838 Minimal Probing: Supporting Expensive Predicates for Top-k Queries 2002 SIGMOD 0.00013550235
942 SPARK: Top-k Keyword Query in Relational Databases 2007 SIGMOD 0.00012956137
961 RankSQL: Query Algebra and Optimization for Relational Top-k Queries 2005 SIGMOD 0.0001282305
1,145 Efficient Diversity-Aware Search 2011 SIGMOD 0.00011824078
1,230 Efficient Query Processing in Geographic Web Search Engines 2006 SIGMOD 0.00011412036
1,293 Finding Related Tables in Data Lakes for Interactive Data Science 2020 SIGMOD 0.00011149857
1,374 Neighborhood Based Fast Graph Search in Large Networks 2011 SIGMOD 0.00010880336
1,379 Designing Fair Ranking Schemes 2019 SIGMOD 0.0001086418
1,396 Ranking Queries on Uncertain Data: A Probabilistic Threshold Approach 2008 SIGMOD 0.0001079253
1,439 Continuous Monitoring of Top-k Queries over Sliding Windows 2006 SIGMOD 0.00010642846
1,445 Finding and Approximating Top-k Answers in Keyword Proximity Search 2006 PODS 0.0001063035
1,476 Diversifying Top-K Results 2012 VLDB 0.00010551487
1,477 Efficient Processing of Top-k Spatial Preference Queries 2011 VLDB 0.00010551239
1,535 Top-k Query Evaluation with Probabilistic Guarantees 2004 VLDB 0.00010331242
1,557 Ordering the Attributes of Query Results 2006 SIGMOD 0.00010266055
1,565 Keyword Proximity Search in Complex Data Graphs 2008 SIGMOD 0.00010220855
1,635 Efficient Search for the Top-k Probable Nearest Neighbors in Uncertain Databases 2008 VLDB 0.00010017067
1,643 Relaxing Join and Selection Queries 2006 VLDB 0.00010006399
1,725 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.7902443e-05
1,737 Extending Autocompletion To Tolerate Errors 2009 SIGMOD 9.7494976e-05
1,760 Structured Querying of Web Text: A Technical Challenge 2007 CIDR 9.7106555e-05
1,773 Rank-aware Query Optimization 2004 SIGMOD 9.6719067e-05
1,812 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5803973e-05
1,856 Efficient Retrieval of the Top-k Most Relevant Spatial Web Objects 2009 VLDB 9.4938262e-05
1,886 Probabilistic Ranking of Database Query Results 2004 VLDB 9.4339749e-05
2,006 IO-Top-k: Index-access Optimized Top-k Query Processing 2006 VLDB 9.199795e-05
2,008 PIQL: Success-Tolerant Query Processing in the Cloud 2012 VLDB 9.1988831e-05
2,046 On the Integration of Structure Indexes and Inverted Lists 2004 SIGMOD 9.1269888e-05
2,214 Effective Phrase Prediction 2007 VLDB 8.8195986e-05
2,229 Real-time Targeted Influence Maximization for Online Advertisements 2015 VLDB 8.8000047e-05
2,234 Efficient Network-Aware Search in Collaborative Tagging Sites 2008 VLDB 8.7872006e-05
Previous Page 1 / 5 Next

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
111 Optimizing Multi-Feature Queries for Image Databases 2000 VLDB 0.00032675259
172 Combining Fuzzy Information from Multiple Systems 1996 PODS 0.00026835705
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,656 Best Position Algorithms for Top-k Queries 2007 VLDB
2 1,535 Top-k Query Evaluation with Probabilistic Guarantees 2004 VLDB
3 2,649 A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams 2006 SIGMOD
4 566 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD
5 5,843 Optimal and General Out-of-Order Sliding-Window Aggregation 2019 VLDB
6 3,566 Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions 2007 SIGMOD
7 3,305 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS
8 849 Aggregation and Ordering in Factorised Databases 2013 VLDB
9 12,599 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD
10 8,189 Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation 2011 VLDB