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: h0cb6ff825085f299
Venue: SIGMOD
Year: 2026
Pagerank: 4.9605343e-05
Overall Rank: 10,620 | 28.82%
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 (Hong Kong University of Science and Technology)
2. Ke Yi (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{dai_sigmod26,
        title = {{Approximate Query Processing under Updates}},
        author = {Dai, Binyang and Yi, Ke},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3769760},
        url = {https://dl.acm.org/doi/10.1145/3769760},
        year = {2026}
}

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
9	Online Aggregation	1997	SIGMOD	0.00076079812
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
17	Provenance Semirings	2007	PODS	0.00059660827
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020048899
374	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019698889
388	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.0001928135
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018836656
639	Answering Conjunctive Queries under Updates	2017	PODS	0.00015289346
815	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013682594
848	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00013463236
979	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012697012
1,065	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012181098
1,568	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010178045
1,740	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7289523e-05
3,122	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6091671e-05
3,199	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	7.5261206e-05
3,269	Robust Query Driven Cardinality Estimation under Changing Workloads	2023	VLDB	7.463682e-05
3,684	DBSP: Automatic Incremental View Maintenance for Rich Query Languages	2023	VLDB	7.0834345e-05
5,080	Change Propagation Without Joins	2023	VLDB	6.2689958e-05
6,397	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.7822506e-05
6,900	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	5.6372471e-05
10,072	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	5.0732737e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,166	Query Processing for SQL Updates	2004	SIGMOD
2	8,725	Aggregate Queries on Sparse Databases	2020	PODS
3	7,485	Update-Pattern-Aware Modeling and Processing of Continuous Queries	2005	SIGMOD
4	10,072	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS
5	3,435	AQP++: Connecting Approximate Query Processing With Aggregate Precomputation for Interactive Analytics	2018	SIGMOD
6	667	Progressive Approximate Aggregate Queries with a Multi-Resolution Tree Structure	2001	SIGMOD
7	11,844	Approximate Queries over Concurrent Updates	2023	VLDB
8	2,014	Sample + Seek: Approximating Aggregates with Distribution Precision Guarantee	2016	SIGMOD
9	11,149	Efficient Approximate Query Processing with Block Sampling	2025	CIDR
10	6,198	Combining Aggregation and Sampling (Nearly) Optimally for Approximate Query Processing	2021	SIGMOD