{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:31:35Z","timestamp":1768109495357,"version":"3.49.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T00:00:00Z","timestamp":1572912000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2019,11,5]]},"abstract":"<jats:p>The ability to efficiently analyze changing data is a key requirement of many real-time analytics applications. Traditional approaches to this problem were developed around the notion of Incremental View Maintenance (IVM), and are based either on the materialization of subresults (to avoid their recomputation) or on the recomputation of subresults (to avoid the space overhead of materialization). Both techniques are suboptimal: instead of materializing results and subresults, one may also maintain a data structure that supports efficient maintenance under updates and from which the full query result can quickly be enumerated. In two previous articles, we have presented algorithms for dynamically evaluating queries that are easy to implement, efficient, and can be naturally extended to evaluate queries from a wide range of application domains. In this paper, we discuss our algorithm and its complexity, explaining the main components behind its efficiency. Finally, we show experiments that compare our algorithm to a state-of-the-art (Higher-order) IVM engine, as well as to a prominent complex event recognition engine. Our approach outperforms the competitor systems by up to two orders of magnitude in processing time, and one order in memory consumption.<\/jats:p>","DOI":"10.1145\/3371316.3371325","type":"journal-article","created":{"date-parts":[[2019,11,5]],"date-time":"2019-11-05T18:56:07Z","timestamp":1572980167000},"page":"33-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Efficient Query Processing for Dynamically Changing Datasets"],"prefix":"10.1145","volume":"48","author":[{"given":"Muhammad","family":"Idris","sequence":"first","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles &amp; TU Dresden, Bruxelles, Belgium"}]},{"given":"Mart\u00edn","family":"Ugarte","sequence":"additional","affiliation":[{"name":"PUC Chile, , Chile"}]},{"given":"Stijn","family":"Vansummeren","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles, Bruxelles, Belgium"}]},{"given":"Hannes","family":"Voigt","sequence":"additional","affiliation":[{"name":"Neo4J, , Germany"}]},{"given":"Wolfgang","family":"Lehner","sequence":"additional","affiliation":[{"name":"TU Dresden, Dresden, Germany"}]}],"member":"320","published-online":{"date-parts":[[2019,11,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/978-3-540-28608-0_16","volume-title":"Data Stream Management - Processing High-Speed Data Streams","author":"Arasu A.","year":"2016","unstructured":"A. Arasu , B. Babcock , S. Babu , J. Cieslewicz , M. Datar , K. Ito , R. Motwani , U. Srivastava , and J. Widom . STREAM: the stanford data stream management system . In Data Stream Management - Processing High-Speed Data Streams , pages 317 -- 336 . Springer , 2016 . A. Arasu, B. Babcock, S. Babu, J. Cieslewicz, M. Datar, K. Ito, R. Motwani, U. Srivastava, and J. Widom. STREAM: the stanford data stream management system. In Data Stream Management - Processing High-Speed Data Streams, pages 317--336. Springer, 2016."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2392389.2392412"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"A. Bonifati W. Martens and T. Timm. An analytical study of large SPARQL query logs. Full version of PVLDB 11(2) paper under submission. Obtained through personal communication.  A. Bonifati W. Martens and T. Timm. An analytical study of large SPARQL query logs. Full version of PVLDB 11(2) paper under submission. Obtained through personal communication.","DOI":"10.14778\/3167892.3167895"},{"key":"e_1_2_1_7_1","volume-title":"Materialized Views","author":"Chirkova R.","year":"2012","unstructured":"R. Chirkova and J. Yang . Materialized Views . Now Publishers Inc ., Hanover, MA, USA, 2012 . R. Chirkova and J. Yang. Materialized Views. Now Publishers Inc., Hanover, MA, USA, 2012."},{"key":"e_1_2_1_8_1","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"2009","unstructured":"T. Cormen . Introduction to Algorithms , 3 rd Edition:. MIT Press , 2009 . T. Cormen. Introduction to Algorithms, 3rd Edition:. MIT Press, 2009.","edition":"3"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187671.2187677"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/170035.170066"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192966"},{"key":"e_1_2_1_14_1","volume-title":"Conjunctive queries with 0-joins under updates. Technical report","author":"Idris M.","year":"2019","unstructured":"M. Idris , M. Ugarte , S. Vansummeren , H. Voigt , and W. Lehner . Conjunctive queries with 0-joins under updates. Technical report , 2019 . Available at http:\/\/arxiv.org\/abs\/1905.09848. M. Idris, M. Ugarte, S. Vansummeren, H. Voigt, and W. Lehner. Conjunctive queries with 0-joins under updates. Technical report, 2019. Available at http:\/\/arxiv.org\/abs\/1905.09848."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807100"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0348-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1108\/09685220810862733"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1619258.1619264"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783888.2783894"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1107499.1107504"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282499"},{"key":"e_1_2_1_23_1","first-page":"82","volume-title":"Proc. of VLDB","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis . Algorithms for acyclic database schemes . In Proc. of VLDB , pages 82 -- 94 , 1981 . M. Yannakakis. Algorithms for acyclic database schemes. In Proc. of VLDB, pages 82--94, 1981."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371316.3371325","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371316.3371325","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:05Z","timestamp":1750204385000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371316.3371325"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,5]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,11,5]]}},"alternative-id":["10.1145\/3371316.3371325"],"URL":"https:\/\/doi.org\/10.1145\/3371316.3371325","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2019,11,5]]},"assertion":[{"value":"2019-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}