Approximate Query Processing under Updates

Summary: Allowing small approximation yields an AQP algorithm that maintains any free-connex aggregation query in O(log n) amortized time per insertion-only update. Works in a general semiring (count/sum/avg/max/distinct), gives large practical speedups with 10% error, and logarithmic bounds for fully dynamic updates ruled out by lower bounds. (summarized by gpt-5-mini on Feb 11 2026)

Paper ID: 7356
Venue: SIGMOD
Year: 2026
Pagerank: 4.1945683e-05
Overall Rank: 10,049 | 30.10%
DOI: 10.1145/3769760

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Binyang Dai
2. Ke Yi

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
14	Online Aggregation	1997	SIGMOD	0.0010801504
31	Provenance Semirings	2007	PODS	0.0007857786
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
449	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00022846068
481	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00022167223
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
586	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019685374
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
1,238	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00013114581
1,259	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00012995821
1,574	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00011287495
2,169	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3845975e-05
2,783	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1293383e-05
3,781	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	6.7723513e-05
4,197	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	6.367895e-05
4,417	Robust Query Driven Cardinality Estimation under Changing Workloads	2023	VLDB	6.2037371e-05
5,944	DBSP: Automatic Incremental View Maintenance for Rich Query Languages	2023	VLDB	5.2628186e-05
5,967	Change Propagation Without Joins	2023	VLDB	5.250976e-05
6,695	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	4.9582125e-05
8,437	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	4.5138778e-05
9,707	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	4.299267e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,789	Query Processing for SQL Updates	2004	SIGMOD	4.6510017e-05
11,557	Aggregate Queries on Sparse Databases	2020	PODS	4.1945683e-05
7,282	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD	4.776631e-05
9,707	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	4.299267e-05
3,944	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	6.6078243e-05
647	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00018668224
11,285	Approximate Queries over Concurrent Updates	2023	VLDB	4.1945683e-05
2,580	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	8.5058814e-05
10,337	Efficient Approximate Query Processing with Block Sampling	2025	CIDR	4.1945683e-05
6,740	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.944395e-05