{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:46:57Z","timestamp":1756000017077},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>Differential computation (DC) is a highly general incremental computation\/view maintenance technique that can maintain the output of an arbitrary and possibly recursive dataflow computation upon changes to its base inputs. As such, it is a promising technique for graph database management systems (GDBMS) that support continuous recursive queries over dynamic graphs. Although differential computation can be highly efficient for maintaining these queries, it can require prohibitively large amount of memory. This paper studies how to reduce the memory overhead of DC with the goal of increasing the scalability of systems that adopt it. We propose a suite of optimizations that are based on dropping the differences of operators, both completely or partially, and recomputing these differences when necessary. We propose deterministic and probabilistic data structures to keep track of the dropped differences. Extensive experiments demonstrate that the optimizations can improve the scalability of a DC-based continuous query processor.<\/jats:p>","DOI":"10.14778\/3551793.3551862","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"3186-3198","source":"Crossref","is-referenced-by-count":4,"title":["Optimizing differentially-maintained recursive queries on dynamic graphs"],"prefix":"10.14778","volume":"15","author":[{"given":"Khaled","family":"Ammar","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Siddhartha","family":"Sahu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Semih","family":"Salihoglu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Tamer","family":"\u00d6zsu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2022. REFINITIV Knowledge Graph. https:\/\/solutions.refinitiv.com\/KnowledgeGraphs.  2022. REFINITIV Knowledge Graph. https:\/\/solutions.refinitiv.com\/KnowledgeGraphs."},{"key":"e_1_2_1_2_1","volume-title":"Foundations of Software Science and Computation Structures","author":"Abadi Mart\u00edn","unstructured":"Mart\u00edn Abadi , Frank McSherry , and Gordon D Plotkin . 2015. Foundations of Differential Dataflow . In Foundations of Software Science and Computation Structures , Andrew Pitts (Ed.). Springer Berlin Heidelberg , Berlin, Heidelberg , 71--83. Mart\u00edn Abadi, Frank McSherry, and Gordon D Plotkin. 2015. Foundations of Differential Dataflow. In Foundations of Software Science and Computation Structures, Andrew Pitts (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 71--83."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2208.00273"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313472"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/11534273_28"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344424"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2001.959900"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Orri Erling Alex Averbuch Josep Larriba-Pey Hassan Chafi Andrey Gubichev Arnau Prat Minh-Duc Pham and Peter Boncz. 2015. The LDBC Social Network Benchmark: Interactive Workload. In SIGMOD. 619--630.  Orri Erling Alex Averbuch Josep Larriba-Pey Hassan Chafi Andrey Gubichev Arnau Prat Minh-Duc Pham and Peter Boncz. 2015. The LDBC Social Network Benchmark: Interactive Workload. In SIGMOD. 619--630.","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Bin Fan Dave G Andersen Michael Kaminsky and Michael D Mitzenmacher. 2014. Cuckoo filter: Practically better than bloom. In ACM CoNEXT. 75--88.  Bin Fan Dave G Andersen Michael Kaminsky and Michael D Mitzenmacher. 2014. Cuckoo filter: Practically better than bloom. In ACM CoNEXT. 75--88.","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_2_1_12_1","volume-title":"SODA","volume":"5","author":"Goldberg Andrew V","year":"2005","unstructured":"Andrew V Goldberg and Chris Harrelson . 2005 . Computing the shortest path: A search meets graph theory .. In SODA , Vol. 5 . Citeseer, 156--165. Andrew V Goldberg and Chris Harrelson. 2005. Computing the shortest path: A search meets graph theory.. In SODA, Vol. 5. Citeseer, 156--165."},{"key":"e_1_2_1_13_1","volume-title":"Boon Thau Loo, Wenchao Zhou, et al.","author":"Green Todd J","year":"2013","unstructured":"Todd J Green , Shan Shan Huang , Boon Thau Loo, Wenchao Zhou, et al. 2013 . Datalog and recursive query processing. Foundations and Trends in Databases . Todd J Green, Shan Shan Huang, Boon Thau Loo, Wenchao Zhou, et al. 2013. Datalog and recursive query processing. Foundations and Trends in Databases."},{"key":"e_1_2_1_14_1","volume-title":"TEGRA: Efficient Ad-Hoc Analytics on Evolving Graphs. In NSDI. 337--355. https:\/\/www.usenix.org\/conference\/nsdi21\/presentation\/iyer","author":"Iyer Anand Padmanabha","year":"2021","unstructured":"Anand Padmanabha Iyer , Qifan Pu , Kishan Patel , Joseph E. Gonzalez , and Ion Stoica . 2021 . TEGRA: Efficient Ad-Hoc Analytics on Evolving Graphs. In NSDI. 337--355. https:\/\/www.usenix.org\/conference\/nsdi21\/presentation\/iyer Anand Padmanabha Iyer, Qifan Pu, Kishan Patel, Joseph E. Gonzalez, and Ion Stoica. 2021. TEGRA: Efficient Ad-Hoc Analytics on Evolving Graphs. In NSDI. 337--355. https:\/\/www.usenix.org\/conference\/nsdi21\/presentation\/iyer"},{"key":"e_1_2_1_15_1","volume-title":"PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations. In ICDM.","author":"Kang U.","year":"2009","unstructured":"U. Kang , Charalampos E. Tsourakakis , and Christos Faloutsos . 2009 . PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations. In ICDM. U. Kang, Charalampos E. Tsourakakis, and Christos Faloutsos. 2009. PEGASUS: A Peta-Scale Graph Mining System Implementation and Observations. In ICDM."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3056445"},{"key":"e_1_2_1_17_1","volume-title":"Seo, Jiwon Seo, and Wook-Shin Han.","author":"Ko Seongyun","year":"2021","unstructured":"Seongyun Ko , Taesung Lee , Kijae Hong , Wonseok Lee , In Seo, Jiwon Seo, and Wook-Shin Han. 2021 . iTurboGraph: Scaling and Automating Incremental Graph Analytics. In SIGMOD. 977--990. Seongyun Ko, Taesung Lee, Kijae Hong, Wonseok Lee, In Seo, Jiwon Seo, and Wook-Shin Han. 2021. iTurboGraph: Scaling and Automating Incremental Graph Analytics. In SIGMOD. 977--990."},{"key":"e_1_2_1_18_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_19_1","volume-title":"A network evaluation procedure. Highway Research Record 205","author":"Loubai Peter S","year":"1967","unstructured":"Peter S Loubai . 1967. A network evaluation procedure. Highway Research Record 205 ( 1967 ). Peter S Loubai. 1967. A network evaluation procedure. Highway Research Record 205 (1967)."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_2_1_21_1","unstructured":"Frank McSherry. 2022. Differential Dataflow. https:\/\/github.com\/frankmcsherry\/differential-dataflow.  Frank McSherry. 2022. Differential Dataflow. https:\/\/github.com\/frankmcsherry\/differential-dataflow."},{"key":"e_1_2_1_22_1","volume-title":"Differential Dataflow. In Proc. 6th Biennial Conf. on Innovative Data Systems Research.","author":"McSherry Frank","year":"2013","unstructured":"Frank McSherry , Derek Murray , Rebecca Isaacs , and Michael Isard . 2013 . Differential Dataflow. In Proc. 6th Biennial Conf. on Innovative Data Systems Research. Frank McSherry, Derek Murray, Rebecca Isaacs, and Michael Isard. 2013. Differential Dataflow. In Proc. 6th Biennial Conf. on Innovative Data Systems Research."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389733"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646063"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0041-5553(68)90148-1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9401-5"},{"key":"e_1_2_1_28_1","unstructured":"Leonid Ryzhyk and Mihai Budiu. 2019. Differential Datalog.. In Datalog. 56--67.  Leonid Ryzhyk and Mihai Budiu. 2019. Differential Datalog.. In Datalog. 56--67."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452837"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2621934.2621938"},{"key":"e_1_2_1_31_1","unstructured":"Christian Stuecklberger. 2016. Expressing the Routing Logic of a SDN Controller as a Differential Dataflow. Master's thesis. ETH Z\u00fcrich.  Christian Stuecklberger. 2016. Expressing the Routing Logic of a SDN Controller as a Differential Dataflow. Master's thesis. ETH Z\u00fcrich."},{"key":"e_1_2_1_32_1","volume-title":"Spark: Cluster Computing with Working Sets. In HotCloud. https:\/\/www.usenix.org\/conference\/hotcloud -cluster-computing-working-sets spark","author":"Zaharia Matei","year":"2010","unstructured":"Matei Zaharia , Mosharaf Chowdhury , Michael J. Franklin , Scott Shenker , and Ion Stoica . 2010 . Spark: Cluster Computing with Working Sets. In HotCloud. https:\/\/www.usenix.org\/conference\/hotcloud -cluster-computing-working-sets spark Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. In HotCloud. https:\/\/www.usenix.org\/conference\/hotcloud -cluster-computing-working-sets spark"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422604.3425936"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551862","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:53:40Z","timestamp":1672224820000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551862"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":33,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551862"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551862","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}