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.0010688884
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 46 of 246 citing papers.

Rank Citing Paper Year Venue Pagerank
10,009 Hyper-Local, Directions-Based Ranking of Places 2011 VLDB 5.0845476e-05
10,057 The Data Interaction Game 2018 SIGMOD 5.0766855e-05
10,064 Distributed Numerical and Machine Learning Computations via Two-Phase Execution of Aggregated Join Trees 2021 VLDB 5.0751093e-05
10,125 On m-Impact Regions and Standing Top-k Influence Problems 2021 SIGMOD 5.0638787e-05
10,192 Threshold Queries in Theory and in the Wild 2022 VLDB 5.052396e-05
10,283 Top-k Relevant Semantic Place Retrieval on Spatial RDF Data 2016 SIGMOD 5.0334833e-05
10,332 Efficient and Effective KNN Sequence Search with Approximate n-grams 2014 VLDB 5.0228171e-05
10,408 SCOUT: Coupling-Free Bounds for Trillion-Scale Top-k Retrieval in Sparse Tensor Factorization 2027 SIGMOD 4.9605343e-05
11,082 ARCADE: A Real-Time Data System for Hybrid and Continuous Query Processing across Diverse Data Modalities 2026 VLDB 4.9605343e-05
11,145 MS-Index: Fast Top-k Subsequence Search for Multivariate Time Series under Euclidean Distance 2026 VLDB 4.9605343e-05
11,245 Approximating Opaque Top-k Queries 2025 SIGMOD 4.9605343e-05
11,581 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9605343e-05
11,596 Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results 2024 SIGMOD 4.9605343e-05
11,651 Searching Data Lakes for Nested and Joined Data 2024 VLDB 4.9605343e-05
11,783 Equitable Top-k Results for Long Tail Data 2023 SIGMOD 4.9605343e-05
12,199 Top-k Queries over Digital Traces 2019 SIGMOD 4.9605343e-05
12,301 Durable Top-k Queries on Temporal Data 2018 VLDB 4.9605343e-05
12,425 Query Reranking As A Service 2016 VLDB 4.9605343e-05
12,634 Making Queries Tractable on Big Data with Preprocessing (through the eyes of complexity theory) 2013 VLDB 4.9605343e-05
12,648 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD 4.9605343e-05
12,659 Taagle: Efficient, Personalized Search in Collaborative Tagging Networks 2012 SIGMOD 4.9605343e-05
12,671 Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions 2012 VLDB 4.9605343e-05
12,695 eXO: Decentralized Autonomous Scalable Social Networking 2011 CIDR 4.9605343e-05
12,706 Schema-As-You-Go: On Probabilistic Tagging and Querying of Wide Tables 2011 SIGMOD 4.9605343e-05
12,708 Exact Indexing for Support Vector Machines 2011 SIGMOD 4.9605343e-05
12,726 Efficient Rank Join with Aggregation Constraints 2011 VLDB 4.9605343e-05
12,748 Transducing Markov Sequences 2010 PODS 4.9605343e-05
12,759 Multiple Feature Fusion for Social Media Applications 2010 SIGMOD 4.9605343e-05
12,767 Finding Maximum Degrees in Hidden Bipartite Graphs 2010 SIGMOD 4.9605343e-05
12,802 An Access Cost-Aware Approach for Object Retrieval over Multiple Sources 2010 VLDB 4.9605343e-05
12,803 Efficient RkNN Retrieval with Arbitrary Non-Metric Similarity Measures 2010 VLDB 4.9605343e-05
12,810 Navigating in Complex Mashed-Up Applications 2010 VLDB 4.9605343e-05
12,818 Optimal Top-K Query Evaluation for Weighted Business Processes 2010 VLDB 4.9605343e-05
12,833 Skip-and-Prune: Cosine-based Top-K Query Processing for Efficient Context-Sensitive Document Retrieval 2009 SIGMOD 4.9605343e-05
12,879 Autocompletion for Mashups 2009 VLDB 4.9605343e-05
12,883 A Fair Assignment Algorithm for Multiple Preference Queries 2009 VLDB 4.9605343e-05
12,885 Improved Search for Socially Annotated Data 2009 VLDB 4.9605343e-05
12,902 Stretch 'n' Shrink: Resizing Queries to User Preferences 2008 SIGMOD 4.9605343e-05
12,919 Dynamic Active Probing of Helpdesk Databases 2008 VLDB 4.9605343e-05
12,924 SEDA: A System for Search, Exploration, Discovery, and Analysis of XML Data 2008 VLDB 4.9605343e-05
12,987 The TopX DB&IR Engine 2007 SIGMOD 4.9605343e-05
13,094 Database-Inspired Search 2005 VLDB 4.9605343e-05
13,098 Complex Spatio-Temporal Pattern Queries 2005 VLDB 4.9605343e-05
13,131 Efficiency-Quality Tradeoffs for Vector Score Aggregation 2004 VLDB 4.9605343e-05
13,178 Searching on the Secondary Structure of Protein Sequences 2002 VLDB 4.9605343e-05
13,190 Database Technologies for Electronic Commerce 2002 VLDB 4.9605343e-05
Previous Page 5 / 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
110 Optimizing Multi-Feature Queries for Image Databases 2000 VLDB 0.00032662513
170 Combining Fuzzy Information from Multiple Systems 1996 PODS 0.0002707332
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,623 Best Position Algorithms for Top-k Queries 2007 VLDB
2 1,539 Top-k Query Evaluation with Probabilistic Guarantees 2004 VLDB
3 2,658 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,861 Optimal and General Out-of-Order Sliding-Window Aggregation 2019 VLDB
6 3,578 Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions 2007 SIGMOD
7 3,312 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS
8 848 Aggregation and Ordering in Factorised Databases 2013 VLDB
9 12,648 Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 2012 SIGMOD
10 8,213 Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation 2011 VLDB