{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T23:50:58Z","timestamp":1782949858964,"version":"3.54.5"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,10,25]],"date-time":"2017-10-25T00:00:00Z","timestamp":1508889600000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1524852 and CCF-1318103"],"award-info":[{"award-number":["CCF-1524852 and CCF-1318103"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"UC Irvine, and by ONR","award":["N00014-14-1-0549 and N00014-16-1-2913"],"award-info":[{"award-number":["N00014-14-1-0549 and N00014-16-1-2913"]}]},{"DOI":"10.13039\/100007602","name":"UC Riverside","doi-asserted-by":"crossref","award":["CNS-1321179, CCF-1409829 and CNS-1613023"],"award-info":[{"award-number":["CNS-1321179, CCF-1409829 and CNS-1613023"]}],"id":[{"id":"10.13039\/100007602","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2016,12,28]]},"abstract":"<jats:p>\n                    Evolving graph processing involves repeating analyses, which are often iterative, over multiple snapshots of the graph corresponding to different points in time. Since the snapshots of an evolving graph share a great number of vertices and edges, traditional approaches that process these snapshots one at a time without exploiting this overlap contain much wasted effort on both data loading and computation, making them extremely inefficient. In this article, we identify major sources of inefficiencies and present two optimization techniques to address them. First, we propose a technique for\n                    <jats:italic toggle=\"yes\">amortizing the fetch cost<\/jats:italic>\n                    by merging fetching of values for different snapshots of the same vertex. Second, we propose a technique for\n                    <jats:italic toggle=\"yes\">amortizing the processing cost<\/jats:italic>\n                    by feeding values computed by earlier snapshots into later snapshots. We have implemented these optimizations in two distributed graph processing systems, namely, GraphLab and ASPIRE. Our experiments with multiple real evolving graphs and algorithms show that, on average fetch amortization speeds up execution of GraphLab and ASPIRE by 5.2\u00d7 and 4.1\u00d7 , respectively. Amortizing the processing cost yields additional average speedups of 2\u00d7 and 7.9\u00d7, respectively.\n                  <\/jats:p>","DOI":"10.1145\/2992784","type":"journal-article","created":{"date-parts":[[2016,10,26]],"date-time":"2016-10-26T09:20:01Z","timestamp":1477473601000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Synergistic Analysis of Evolving Graphs"],"prefix":"10.1145","volume":"13","author":[{"given":"Keval","family":"Vora","sequence":"first","affiliation":[{"name":"University of California, Riverside, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajiv","family":"Gupta","sequence":"additional","affiliation":[{"name":"University of California, Riverside, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guoqing","family":"Xu","sequence":"additional","affiliation":[{"name":"University of California, Irvine, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,10,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","unstructured":"Bahman Bahmani Ravi Kumar Mohammad Mahdian and Eli Upfal. 2012. PageRank on an evolving graph. In KDD. 24--32. 10.1145\/2339530.2339539","DOI":"10.1145\/2339530.2339539"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/32.56098"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Zhuhua Cai Dionysios Logothetis and Georgos Siganos. 2012. Facilitating real-time graph mining. In CloudDB. 1--8. 10.1145\/2390021.2390023","DOI":"10.1145\/2390021.2390023"},{"key":"e_1_2_1_4_1","volume-title":"Gummadi","author":"Cha Meeyoung","year":"2010","unstructured":"Meeyoung Cha, Hamed Haddadi, Fabrcio Benevenuto, and Krishna P. Gummadi. 2010. Measuring user influence in twitter: The million follower fallacy. In ICWSM."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","unstructured":"Rong Chen Xin Ding Peng Wang Haibo Chen Binyu Zang and Haibing Guan. 2014. Computation and communication efficient graph processing with distributed immutable view. In HPDC. 215--226. 10.1145\/2600212.2600233","DOI":"10.1145\/2600212.2600233"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_8_1","unstructured":"DeliciousUI 2014. Delicious user-url network dataset. In KONECT."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","unstructured":"Prasanna Desikan Nishith Pathak Jaideep Srivastava and Vipin Kumar. 2005. Incremental page rank computation on evolving graphs. In WWW. 1094--1095. 10.1145\/1062745.1062885","DOI":"10.1145\/1062745.1062885"},{"key":"e_1_2_1_10_1","volume-title":"Bader","author":"Ediger David","year":"2012","unstructured":"David Ediger, Robert McColl, Jason Riedy, and David A. Bader. 2012. STINGER: High performance data structure for streaming graphs. In HPEC. 1--5."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502412875"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4108\/icst.collaboratecom.2012.250532"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","unstructured":"Vicen\u00e7 G\u00f3mez Andreas Kaltenbrunner and Vicente L\u00f3pez. 2008. Statistical analysis of the social network and discussion threads in slashdot. In WWW. 645--654. 10.1145\/1367497.1367585","DOI":"10.1145\/1367497.1367585"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","unstructured":"Joseph E. Gonzalez Yucheng Low Haijie Gu Danny Bickson and Carlos Guestrin. 2012. PowerGraph: Distributed graph-parallel computation on natural graphs. In OSDI. 17--30.","DOI":"10.5555\/2387880.2387883"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Joseph E. Gonzalez Reynold S. Xin Ankur Dave Daniel Crankshaw Michael J. Franklin and Ion Stoica. 2014. GraphX: Graph processing in a distributed dataflow framework. In OSDI. 599--613.","DOI":"10.5555\/2685048.2685096"},{"key":"e_1_2_1_16_1","volume-title":"Cache Consistency and Sequential Consistency","author":"Goodman James R.","unstructured":"James R. Goodman. 1991. Cache Consistency and Sequential Consistency. University of Wisconsin-Madison, CS Department, 567--574."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592799"},{"key":"e_1_2_1_18_1","unstructured":"InfoGrid. 2016. Homepage. Retrieved from http:\/\/infogrid.org\/."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","unstructured":"Andrey Kan Jeffrey Chan James Bailey and Christopher Leckie. 2009. A query based approach for mining evolving graphs. In AusDM. 139--150.","DOI":"10.5555\/2449360.2449386"},{"key":"e_1_2_1_20_1","volume-title":"Parmetis: Parallel Graph Partitioning and Sparse Matrix Ordering Library. Department of Computer Science","author":"Karypis George","year":"1997","unstructured":"George Karypis, Kirk Schloegel, and Vipin Kumar. 1997. Parmetis: Parallel Graph Partitioning and Sparse Matrix Ordering Library. Department of Computer Science, University of Minnesota."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","unstructured":"Udayan Khurana and Amol Deshpande. 2013. Efficient snapshot retrieval over historical graph data. In ICDE. 997--1008. 10.1109\/ICDE.2013.6544892","DOI":"10.1109\/ICDE.2013.6544892"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","unstructured":"Amlan Kusum Keval Vora Rajiv Gupta and Iulian Neamtiu. 2016. Efficient processing of large graphs via input reduction. In HPDC. 245--257. 10.1145\/2907294.2907312","DOI":"10.1145\/2907294.2907312"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Aapo Kyrola Guy Blelloch and Carlos Guestrin. 2012. GraphChi: Large-scale graph computation on just a PC. In OSDI. 31--46.","DOI":"10.5555\/2387880.2387884"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","unstructured":"Jure Leskovec Jon Kleinberg and Christos Faloutsos. 2005. Graphs over time: Densification laws shrinking diameters and possible explanations. In SIGKDD. 177--187. 10.1145\/1081870.1081893","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Michael Ley. 2002. The DBLP computer science bibliography: Evolution research issues perspectives. In SPIRE. 1--10.","DOI":"10.5555\/646491.694954"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/525588.850069"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","unstructured":"Ee-Peng Lim Viet-An Nguyen Nitin Jindal Bing Liu and Hady Wirawan Lauw. 2010. Detecting product review spammers using rating behaviors. In CIKM. 939--948. 10.1145\/1871437.1871557","DOI":"10.1145\/1871437.1871557"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","unstructured":"Xing Liu Edmond Chow Karthikeyan Vaidyanathan and Mikhail Smelyanskiy. 2012. Improving the performance of dynamical simulations via multiple right-hand sides. In IPDPS. 36--47. 10.1109\/IPDPS.2012.14","DOI":"10.1109\/IPDPS.2012.14"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Paolo Massa and Paolo Avesani. 2005. Controversial users demand local trust metrics: An experimental study on epinions.com community. In AAAI. 121--126.","DOI":"10.5555\/1619332.1619354"},{"key":"e_1_2_1_33_1","volume-title":"Graph NoSQL Database {Online}","author":"J.","year":"2012","unstructured":"Neo4J. 2012. Neo4J. Graph NoSQL Database {Online} (2012). https:\/\/neo4j.com\/."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","unstructured":"Donald Nguyen Andrew Lenharth and Keshav Pingali. 2013. A lightweight infrastructure for graph analytics. In SOSP. 456--471. 10.1145\/2517349.2522739","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_35_1","unstructured":"OrientDB. 2012. OrientDB. Hybrid Document-Store and Graph NoSQL Database {Online}. http:\/\/orientdb.com\/."},{"key":"e_1_2_1_36_1","unstructured":"Lawrence Page Sergey Brin Rajeev Motwani and Terry Winograd. 1999. The PageRank citation ranking: Bringing order to the web. Stanford InfoLab."},{"key":"e_1_2_1_37_1","unstructured":"Robey Pointer N. Kallen E. Ceaser and J. Kalucki. 2010. Introducing FlockDB. https:\/\/blog.twitter.com\/2010\/introducing-flockdb."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.80.056103"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402713"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","unstructured":"Ryan A. Rossi Brian Gallagher Jennifer Neville and Keith Henderson. 2013. Modeling dynamic behavior in large evolving graphs. In WSDM. 667--676. 10.1145\/2433396.2433479","DOI":"10.1145\/2433396.2433479"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","unstructured":"Amitabha Roy Ivo Mihailovic and Willy Zwaenepoel. 2013. X-Stream: Edge-centric graph processing using streaming partitions. In SOSP. 472--488. 10.1145\/2517349.2522740","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_43_1","unstructured":"StackExchange. Stack Exchange Inc. Stack Exchange Data Explorer. Retrieved from http:\/\/data.stackexchange.com\/."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281266"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","unstructured":"Toyotaro Suzumura Shunsuke Nishii and Masaru Ganse. 2014. Towards large-scale graph stream processing platform. In WWW Companion. 1321--1326. 10.1145\/2567948.2580051","DOI":"10.1145\/2567948.2580051"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660227"},{"key":"e_1_2_1_47_1","unstructured":"Keval Vora Guoqing Xu and Rajiv Gupta. 2016. Load the edges you need: A generic I\/O optimization for disk-based graph processing. In USENIX ATC."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519065.1519089"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321598"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","unstructured":"Mindi Yuan Kun-Lung Wu Gabriela Jacques-Silva and Yi Lu. 2013. Efficient processing of streaming graphs for evolution-aware clustering. In CIKM. 319--328. 10.1145\/2505515.2505750","DOI":"10.1145\/2505515.2505750"},{"key":"e_1_2_1_52_1","unstructured":"Xiaojin Zhu and Zoubin Ghahramani. 2002. Learning from Labeled and Unlabeled Data with Label Propagation. Technical Report CMU-CALD-02-107 Carnegie Mellon University."}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2992784","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2992784","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2992784","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:18:13Z","timestamp":1763457493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2992784"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,25]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12,28]]}},"alternative-id":["10.1145\/2992784"],"URL":"https:\/\/doi.org\/10.1145\/2992784","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,25]]},"assertion":[{"value":"2016-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}