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: 1228
Venue: PODS
Year: 2001
Pagerank: 0.0015496097
Overall Rank: 7 | 99.96%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 243 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,637	Context-Sensitive Ranking	2006	SIGMOD	6.0303293e-05
4,711	Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach	2006	VLDB	5.9790683e-05
4,803	A System for Management and Analysis of Preference Data	2014	VLDB	5.9107061e-05
4,807	Diversified Top-k Graph Pattern Matching	2013	VLDB	5.9092289e-05
4,849	Durable Top-k Search in Document Archives	2010	SIGMOD	5.8773304e-05
4,960	Reverse Spatial and Textual k Nearest Neighbor Search	2011	SIGMOD	5.7987607e-05
4,971	Maximizing Conjunctive Views in Deletion Propagation	2011	PODS	5.7938195e-05
4,988	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	5.783959e-05
5,032	Actively Soliciting Feedback for Query Answers in Keyword Search-Based Data Integration	2013	VLDB	5.748807e-05
5,078	Efficient Location-Aware Influence Maximization	2014	SIGMOD	5.715243e-05
5,095	Branch-and-Bound Algorithm for Reverse Top-k Queries	2013	SIGMOD	5.7021328e-05
5,116	Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative	2017	SIGMOD	5.6830089e-05
5,248	Buffering in Query Evaluation over XML Streams	2005	PODS	5.6056584e-05
5,311	From del.icio.us to x.qui.site: Recommendations in Social Tagging Sites	2008	SIGMOD	5.5741093e-05
5,373	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5425231e-05
5,391	Scalable Ranked Publish/Subscribe	2008	VLDB	5.533552e-05
5,555	On Obtaining Stable Rankings	2019	VLDB	5.4386174e-05
5,615	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4101086e-05
5,643	An Optimal and Progressive Approach to Online Search of Top-K Influential Communities	2018	VLDB	5.3928286e-05
5,683	Efficient and Progressive Group Steiner Tree Search	2016	SIGMOD	5.3723969e-05
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
5,903	Building Wavelet Histograms on Large Data in MapReduce	2012	VLDB	5.2791351e-05
5,962	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2536266e-05
5,985	Call to Order: A Hierarchical Browsing Approach to Eliciting Users' Preference	2010	SIGMOD	5.2442779e-05
6,000	DeepEverest: Accelerating Declarative Top-K Queries for Deep Neural Network Interpretation	2022	VLDB	5.2415551e-05
6,050	Ranking Objects by Exploiting Relationships: Computing Top-K over Aggregation	2006	SIGMOD	5.2360729e-05
6,126	In Search of Influential Event Organizers in Online Social Networks	2014	SIGMOD	5.198494e-05
6,164	Similarity Search: A Matching Based Approach	2006	VLDB	5.1733919e-05
6,222	Reverse k-Ranks Query	2014	VLDB	5.1503175e-05
6,293	Ad-Hoc Aggregations of Ranked Lists in the Presence of Hierarchies	2008	SIGMOD	5.1257071e-05
6,297	Towards instance-optimized data systems	2021	VLDB	5.1227886e-05
6,320	Indexing the Earth Mover's Distance Using Normal Distributions	2012	VLDB	5.1129965e-05
6,527	Evaluation Strategies for Top-k Queries over Memory-Resident Inverted Indexes	2011	VLDB	5.0257582e-05
6,547	Flexible Aggregate Similarity Search	2011	SIGMOD	5.0183532e-05
6,632	Global Immutable Region Computation	2014	SIGMOD	4.984576e-05
6,642	Privacy Implications of Database Ranking	2015	VLDB	4.9794512e-05
6,653	Supporting Ranking and Clustering as Generalized Order-By and Group-By	2007	SIGMOD	4.9735307e-05
6,654	Moirae: History-Enhanced Monitoring	2007	CIDR	4.9733876e-05
6,702	Efficient and Flexible Information Retrieval Using MonetDB/X100	2007	CIDR	4.9559916e-05
6,729	Keyword Query Cleaning	2008	VLDB	4.9483065e-05
6,816	RRR: Rank-Regret Representative	2019	SIGMOD	4.9173197e-05
6,829	Depth Estimation for Ranking Query Optimization	2007	VLDB	4.9136064e-05
6,834	A Unified Optimization Algorithm For Solving "Regret-Minimizing Representative" Problems	2020	VLDB	4.9117328e-05
6,855	DBease: Making Databases User-friendly and Easily Accessible	2011	CIDR	4.9062505e-05
6,906	Explaining Monotonic Ranking Functions	2021	VLDB	4.8925595e-05
6,921	Skyline Query Processing over Joins	2011	SIGMOD	4.8925595e-05
7,113	Answering Planning Queries with the Crowd	2013	VLDB	4.8274062e-05
7,135	Anytime Measures for Top-k Algorithms	2007	VLDB	4.8221884e-05
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05
7,240	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	4.792172e-05

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
17	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00096067547
72	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00058577335

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,186	Best Position Algorithms for Top-k Queries	2007	VLDB	6.3764858e-05
1,808	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010486213
2,920	A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams	2006	SIGMOD	7.9001024e-05
619	On Computing Correlated Aggregates Over Continual Data Streams	2001	SIGMOD	0.00019066583
5,971	Optimal and General Out-of-Order Sliding-Window Aggregation	2019	VLDB	5.2480159e-05
3,908	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	6.6392878e-05
3,310	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2408955e-05
1,259	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00012995821
12,111	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD	4.1945683e-05
8,040	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	4.600049e-05