{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T17:00:50Z","timestamp":1759683650273,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,7,24]],"date-time":"2015-07-24T00:00:00Z","timestamp":1437696000000},"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":["ACM Trans. Storage"],"published-print":{"date-parts":[[2015,7,29]]},"abstract":"<jats:p>\n            Temporal graphs that capture graph changes over time are attracting increasing interest from research communities, for functions such as understanding temporal characteristics of social interactions on a time-evolving social graph. ImmortalGraph is a storage and execution engine designed and optimized specifically for temporal graphs. Locality is at the center of ImmortalGraph\u2019s design: temporal graphs are carefully laid out in both persistent storage and memory, taking into account data locality in both time and graph-structure dimensions. ImmortalGraph introduces the notion of\n            <jats:italic>locality-aware batch scheduling<\/jats:italic>\n            in computation, so that common \u201cbulk\u201d operations on temporal graphs are scheduled to maximize the benefit of in-memory data locality. The design of ImmortalGraph explores an interesting interplay among locality, parallelism, and incremental computation in supporting common mining tasks on temporal graphs. The result is a high-performance temporal-graph system that is up to 5 times more efficient than existing database solutions for graph queries. The locality optimizations in ImmortalGraph offer up to an order of magnitude speedup for temporal iterative graph mining compared to a straightforward application of existing graph engines on a series of snapshots.\n          <\/jats:p>","DOI":"10.1145\/2700302","type":"journal-article","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T13:33:00Z","timestamp":1438003980000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":51,"title":["ImmortalGraph"],"prefix":"10.1145","volume":"11","author":[{"given":"Youshan","family":"Miao","sequence":"first","affiliation":[{"name":"University of Science and Technology of China"}]},{"given":"Wentao","family":"Han","sequence":"additional","affiliation":[{"name":"Tsinghua University"}]},{"given":"Kaiwei","family":"Li","sequence":"additional","affiliation":[{"name":"Tsinghua University"}]},{"given":"Ming","family":"Wu","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia"}]},{"given":"Fan","family":"Yang","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia"}]},{"given":"Lidong","family":"Zhou","sequence":"additional","affiliation":[{"name":"Microsoft Research Asia"}]},{"given":"Vijayan","family":"Prabhakaran","sequence":"additional","affiliation":[{"name":"Microsoft Research Silicon Valley"}]},{"given":"Enhong","family":"Chen","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China"}]},{"given":"Wenguang","family":"Chen","sequence":"additional","affiliation":[{"name":"Tsinghua University"}]}],"member":"320","published-online":{"date-parts":[[2015,7,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Aggarwal and Haixun Wang (Eds.)","author":"Charu","year":"2010","unstructured":"Charu C. Aggarwal and Haixun Wang (Eds.) . 2010 . Managing and Mining Graph Data. Advances in Database Systems, Vol. 40 . Springer . 40--43 pages. Charu C. Aggarwal and Haixun Wang (Eds.). 2010. Managing and Mining Graph Data. Advances in Database Systems, Vol. 40. Springer. 40--43 pages."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1480506.1480511"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2168836.2168846"},{"volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS\u201999)","author":"Frigo M.","key":"e_1_2_1_6_1","unstructured":"M. Frigo , C. Leiserson , H. Prokop , and S. Ramachandran . 1999. Cache-oblivious algorithms . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS\u201999) . 285--298. M. Frigo, C. Leiserson, H. Prokop, and S. Ramachandran. 1999. Cache-oblivious algorithms. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS\u201999). 285--298."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201912)","author":"Gonzalez Joseph E.","year":"2012","unstructured":"Joseph E. Gonzalez , Yucheng Low , Haijie Gu , Danny Bickson , and Carlos Guestrin . 2012 . PowerGraph: Distributed graph-parallel computation on natural graphs . In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201912) . 17--30. Joseph E. Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. 2012. PowerGraph: Distributed graph-parallel computation on natural graphs. In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201912). 17--30."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465369"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544892"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912)","volume":"8","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola , Guy Blelloch , and Carlos Guestrin . 2012 . GraphChi: Large-scale graph computation on just a PC . In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912) , Vol. 8 . 31--46. Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi: Large-scale graph computation on just a PC. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation (OSDI\u201912), Vol. 8. 31--46."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1830252.1830262"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066295"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/67544.66956"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/121132.286600"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522738"},{"volume-title":"Neo4j: The graph database. Retrieved","year":"2015","key":"e_1_2_1_21_1","unstructured":"Neo4j. 2013. Neo4j: The graph database. Retrieved July 5, 2015 from http:\/\/neo4j.org. Neo4j. 2013. Neo4j: The graph database. Retrieved July 5, 2015 from http:\/\/neo4j.org."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522739"},{"key":"e_1_2_1_23_1","unstructured":"PostgreSQL. 2013. PostgreSQL. Retrieved July 5 2015 from http:\/\/postgresql.org.  PostgreSQL. 2013. PostgreSQL. Retrieved July 5 2015 from http:\/\/postgresql.org."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201910)","author":"Power Russell","year":"2010","unstructured":"Russell Power and Jinyang Li . 2010 . Piccolo: Building fast, distributed programs with partitioned tables . In Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201910) . 1--14. Russell Power and Jinyang Li. 2010. Piccolo: Building fast, distributed programs with partitioned tables. In Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI\u201910). 1--14."},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 2012 USENIX Annual Technical Conference (ATC\u201912)","volume":"12","author":"Prabhakaran Vijayan","year":"2012","unstructured":"Vijayan Prabhakaran , Ming Wu , Xuetian Weng , Frank McSherry , Lidong Zhou , and Maya Haridasan . 2012 . Managing large graphs on multi-cores with graph awareness . In Proceedings of the 2012 USENIX Annual Technical Conference (ATC\u201912) , Vol. 12 . Vijayan Prabhakaran, Ming Wu, Xuetian Weng, Frank McSherry, Lidong Zhou, and Maya Haridasan. 2012. Managing large graphs on multi-cores with graph awareness. In Proceedings of the 2012 USENIX Annual Technical Conference (ATC\u201912), Vol. 12."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402713"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_52"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963503"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/319806.319816"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_32_1","unstructured":"Sina. 2013. Weibo. Retrieved July 5 2015 from http:\/\/weibo.com.  Sina. 2013. Weibo. Retrieved July 5 2015 from http:\/\/weibo.com."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/2342806.2342807"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465371"},{"volume-title":"Graph database. Retrieved","year":"2015","key":"e_1_2_1_35_1","unstructured":"Wikipedia. 2013. Graph database. Retrieved July 5, 2015 from http:\/\/en.wikipedia.org\/wiki\/Graph_database. Wikipedia. 2013. Graph database. Retrieved July 5, 2015 from http:\/\/en.wikipedia.org\/wiki\/Graph_database."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519065.1519089"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1321440.1321598"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 9th Symposium on Networked Systems Design and Implementation (NSDI\u201912)","author":"Zaharia Matei","year":"2012","unstructured":"Matei Zaharia , Mosharaf Chowdhury , Tathagata Das , Ankur Dave , Justin Ma , Murphy McCauley , Michael Franklin , Scott Shenker , and Ion Stoica . 2012 . Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing . In Proceedings of the 9th Symposium on Networked Systems Design and Implementation (NSDI\u201912) . 2--2. Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauley, Michael Franklin, Scott Shenker, and Ion Stoica. 2012. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In Proceedings of the 9th Symposium on Networked Systems Design and Implementation (NSDI\u201912). 2--2."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920894"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700302","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2700302","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:44Z","timestamp":1750223264000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700302"}},"subtitle":["A System for Storage and Analysis of Temporal Graphs"],"short-title":[],"issued":{"date-parts":[[2015,7,24]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,7,29]]}},"alternative-id":["10.1145\/2700302"],"URL":"https:\/\/doi.org\/10.1145\/2700302","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"type":"print","value":"1553-3077"},{"type":"electronic","value":"1553-3093"}],"subject":[],"published":{"date-parts":[[2015,7,24]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}