{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T23:15:13Z","timestamp":1776122113568,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:p>The ever-growing amount of dynamic graph data demands efficient techniques of incremental graph processing. However, incremental graph algorithms are challenging to develop. Existing approaches usually require users to manually design nontrivial incremental operators, or choose different memoization strategies for certain specific types of computation, limiting the usability and generality.<\/jats:p>\n          <jats:p>\n            In light of these challenges, we propose Ingress, an automated system for\n            <jats:italic>&lt;u&gt;in&lt;\/u&gt;cremental &lt;u&gt;g&lt;\/u&gt;raph proc&lt;u&gt;ess&lt;\/u&gt;ing.<\/jats:italic>\n            Ingress is able to incrementalize batch vertex-centric algorithms into their incremental counterparts as a whole, without the need of redesigned logic or data structures from users. Underlying Ingress is an automated incrementalization framework equipped with four different memoization policies, to support all kinds of vertex-centric computations with optimized memory utilization. We identify sufficient conditions for the applicability of these policies. Ingress chooses the best-fit policy for a given algorithm automatically by verifying these conditions. In addition to the ease-of-use and generalization, Ingress outperforms state-of-the-art incremental graph systems by 15.93X on average (up to 147.14X) in efficiency.\n          <\/jats:p>","DOI":"10.14778\/3461535.3461550","type":"journal-article","created":{"date-parts":[[2021,10,22]],"date-time":"2021-10-22T22:22:49Z","timestamp":1634941369000},"page":"1613-1625","source":"Crossref","is-referenced-by-count":20,"title":["Automating incremental graph processing with flexible memoization"],"prefix":"10.14778","volume":"14","author":[{"given":"Shufeng","family":"Gong","sequence":"first","affiliation":[{"name":"Northeastern University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chao","family":"Tian","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qiang","family":"Yin","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenyuan","family":"Yu","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yanfeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Northeastern University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Liang","family":"Geng","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Song","family":"Yu","sequence":"additional","affiliation":[{"name":"Northeastern University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ge","family":"Yu","sequence":"additional","affiliation":[{"name":"Northeastern University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingren","family":"Zhou","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,10,22]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2005. uk-2005. https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/LAW\/uk-2005.html.  2005. uk-2005. https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/LAW\/uk-2005.html."},{"key":"e_1_2_1_2_1","unstructured":"2010. europe-osm. https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/DIMACS10\/europe_osm.html.  2010. europe-osm. https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/DIMACS10\/europe_osm.html."},{"key":"e_1_2_1_3_1","unstructured":"2011. road-usa-graph. https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/DIMACS10\/road_usa.html.  2011. road-usa-graph. https:\/\/www.cise.ufl.edu\/research\/sparse\/matrices\/DIMACS10\/road_usa.html."},{"key":"e_1_2_1_4_1","unstructured":"2020. libgrape-lite. https:\/\/github.com\/alibaba\/libgrape-lite.  2020. libgrape-lite. https:\/\/github.com\/alibaba\/libgrape-lite."},{"key":"e_1_2_1_5_1","unstructured":"2020. Size of Wikipedia. https:\/\/en.wikipedia.org\/wiki\/Wikipedia:Size_of_Wikipedia.  2020. Size of Wikipedia. https:\/\/en.wikipedia.org\/wiki\/Wikipedia:Size_of_Wikipedia."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367618"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1523254"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594304"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3411946"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Leonardo Mendon\u00e7a de Moura and Nikolaj Bj\u00f8rner. 2008. Z3: An Efficient SMT Solver. In TACAS.  Leonardo Mendon\u00e7a de Moura and Nikolaj Bj\u00f8rner. 2008. Z3: An Efficient SMT Solver. In TACAS.","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035944"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389142"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035942"},{"key":"e_1_2_1_15_1","volume-title":"RisGraph: A Real-Time Streaming System for Evolving Graphs. arXiv preprint arXiv:2004.00803","author":"Feng Guanyu","year":"2020"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2387880.2387883"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.2307\/421196"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989421"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294869"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2666356.2594324"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502095"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196917"},{"key":"e_1_2_1_26_1","volume-title":"Kipf and Max Welling","author":"Thomas","year":"2017"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.158"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026547031739"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3386132"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_2_1_32_1","volume-title":"Studies in Logic and the Foundations of Mathematics.","author":"Matijasevi\u010d Yu V"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818185"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902283"},{"key":"e_1_2_1_35_1","volume-title":"Rebecca Isaacs, and Michael Isard.","author":"McSherry Frank","year":"2013"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/2876686.2876719"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2888116.2888372"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/3454287.3455270"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-43659-3_24"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882950"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3157096.3157348"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732232.2732238"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3479162.3479181"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093337.3037748"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389712"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3277355.3277445"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.138"},{"key":"e_1_2_1_50_1","unstructured":"Timothy A. K. Zakian Ludovic A. R. Capelli and Zhenjiang Hu. 2019. Incrementalization of Vertex-Centric Programs. In IPDPS.  Timothy A. K. Zakian Ludovic A. R. Capelli and Zhenjiang Hu. 2019. Incrementalization of Vertex-Centric Programs. In IPDPS."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038916.2038929"},{"key":"e_1_2_1_52_1","first-page":"2091","article-title":"Maiter: An asynchronous graph processing framework for delta-based accumulative iterative computation","volume":"25","author":"Zhang Yanfeng","year":"2013","journal-title":"TPDS"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367471.3367656"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/3026877.3026901"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3461535.3461550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:49:11Z","timestamp":1672220951000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3461535.3461550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5]]},"references-count":52,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["10.14778\/3461535.3461550"],"URL":"https:\/\/doi.org\/10.14778\/3461535.3461550","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,5]]}}}