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.9793485e-05
Overall Rank: 10,544 | 29.11%
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.00076195956
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
17	Provenance Semirings	2007	PODS	0.00059752575
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020020639
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019720059
388	Incremental Maintenance of Views with Duplicates	1995	SIGMOD	0.00019350381
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018900199
637	Answering Conjunctive Queries under Updates	2017	PODS	0.00015341557
812	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013729015
849	Aggregation and Ordering in Factorised Databases	2013	VLDB	0.00013504405
978	Incremental Query Evaluation in a Ring of Databases	2010	PODS	0.00012731074
1,082	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012122749
1,570	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.0001020855
1,734	Flow-Loss: Learning Cardinality Estimates That Matter	2021	VLDB	9.7545773e-05
3,112	Incremental View Maintenance with Triple Lock Factorization Benefits	2018	SIGMOD	7.6357579e-05
3,187	Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries	2020	PODS	7.5546613e-05
3,327	Robust Query Driven Cardinality Estimation under Changing Workloads	2023	VLDB	7.4207879e-05
3,673	DBSP: Automatic Incremental View Maintenance for Rich Query Languages	2023	VLDB	7.1092596e-05
5,057	Change Propagation Without Joins	2023	VLDB	6.2927647e-05
6,386	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.8040725e-05
6,876	Insert-Only versus Insert-Delete in Dynamic Query Evaluation	2024	PODS	5.6586279e-05
10,028	Towards Update-Dependent Analysis of Query Maintenance	2025	PODS	5.0925155e-05

Semantically Similar Papers

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