{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:57:58Z","timestamp":1781326678404,"version":"3.54.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"name":"HKRGC","award":["16205422,16204223,16203924"],"award-info":[{"award-number":["16205422,16204223,16203924"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>Query processing under updates (a.k.a. incremental view maintenance) has received increasing attention in recent years, from both theoretical and practical angles. While existing algorithms work well in handling reporting queries, they may incur a high cost on aggregation queries, which are the more important type of analytical workload.<\/jats:p>\n                  <jats:p>In this paper, we show that by allowing a small approximation error, aggregation queries can be processed efficiently under updates. Specifically, we design a new approximate query processing (AQP) algorithm that can maintain the result of any free-connex aggregation query in logarithmic time amortized per update over an insertion-only update sequence. For update sequences with both insertions and deletions, the logarithmic time bound does not hold, due to known lower bounds. Practically, our algorithm performs well on both insertion-only and fully dynamic update sequences. Our experimental results show that, with a 10% error guarantee, the algorithm achieves average speedups of 1.5x, 4.8x, and 13.4x over three exact solutions. Our algorithm works in a general semiring framework, which incorporates a variety of aggregations, including count, sum, avg, max, and count distinct, possibly with a group by.<\/jats:p>","DOI":"10.1145\/3769760","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Query Processing under Updates"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-5438-7288","authenticated-orcid":false,"given":"Binyang","family":"Dai","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2178-3716","authenticated-orcid":false,"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Code and Queries. https:\/\/github.com\/hkustDB\/DynaGox\/."},{"key":"e_1_2_1_2_1","unstructured":"DuckDB. https:\/\/duckdb.org\/."},{"key":"e_1_2_1_3_1","unstructured":"feldera. https:\/\/www.feldera.com\/."},{"key":"e_1_2_1_4_1","unstructured":"TPC-DS. https:\/\/www.tpc.org\/tpcds\/."},{"key":"e_1_2_1_5_1","unstructured":"TPC-H. https:\/\/www.tpc.org\/tpch\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3695837"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2015836.2015849"},{"key":"e_1_2_1_9_1","volume-title":"Alex Averbuch, Altan Birler, Peter Boncz, M\u00e1rton B\u00far, Orri Erling, Andrey Gubichev, Vlad Haprian, Moritz Kaufmann, et al.","author":"Angles Renzo","year":"2020","unstructured":"Renzo Angles, J\u00e1nos Benjamin Antal, Alex Averbuch, Altan Birler, Peter Boncz, M\u00e1rton B\u00far, Orri Erling, Andrey Gubichev, Vlad Haprian, Moritz Kaufmann, et al. 2020. The LDBC social network benchmark. arXiv preprint arXiv:2001.02299 (2020)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3587136.3587137"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056097"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Rada Chirkova Jun Yang et al. 2012. Materialized views. Foundations and Trends\u00ae in Databases 4 4 (2012) 295-405.","DOI":"10.1561\/1900000020"},{"key":"e_1_2_1_16_1","first-page":"645927","article-title":"Approximate Query Processing: Taming the TeraBytes","volume":"10","author":"Garofalakis Minos N","year":"2001","unstructured":"Minos N Garofalakis and Phillip B Gibbons. 2001. Approximate Query Processing: Taming the TeraBytes.. In VLDB, Vol. 10. 645927-672356.","journal-title":"VLDB"},{"key":"e_1_2_1_17_1","volume-title":"Semirings and affine equations over them: theory and applications","author":"Golan Jonathan S","unstructured":"Jonathan S Golan. 2003. Semirings and affine equations over them: theory and applications. Vol. 556. Springer Science & Business Media."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11604686_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265535"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223849"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2004.11.011"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3725254"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902293"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2019.4"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3396375"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387646"},{"key":"e_1_2_1_29_1","volume-title":"Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries. Logical Methods in Computer Science 19","author":"Kara Ahmet","year":"2023","unstructured":"Ahmet Kara, Milos Nikolic, Dan Olteanu, and Haozhe Zhang. 2023. Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries. Logical Methods in Computer Science 19 (2023)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-023-00817-w"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0348-4"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_34_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461837.3464516"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476259"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3583140.3583164"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183758"},{"key":"e_1_2_1_39_1","volume-title":"Recent Increments in Incremental View Maintenance. In Companion of the 43rd Symposium on Principles of Database Systems. 8-17","author":"Olteanu Dan","year":"2024","unstructured":"Dan Olteanu. 2024. Recent Increments in Incremental View Maintenance. In Companion of the 43rd Symposium on Principles of Database Systems. 8-17."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274607"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662508.004"},{"key":"e_1_2_1_43_1","unstructured":"D Quass. 1996. Maintenance Expressions for Views with Aggregation. (1996)."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579080"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380586"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769760","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:40:22Z","timestamp":1781325622000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":45,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769760"],"URL":"https:\/\/doi.org\/10.1145\/3769760","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}