{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T14:53:47Z","timestamp":1777733627195,"version":"3.51.4"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:p>Despite the wide adoption of graph processing across many different application domains, there is no underlying data structure that can serve a variety of graph workloads (analytics, traversals, and pattern matching) on dynamic graphs with transactional updates.<\/jats:p>\n          <jats:p>In this paper, we present Sortledton, a universal graph data structure that addresses the open problem by being carefully optimizing for the most relevant data access patterns used by graph computation kernels. It can support millions of transactional updates per second, while providing competitive performance (1.22x on average) for the most common graph workloads to the best-known baseline for static graphs - CSR. With this, we improve the ingestion throughput over state-of-the-art dynamic graph data structures, while supporting a wider range of graph computations under transactional guarantees, with a much simpler design and significantly smaller memory footprint (2.1x that of CSR).<\/jats:p>","DOI":"10.14778\/3514061.3514065","type":"journal-article","created":{"date-parts":[[2022,6,22]],"date-time":"2022-06-22T22:26:10Z","timestamp":1655936770000},"page":"1173-1186","source":"Crossref","is-referenced-by-count":34,"title":["Sortledton"],"prefix":"10.14778","volume":"15","author":[{"given":"Per","family":"Fuchs","sequence":"first","affiliation":[{"name":"TU Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Domagoj","family":"Margan","sequence":"additional","affiliation":[{"name":"Imperial College London"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jana","family":"Giceva","sequence":"additional","affiliation":[{"name":"TU Munich"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915213"},{"key":"e_1_2_1_2_1","unstructured":"Renzo Angles J\u00e1nos Benjamin Antal Alex Averbuch Peter A. Boncz Orri Erling Andrey Gubichev Vlad Haprian Moritz Kaufmann Josep Llu\u00eds Larriba-Pey Norbert Mart\u00ednez-Bazan J\u00f3zsef Marton Marcus Paradies Minh-Duc Pham Arnau Prat-P\u00e9rez Mirko Spasic Benjamin A. Steer G\u00e1bor Sz\u00e1rnyas and Jack Waudby. 2020. The LDBC Social Network Benchmark. CoRR abs\/2001.02299 (2020). arXiv:2001.02299 http:\/\/arxiv.org\/abs\/2001.02299  Renzo Angles J\u00e1nos Benjamin Antal Alex Averbuch Peter A. Boncz Orri Erling Andrey Gubichev Vlad Haprian Moritz Kaufmann Josep Llu\u00eds Larriba-Pey Norbert Mart\u00ednez-Bazan J\u00f3zsef Marton Marcus Paradies Minh-Duc Pham Arnau Prat-P\u00e9rez Mirko Spasic Benjamin A. Steer G\u00e1bor Sz\u00e1rnyas and Jack Waudby. 2020. The LDBC Social Network Benchmark. CoRR abs\/2001.02299 (2020). arXiv:2001.02299 http:\/\/arxiv.org\/abs\/2001.02299"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3190654"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465296"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.3233\/SPR-130370"},{"key":"e_1_2_1_6_1","volume-title":"Patterson","author":"Beamer Scott","year":"2015","unstructured":"Scott Beamer , Krste Asanovic , and David A . Patterson . 2015 . The GAP Benchmark Suite. CoRR abs\/1508.03619 (2015). arXiv:1508.03619 http:\/\/arxiv.org\/abs\/1508.03619 Scott Beamer, Krste Asanovic, and David A. Patterson. 2015. The GAP Benchmark Suite. CoRR abs\/1508.03619 (2015). arXiv:1508.03619 http:\/\/arxiv.org\/abs\/1508.03619"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2015.12"},{"key":"e_1_2_1_8_1","volume-title":"System Designs, and Graph Queries. CoRR abs\/1910.09017","author":"Besta Maciej","year":"2019","unstructured":"Maciej Besta , Emanuel Peter , Robert Gerstenberger , Marc Fischer , Michal Podstawski , Claude Barthels , Gustavo Alonso , and Torsten Hoefler . 2019. Demystifying Graph Databases: Analysis and Taxonomy of Data Organization , System Designs, and Graph Queries. CoRR abs\/1910.09017 ( 2019 ). arXiv:1910.09017 http:\/\/arxiv.org\/abs\/1910.09017 Maciej Besta, Emanuel Peter, Robert Gerstenberger, Marc Fischer, Michal Podstawski, Claude Barthels, Gustavo Alonso, and Torsten Hoefler. 2019. Demystifying Graph Databases: Analysis and Taxonomy of Data Organization, System Designs, and Graph Queries. CoRR abs\/1910.09017 (2019). arXiv:1910.09017 http:\/\/arxiv.org\/abs\/1910.09017"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3399666.3399908"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364328"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764947.2764954"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2750545"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11945529_11"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314598"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463710"},{"key":"e_1_2_1_17_1","unstructured":"Bolin Ding Kai Zeng and Wenyuan Yu. 2020. Alibaba Sponsor Talk at VLDB.  Bolin Ding Kai Zeng and Wenyuan Yu. 2020. Alibaba Sponsor Talk at VLDB."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319875"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2012.6408680"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851553.2851572"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3398682.3399162"},{"key":"e_1_2_1_23_1","unstructured":"Alastair Green. 2019. THE GQL MANIFESTO. https:\/\/gql.today\/  Alastair Green. 2019. THE GQL MANIFESTO. https:\/\/gql.today\/"},{"key":"e_1_2_1_24_1","volume-title":"Integrating Column-Oriented Storage and Query Processing Techniques Into Graph Database Management Systems. CoRR abs\/2103.02284","author":"Gupta Pranjal","year":"2021","unstructured":"Pranjal Gupta , Amine Mhedhbi , and Semih Salihoglu . 2021. Integrating Column-Oriented Storage and Query Processing Techniques Into Graph Database Management Systems. CoRR abs\/2103.02284 ( 2021 ). arXiv:2103.02284 https:\/\/arxiv.org\/abs\/2103.02284 Pranjal Gupta, Amine Mhedhbi, and Semih Salihoglu. 2021. Integrating Column-Oriented Storage and Query Processing Techniques Into Graph Database Management Systems. CoRR abs\/2103.02284 (2021). arXiv:2103.02284 https:\/\/arxiv.org\/abs\/2103.02284"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733010"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72951-8_11"},{"key":"e_1_2_1_27_1","first-page":"64","article-title":"The Periodic Table of Data Structures","volume":"41","author":"Idreos Stratos","year":"2018","unstructured":"Stratos Idreos , Kostas Zoumpatianos , Manos Athanassoulis , Niv Dayan , Brian Hentschel , Michael S. Kester , Demi Guo , Lukas M. Maas , Wilson Qin , Abdul Wasay , and Yiyou Sun . 2018 . The Periodic Table of Data Structures . IEEE Data Eng. Bull. 41 , 3 (2018), 64 -- 75 . http:\/\/sites.computer.org\/debull\/A18sept\/p64.pdf Stratos Idreos, Kostas Zoumpatianos, Manos Athanassoulis, Niv Dayan, Brian Hentschel, Michael S. Kester, Demi Guo, Lukas M. Maas, Wilson Qin, Abdul Wasay, and Yiyou Sun. 2018. The Periodic Table of Data Structures. IEEE Data Eng. Bull. 41, 3 (2018), 64--75. http:\/\/sites.computer.org\/debull\/A18sept\/p64.pdf","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_28_1","unstructured":"SQL ISO. 2020. ISO\/IEC CD 9075-16. https:\/\/www.iso.org\/standard\/79473.html  SQL ISO. 2020. ISO\/IEC CD 9075-16. https:\/\/www.iso.org\/standard\/79473.html"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562164.1562188"},{"key":"e_1_2_1_30_1","volume-title":"GraphOne: A Data Store for Realtime Analytics on Evolving Graphs. In 17th USENIX Conference on File and Storage Technologies, FAST 2019","author":"Kumar Pradeep","year":"2019","unstructured":"Pradeep Kumar and H. Howie Huang . 2019 . GraphOne: A Data Store for Realtime Analytics on Evolving Graphs. In 17th USENIX Conference on File and Storage Technologies, FAST 2019 , Boston, MA, February 25--28 , 2019 . USENIX Association, 249--263. https:\/\/www.usenix.org\/conference\/fast19\/presentation\/kumar Pradeep Kumar and H. Howie Huang. 2019. GraphOne: A Data Store for Realtime Analytics on Evolving Graphs. In 17th USENIX Conference on File and Storage Technologies, FAST 2019, Boston, MA, February 25--28, 2019. USENIX Association, 249--263. https:\/\/www.usenix.org\/conference\/fast19\/presentation\/kumar"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2095686.2095689"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3327964.3328497"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447708"},{"key":"e_1_2_1_35_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113298"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816685"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3302424.3303974"},{"key":"e_1_2_1_40_1","volume-title":"Lightweight and Highly Flexible Adjacency Lists for Graph Database Management Systems. CoRR abs\/2004.00130","author":"Mhedhbi Amine","year":"2020","unstructured":"Amine Mhedhbi , Pranjal Gupta , Shahid Khaliq , and Semih Salihoglu . 2020. A+ Indexes : Lightweight and Highly Flexible Adjacency Lists for Graph Database Management Systems. CoRR abs\/2004.00130 ( 2020 ). arXiv:2004.00130 https:\/\/arxiv.org\/abs\/2004.00130 Amine Mhedhbi, Pranjal Gupta, Shahid Khaliq, and Semih Salihoglu. 2020. A+ Indexes: Lightweight and Highly Flexible Adjacency Lists for Graph Database Management Systems. CoRR abs\/2004.00130 (2020). arXiv:2004.00130 https:\/\/arxiv.org\/abs\/2004.00130"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342643"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/128765.128770"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2749436"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457313"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2019.00157"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3229863.3229874"},{"key":"e_1_2_1_47_1","unstructured":"James Reinders. 2007. Intel threading building blocks - outfitting C++ for multi-core processor parallelism. O'Reilly. http:\/\/www.oreilly.com\/catalog\/9780596514808\/index.html  James Reinders. 2007. Intel threading building blocks - outfitting C++ for multi-core processor parallelism. O'Reilly. http:\/\/www.oreilly.com\/catalog\/9780596514808\/index.html"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882958"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718003"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007267"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2442516.2442530"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522713"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3037697.3037748"},{"key":"e_1_2_1_55_1","volume-title":"Fast Databases with Fast Durability and Recovery Through Multicore Parallelism. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI '14","author":"Zheng Wenting","year":"2014","unstructured":"Wenting Zheng , Stephen Tu , Eddie Kohler , and Barbara Liskov . 2014 . Fast Databases with Fast Durability and Recovery Through Multicore Parallelism. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI '14 , Broomfield, CO, USA, October 6--8 , 2014, Jason Flinn and Hank Levy (Eds.). USENIX Association, 465--477. https:\/\/www.usenix.org\/conference\/osdi14\/technical-sessions\/presentation\/zheng_wenting Wenting Zheng, Stephen Tu, Eddie Kohler, and Barbara Liskov. 2014. Fast Databases with Fast Durability and Recovery Through Multicore Parallelism. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI '14, Broomfield, CO, USA, October 6--8, 2014, Jason Flinn and Hank Levy (Eds.). USENIX Association, 465--477. https:\/\/www.usenix.org\/conference\/osdi14\/technical-sessions\/presentation\/zheng_wenting"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469379.3469389"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384351"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3514061.3514065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:22:38Z","timestamp":1672219358000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3514061.3514065"}},"subtitle":["a universal, transactional graph data structure"],"short-title":[],"issued":{"date-parts":[[2022,2]]},"references-count":57,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10.14778\/3514061.3514065"],"URL":"https:\/\/doi.org\/10.14778\/3514061.3514065","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,2]]}}}