{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T09:35:30Z","timestamp":1774949730458,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,4]]},"abstract":"<jats:p>Analytical graph algorithms commonly compute metrics for a graph at one point in time. In practice it is often also of interest how metrics change over time, e.g., to find trends. For this purpose, algorithms must be executed for multiple graph snapshots.<\/jats:p>\n          <jats:p>\n            We present\n            <jats:italic>Single Algorithm Multiple Snapshots (SAMS)<\/jats:italic>\n            , a novel approach to execute algorithms concurrently for multiple graph snapshots. SAMS automatically transforms graph algorithms to leverage similarities between the analyzed graph snapshots. The automatic transformation interleaves algorithm executions on multiple snapshots, synergistically shares their graph accesses and traversals, and optimizes the algorithm's data layout. Thus, SAMS can amortize the cost of random data accesses and improve memory bandwidth utilization---two main cost factors in graph analytics. We extensively evaluate SAMS using six well-known algorithms and multiple synthetic as well as real-world graph datasets. Our measurements show that in multi-snapshot analyses, SAMS offers runtime improvements of up to two orders of magnitude over traditional snapshot-at-a-time execution.\n          <\/jats:p>","DOI":"10.14778\/3090163.3090166","type":"journal-article","created":{"date-parts":[[2017,5,12]],"date-time":"2017-05-12T12:17:14Z","timestamp":1494591434000},"page":"877-888","source":"Crossref","is-referenced-by-count":21,"title":["Automatic algorithm transformation for efficient multi-snapshot analytics on temporal graphs"],"prefix":"10.14778","volume":"10","author":[{"given":"Manuel","family":"Then","sequence":"first","affiliation":[{"name":"Technical University of Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Timo","family":"Kersten","sequence":"additional","affiliation":[{"name":"Technical University of Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephan","family":"G\u00fcnnemann","sequence":"additional","affiliation":[{"name":"Technical University of Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alfons","family":"Kemper","sequence":"additional","affiliation":[{"name":"Technical University of Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Neumann","sequence":"additional","affiliation":[{"name":"Technical University of Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/567067.567085"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2388996.2389013"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00359-0"},{"key":"e_1_2_1_4_1","volume-title":"DBPL","author":"Cook W. R.","year":"2011"},{"key":"e_1_2_1_5_1","first-page":"599","volume-title":"OSDI","author":"Gonzalez J. E.","year":"2014"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453975"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2592798.2592799"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2150976.2151013"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007270"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544892"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401948"},{"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.1109\/ICDE.2015.7113298"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818185"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.016105"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735507"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"S. Wasserman and K. Faust. Social network analysis: Methods and applications volume 8. Cambridge university press 1994.  S. Wasserman and K. Faust. Social network analysis: Methods and applications volume 8. Cambridge university press 1994.","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_21_1","unstructured":"G. Winskel. The formal semantics of programming languages. MIT press 2001.   G. Winskel. The formal semantics of programming languages . MIT press 2001."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732945"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113363"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3090163.3090166","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:19:51Z","timestamp":1672222791000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3090163.3090166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4]]},"references-count":23,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["10.14778\/3090163.3090166"],"URL":"https:\/\/doi.org\/10.14778\/3090163.3090166","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,4]]}}}