{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T05:23:29Z","timestamp":1775453009646,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,5,18]],"date-time":"2024-05-18T00:00:00Z","timestamp":1715990400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,18]],"date-time":"2024-05-18T00:00:00Z","timestamp":1715990400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100006231","name":"Brookhaven National Laboratory","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006231","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000028","name":"Semiconductor Research Corporation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000028","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Streaming graph processing performs batched updates and analytics on a time-evolving graph. The underlying representation format of the graph largely determines the throughputs of these updates and analytics phases. Existing representation formats usually employ variations of hash tables or adjacency lists. However, a recent study showed that the adjacency-list-based approaches perform poorly on heavy-tailed graphs, and the hash table-based approaches suffer on short-tailed graphs. We propose GraphTango, a hybrid representation format that provides excellent update and analytics throughput regardless of the graph\u2019s degree distribution. GraphTango dynamically switches among three different formats based on a vertex\u2019s degree: (i) Low-degree vertices store the edges directly with the neighborhood metadata, confining accesses to a single cache line, (2) Medium-degree vertices use adjacency lists, and (3) High-degree vertices use hash tables as well as adjacency lists. In this case, the adjacency list provides fast traversal during the analytics phase, while the hash table provides constant-time lookups during the update phase. We further optimized the performance by designing an open-addressing-based hash table that fully utilizes every fetched cache line. In addition, we developed a thread-local lock-free memory pool that allows fast growing\/shrinking of the adjacency lists and hash tables in a multi-threaded environment. We evaluated GraphTango with the help of the SAGA-Bench framework and compared it with four other representation formats: Stinger, Degree-aware Robin Hood Hashing, and two adjacency list-based formats with different workload balancing scheme. On average, GraphTango provides 4.5x higher insertion throughput, 3.2x higher deletion throughput, and 1.1x higher analytics throughput over the <jats:italic>next best<\/jats:italic> format. Furthermore, we integrated GraphTango with the state-of-the-art graph processing frameworks DZiG and RisGraph. Compared to the <jats:italic>vanilla DZiG<\/jats:italic> and <jats:italic>vanilla RisGraph<\/jats:italic>, [<jats:italic>GraphTango + DZiG<\/jats:italic>] and [<jats:italic>GraphTango + RisGraph<\/jats:italic>] reduces the average batch processing time by 2.3x and 1.5x, respectively.<\/jats:p>","DOI":"10.1007\/s10766-024-00768-x","type":"journal-article","created":{"date-parts":[[2024,5,18]],"date-time":"2024-05-18T10:01:52Z","timestamp":1716026512000},"page":"147-170","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["GraphTango: A Hybrid Representation Format for Efficient Streaming Graph Updates and Analysis"],"prefix":"10.1007","volume":"52","author":[{"given":"Alif","family":"Ahmed","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Farzana Ahmed","family":"Siddique","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Skadron","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,18]]},"reference":[{"key":"768_CR1","doi-asserted-by":"crossref","unstructured":"Han, W., et\u00a0al.: Chronos: a graph engine for temporal graph analysis. In: EUROSYS, pp. 1\u201314 (2014)","DOI":"10.1145\/2592798.2592799"},{"key":"768_CR2","doi-asserted-by":"crossref","unstructured":"Cheng, R., et\u00a0al.: Kineograph: taking the pulse of a fast-changing and connected world. In: EUROSYS, pp 85\u201398 (2012)","DOI":"10.1145\/2168836.2168846"},{"key":"768_CR3","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1038\/nbt.2023","volume":"29","author":"PEC Compeau","year":"2011","unstructured":"Compeau, P.E.C., et al.: How to apply de bruijn graphs to genome assembly. Nat. Biotechnol. 29, 987\u2013991 (2011)","journal-title":"Nat. Biotechnol."},{"key":"768_CR4","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1101\/gr.074492.107","volume":"18","author":"DR Zerbino","year":"2008","unstructured":"Zerbino, D.R., et al.: Velvet: algorithms for de novo short read assembly using de bruijn graphs. Genome Res. 18, 821\u2013829 (2008)","journal-title":"Genome Res."},{"key":"768_CR5","unstructured":"Grewal, A., et\u00a0al.: Recservice: distributed real-time graph processing at twitter. In: HotCloud (2018)"},{"key":"768_CR6","doi-asserted-by":"crossref","unstructured":"Eksombatchai, C., et\u00a0al.: Pixie: a system for recommending 3+ billion items to 200+ million users in real-time. In: WWW, pp. 1775\u20131784 (2018)","DOI":"10.1145\/3178876.3186183"},{"key":"768_CR7","doi-asserted-by":"crossref","unstructured":"Park, J., Nahrstedt, K.: navigation graph for tiled media streaming. In: ICME, pp. 447\u2013455 (2019)","DOI":"10.1145\/3343031.3351021"},{"key":"768_CR8","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1016\/j.procs.2016.08.250","volume":"96","author":"P Braun","year":"2016","unstructured":"Braun, P., et al.: Knowledge discovery from social graph data. Procedia Comput. Sci. 96, 682\u2013691 (2016)","journal-title":"Procedia Comput. Sci."},{"key":"768_CR9","doi-asserted-by":"crossref","unstructured":"Borgman, C.L., et\u00a0al.: Drowning in data: digital library architecture to support scientific use of embedded sensor networks. In: JCDL, pp. 269\u2013277 (2007)","DOI":"10.1145\/1255175.1255228"},{"key":"768_CR10","doi-asserted-by":"crossref","unstructured":"Basak, A., et\u00a0al.: Saga-bench: software and hardware characterization of streaming graph analytics workloads. In: ISPASS, pp. 12\u201323 (2020)","DOI":"10.1109\/ISPASS48437.2020.00012"},{"key":"768_CR11","doi-asserted-by":"crossref","unstructured":"Ediger, D., et\u00a0al.: Stinger: high performance data structure for streaming graphs. In: HPEC (2012)","DOI":"10.1109\/HPEC.2012.6408680"},{"key":"768_CR12","doi-asserted-by":"crossref","unstructured":"Jaiyeoba, W., Skadron, K.: Graphtinker: a high performance data structure for dynamic graph processing. In: IPDPS, pp. 1030\u20131041 (2019)","DOI":"10.1109\/IPDPS.2019.00110"},{"key":"768_CR13","doi-asserted-by":"crossref","unstructured":"Iwabuchi, K., et\u00a0al.: Towards a distributed large-scale dynamic graph data store. In: IPDPSW, pp. 892\u2013901 (2016)","DOI":"10.1109\/IPDPSW.2016.189"},{"key":"768_CR14","doi-asserted-by":"publisher","first-page":"936","DOI":"10.1109\/TC.2021.3059386","volume":"70","author":"A McCrabb","year":"2021","unstructured":"McCrabb, A., Bertacco, V.: Optimizing vertex pressure dynamic graph partitioning in many-core systems. IEEE Trans. Comput. 70, 936\u2013949 (2021)","journal-title":"IEEE Trans. Comput."},{"key":"768_CR15","doi-asserted-by":"crossref","unstructured":"Mariappan, M., et\u00a0al.: Dzig: sparsity-aware incremental processing of streaming graphs. In: EUROSYS, pp. 83\u201398 (2021)","DOI":"10.1145\/3447786.3456230"},{"key":"768_CR16","doi-asserted-by":"crossref","unstructured":"Feng, G., et\u00a0al.: Risgraph: a real-time streaming system for evolving graphs to support sub-millisecond per-update analysis at millions ops\/s. In: SIGMOD, pp. 513\u2013527 (2021)","DOI":"10.1145\/3448016.3457263"},{"key":"768_CR17","doi-asserted-by":"crossref","unstructured":"Hu, Y.,\u00a0et\u00a0al.: Graphlily: accelerating graph linear algebra on hbm-equipped fpgas. In: ICCAD, pp. 1\u20139 (2021)","DOI":"10.1109\/ICCAD51958.2021.9643582"},{"key":"768_CR18","doi-asserted-by":"crossref","unstructured":"Ham, T.J. et\u00a0al.: Graphicionado: a high-performance and energy-efficient accelerator for graph analytics. In MICRO, pp. 1\u201313 (2016)","DOI":"10.1109\/MICRO.2016.7783759"},{"key":"768_CR19","doi-asserted-by":"crossref","unstructured":"Sundaram, N., et\u00a0al.: Graphmat: high performance graph analytics made productive. arXiv:1503.07241 (2015)","DOI":"10.14778\/2809974.2809983"},{"key":"768_CR20","first-page":"339","volume":"34","author":"CY Gui","year":"2019","unstructured":"Gui, C.Y., et al.: A survey on graph processing accelerators: challenges and opportunities. JCS &T 34, 339\u2013371 (2019)","journal-title":"JCS &T"},{"key":"768_CR21","doi-asserted-by":"crossref","unstructured":"Celis, P., et\u00a0al.: Robin hood hashing. In: SFCS, pp. 281\u2013288 (1985)","DOI":"10.1109\/SFCS.1985.48"},{"key":"768_CR22","volume-title":"Introduction to algorithms","author":"Cormen","year":"2009","unstructured":"Cormen, et al.: Introduction to algorithms. MIT press, Cambridge (2009)"},{"key":"768_CR23","unstructured":"ISO\/IEC JTC 1\/SC 22 technical committee. C++ standard. https:\/\/www.iso.org\/standard\/79358.html (2020)"},{"key":"768_CR24","volume-title":"The art of computer programming","author":"DE Knuth","year":"1973","unstructured":"Knuth, D.E.: The art of computer programming. Addison-Westley Publishing, Reading, MA (1973)"},{"key":"768_CR25","unstructured":"Leskovec, J., Krevl, A.: Snap datasets: stanford large network dataset collection. https:\/\/snap.stanford.edu\/data\/ (2014)"},{"key":"768_CR26","unstructured":"Planchon T.: Tessil github repository. https:\/\/github.com\/Tessil\/robin-map (2022)"},{"key":"768_CR27","unstructured":"Ankerl M.: Robin hood hashing github repository. https:\/\/github.com\/martinus\/robin-hood-hashing (2022)"},{"key":"768_CR28","unstructured":"Google: Abseil github repository. https:\/\/github.com\/abseil\/abseil-cpp (2022)"},{"key":"768_CR29","unstructured":"Ankerl M.: Hashmap benchmarks. https:\/\/martin.ankerl.com\/2019\/04\/01\/hashmap-benchmarks-01-overview\/ (2019)"},{"key":"768_CR30","unstructured":"Matt K.: Designing a fast, efficient, cache-friendly hash table, step by step. CPPcon. Standard C++ Foundation (2017)"},{"key":"768_CR31","doi-asserted-by":"crossref","unstructured":"Mariappan, M., et\u00a0al.: Dzig: sparsity-aware incremental processing of streaming graphs. https:\/\/github.com\/pdclab\/graphbolt\/tree\/eurosys21-artifact (2021)","DOI":"10.1145\/3447786.3456230"},{"key":"768_CR32","unstructured":"Feng et\u00a0al.: Risgraph github repository. https:\/\/github.com\/thu-pacman\/RisGraph (2021)"}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-024-00768-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10766-024-00768-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10766-024-00768-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,17]],"date-time":"2024-06-17T15:34:07Z","timestamp":1718638447000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10766-024-00768-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,18]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["768"],"URL":"https:\/\/doi.org\/10.1007\/s10766-024-00768-x","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"value":"0885-7458","type":"print"},{"value":"1573-7640","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,18]]},"assertion":[{"value":"20 October 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All (U. Virginia)\u2014plus,  Abraham, Jacob (U. Texas),   Akel, Ameen (Micron Technologies),   Angstadt, Kevin (St. Lawrence U.),   Aly, Mohamed El-Hadedy (California Polytechnic),   Ceze, Luis (University of Washington),   Cheng, Eric (Laboratory for Physical Sciences),   Cher, Chen-Yong (Graphen),   Cho, Hyungmin (Sungkyunkwan U.),   Chung, Sung Woo (Korea University),   Clark, Doug (Princeton, retired),    Cong, Jason (University of California, Los Angeles),    Dickerson, Samuel (University of Pittsburgh),    Eilert, Sean (independent),    Eliceiri, Kevin (University of Wisconsin),    Fazeli, Mahdi (Halmsted University),   Gai, Yan (St. Louis University),Gao, Wei (University of Pittsburgh), Gaur, Jayesh (Intel), Gavrilovska, Ada (Georgia Tech),  Guo, Xinfei (Shanghai Jiao Tong U.),  Hoe, James (CMU), Huang, Hang (University of Maryland), Hwu, Wen-Mei (UIUC), Imani, Mohsen (UC Irvine), Jun, Sang-Woo (UC Irvine), Knight, Rob (University of California, San Diego),  Kozyrakis, Christos (Stanford University), Li, Jing (UPenn), Lila, Klas (Robust Chip), Marino, Mario (Leeds Beckett University), Martinez, Jose (Cornell University), Martonosi, Margaret (Princeton), McDaniel, Patrick (Penn State U), Meyer, Brett (McGill), Mirkhani, Shahrzad (U. Texas), Moshiri, Niema (UCSD), Narayanan, Vijay (Penn State U), Orenstein, Yaron (Bar Ilan U), Page, Brian (LPS), Parkhurst, Jeff (Intel), Patel, Jignesh (Wisconsin University), Pop, Eric (Stanford), Qureshi, Moin (Georgia Tech), Raina, Priyanka (Stanford), Rosing, Tajana (University of California, San Diego), Sadredini, Elaheh (UC Riverside), Salahuddin, Sayeef (Berkeley), Sampson, Adrian (Cornell), Sheaffer, Jeremy (Iowa State), Sivasubramaniam, Anand (Penn State U), Strukov, Dimitri (University of California, Santa Barbara), Subrramaniyan, Arun (Michigan), Subramoney, Sreenivas (Intel), Sun, Yizhou (UCKA), Swift, Michael (Wisconsin), Swanson, Steven (University of California, San Diego), Tabajara, Lucas (Rice), Vardi, Moshe (Rice), Wadden, John \u201cJack\u201d (University of Michigan), Weimer, Westley (University of Michigan), Witchell, Emmet (U. Texas), Wong, Philip (Stanford), Xie, Yuan (UCSB), Yu, Shimeng (Georgia Tech), Zhang, Yiying (UCSD), Zhang, Zhiru (Cornell University), Zhao, Jishen (University of California, San Diego), Zhou, Peipei (U. Pittsburgh),  Zhou, Yuanyuan (University of California, San Diego), Zhu, Song-Chun (University of California, Los Angeles)","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}