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: 7357
Venue: SIGMOD
Year: 2026
Pagerank: 4.1905499e-05
Overall Rank: 10,049 | 30.16%
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.0010813443
31	Provenance Semirings	2007	PODS	0.00078516827
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482
430	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00023406426
482	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00022145976
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
585	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00019682634
770	Answering Conjunctive Queries under Updates	2017	PODS	0.0001686092
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587
1,231	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00013141213
1,255	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00013011216
1,574	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00011289028
2,173	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3767985e-05
2,781	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	8.1282042e-05
3,785	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	6.7658346e-05
4,200	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	6.3618329e-05
4,413	Robust Query Driven Cardinality Estimation under Changing Workloads	2023	VLDB	6.1989918e-05
5,947	DBSP: Automatic Incremental View Maintenance for Rich Query Languages	2023	VLDB	5.2577662e-05
5,973	Change Propagation Without Joins	2023	VLDB	5.2459364e-05
6,699	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	4.9534535e-05
8,428	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	4.5095504e-05
9,706	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	4.2951473e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,788	Query Processing for SQL Updates	2004	SIGMOD	4.6465948e-05
11,561	Aggregate Queries on Sparse Databases	2020	PODS	4.1905499e-05
7,280	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD	4.7718173e-05
9,706	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	4.2951473e-05
3,944	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD	6.6056349e-05
649	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD	0.00018652362
2,583	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD	8.4973431e-05
11,287	Approximate Queries over Concurrent Updates	2023	VLDB	4.1905499e-05
10,349	Efficient Approximate Query Processing with Block Sampling	2025	CIDR	4.1905499e-05
6,724	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD	4.9449472e-05