{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T17:18:46Z","timestamp":1763572726868,"version":"build-2065373602"},"reference-count":60,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T00:00:00Z","timestamp":1698969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Data"],"abstract":"<jats:p>The graph model enables a broad range of analyses; thus, graph processing (GP) is an invaluable tool in data analytics. At the heart of every GP system lies a concurrent graph data structure that stores the graph. Such a data structure needs to be highly efficient for both graph algorithms and queries. Due to the continuous evolution, the sparsity, and the scale-free nature of real-world graphs, GP systems face the challenge of providing an appropriate graph data structure that enables both fast analytical workloads and fast, low-memory graph mutations. Existing graph structures offer a hard tradeoff among read-only performance, update friendliness, and memory consumption upon updates. In this paper, we introduce CSR++, a new graph data structure that removes these tradeoffs and enables both fast read-only analytics, and quick and memory-friendly mutations. CSR++ combines ideas from CSR, the fastest read-only data structure, and adjacency lists (ALs) to achieve the best of both worlds. We compare CSR++ to CSR, ALs from the Boost Graph Library (BGL), and the following state-of-the-art update-friendly graph structures: LLAMA, STINGER, GraphOne, and Teseo. In our evaluation, which is based on popular GP algorithms executed over real-world graphs, we show that CSR++ remains close to CSR in read-only concurrent performance (within 10% on average) while significantly outperforming CSR (by an order of magnitude) and LLAMA (by almost 2\u00d7) with frequent updates. We also show that both CSR++\u2019s update throughput and analytics performance exceed those of several state-of-the-art graph structures while maintaining low memory consumption when the workload includes updates.<\/jats:p>","DOI":"10.3390\/data8110166","type":"journal-article","created":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T10:51:28Z","timestamp":1699008688000},"page":"166","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Scalable Data Structure for Efficient Graph Analytics and In-Place Mutations"],"prefix":"10.3390","volume":"8","author":[{"given":"Soukaina","family":"Firmli","sequence":"first","affiliation":[{"name":"SIP Research Team, Rabat IT Center, EMI, Mohammed V University in Rabat, Morocco"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dalila","family":"Chiadmi","sequence":"additional","affiliation":[{"name":"SIP Research Team, Rabat IT Center, EMI, Mohammed V University in Rabat, Morocco"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2023,11,3]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Dhulipala, L., Blelloch, G., and Shun, J. (2017, January 24\u201326). Julienne: A Framework for Parallel Graph Algorithms Using Work-efficient Bucketing. Proceedings of the SPAA, New York, NY, USA.","DOI":"10.1145\/3087556.3087580"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Haubenschild, M., Then, M., Hong, S., and Chafi, H. (2016, January 24). ASGraph: A Mutable Multi-versioned Graph Container with High Analytical Performance. Proceedings of the GRADES, New York, NY, USA.","DOI":"10.1145\/2960414.2960422"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Macko, P., Marathe, V.J., Margo, D.W., and Seltzer, M.I. (2015, January 13\u201317). LLAMA: Efficient Graph Analytics Using Large Multiversioned Arrays. Proceedings of the ICDE, Seoul, Republic of Korea.","DOI":"10.1109\/ICDE.2015.7113298"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"1257","DOI":"10.14778\/3007263.3007265","article-title":"Using Domain-specific Languages for Analytic Graph Databases","volume":"9","author":"Sevenich","year":"2016","journal-title":"Proc. VLDB Endow."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Shun, J., and Blelloch, G.E. (2013, January 23\u201327). Ligra: A Lightweight Graph Processing Framework For Shared Memory. Proceedings of the PPoPP, Shenzhen, China.","DOI":"10.1145\/2442516.2442530"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Zhang, K., Chen, R., and Chen, H. (2015, January 7\u201311). NUMA-Aware Graph-Structured Analytics. Proceedings of the PPoPP, San Francisco, CA, USA.","DOI":"10.1145\/2688500.2688507"},{"key":"ref_7","unstructured":"Page, L., Brin, S., Motwani, R., and Winograd, T. (1999). The PagerRank Citation Ranking: Bringing Order to the Web, Stanford InfoLab. Technical Report."},{"key":"ref_8","unstructured":"Dias, V., Teixeira, C.H.C., Guedes, D., Meira, W., and Parthasarathy, S. (July, January 30). Fractal: A General-Purpose Graph Pattern Mining System. Proceedings of the SIGMOD, Amsterdam, The Netherlands."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Kankanamge, C., Sahu, S., Mhedbhi, A., Chen, J., and Salihoglu, S. (2017, January 14\u201319). Graphflow: An Active Graph Database. Proceedings of the SIGMOD, Chicago, IL, USA.","DOI":"10.1145\/3035918.3056445"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Mawhirter, D., and Wu, B. (2019, January 27\u201330). AutoMine: Harmonizing High-level Abstraction and High Performance for Graph Mining. Proceedings of the SOSP, Huntsville, ON, Canada.","DOI":"10.1145\/3341301.3359633"},{"key":"ref_11","unstructured":"(2023, November 02). Neo4j. Available online: http:\/\/www.neo4j.org."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Raman, R., van Rest, O., Hong, S., Wu, Z., Chafi, H., and Banerjee, J. (2014, January 22\u201327). PGX.ISO: Parallel and Efficient In-memory Engine for Subgraph Isomorphism. Proceedings of the GRADES, Snowbird, UT, USA.","DOI":"10.1145\/2621934.2621939"},{"key":"ref_13","unstructured":"Sakr, S., Elnikety, S., and He, Y. (November, January 29). G-SPARQL: A Hybrid Engine for Querying Large Attributed Graphs. Proceedings of the ACM CIKM, Maui, HI, USA."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"van Rest, O., Hong, S., Kim, J., Meng, X., and Chafi, H. (2016, January 24). PGQL: A Property Graph Query Language. Proceedings of the GRADES, Redwood Shores, CA, USA.","DOI":"10.1145\/2960414.2960421"},{"key":"ref_15","unstructured":"(2023, November 02). PGQL: Property Graph Query Language. Available online: http:\/\/pgql-lang.org\/."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Firmli, S., and Chiadmi, D. (2020, January 6\u20138). A Review of Engines for Graph Storage and Mutations. Proceedings of the EMENA-ISTL, Marrakesh, Morocco.","DOI":"10.1007\/978-3-030-36778-7_23"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1017\/nws.2016.20","article-title":"NetworKit: A Tool Suite For Large-Scale Complex Network Analysis","volume":"4","author":"Staudt","year":"2016","journal-title":"Netw. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Wheatman, B., and Xu, H. (2018, January 25\u201327). Packed Compressed Sparse Row: A Dynamic Graph Representation. Proceedings of the HPEC, Waltham, MA, USA.","DOI":"10.1109\/HPEC.2018.8547566"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cheng, R., Chen, E., Hong, J., Kyrola, A., Miao, Y., Weng, X., Wu, M., Yang, F., Zhou, L., and Zhao, F. (2012, January 10\u201313). Kineograph: Taking the Pulse of a Fast-changing and Connected World. Proceedings of the EuroSys, Bern, Switzerland.","DOI":"10.1145\/2168836.2168846"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Madduri, K., and Bader, D.A. (2009, January 23\u201329). Compact Graph Representations and Parallel Connectivity Algorithms for Massive Dynamic Network Analysis. Proceedings of the IPDPS, Rome, Italy.","DOI":"10.1109\/IPDPS.2009.5161060"},{"key":"ref_21","unstructured":"Kyrola, A., Blelloch, G., and Guestrin, C. (2012, January 8\u201310). GraphChi: Large-Scale Graph Computation on Just a PC. Proceedings of the OSDI, Hollywood, CA, USA."},{"key":"ref_22","first-page":"29","article-title":"GraphOne: A Data Store for Real-Time Analytics on Evolving Graphs","volume":"15","author":"Kumar","year":"2020","journal-title":"ACM Trans. Storage"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Ediger, D., McColl, R., Riedy, J., and Bader, D.A. (2012, January 10\u201312). STINGER: High performance data structure for streaming graphs. Proceedings of the HPEC, Waltham, MA, USA.","DOI":"10.1109\/HPEC.2012.6408680"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1053","DOI":"10.14778\/3447689.3447708","article-title":"Teseo and the Analysis of Structural Dynamic Graphs","volume":"14","author":"Boncz","year":"2021","journal-title":"Proc. VLDB Endow."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/S0097539701389956","article-title":"Cache-Oblivious B-Trees","volume":"35","author":"Bender","year":"2005","journal-title":"SIAM J. Comput."},{"key":"ref_26","unstructured":"Firmli, S., Trigonakis, V., Lozi, J.P., Psaroudakis, I., Weld, A., Chiadmi, D., Hong, S., and Chafi, H. (2021, January 13\u201315). CSR++: A Fast, Scalable, Update-Friendly Graph Data Structure. Proceedings of the OPODIS, Strasbourg, France."},{"key":"ref_27","unstructured":"(2023, November 02). GFE Driver Code. Available online: https:\/\/github.com\/cwida\/gfe_driver."},{"key":"ref_28","unstructured":"(2023, November 02). Gartner Top 10 Data and Analytics Trends for 2019. Available online: https:\/\/www.gartner.com\/smarterwithgartner\/gartner-top-10-data-analytics-trends\/."},{"key":"ref_29","unstructured":"Sun, W., Fokoue, A., Srinivas, K., Kementsietsidis, A., Hu, G., and Xie, G.T. (June, January 31). SQLGraph: An Efficient Relational-Based Property Graph Store. Proceedings of the SIGMOD, Melbourne, VIC, Australia."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Hong, S., Chafi, H., Sedlar, E., and Olukotun, K. (2012, January 3\u20137). Green-Marl: A DSL for Easy and Efficient Graph Analysis. Proceedings of the ASPLOS, London, UK.","DOI":"10.1145\/2150976.2151013"},{"key":"ref_31","unstructured":"(2023, November 02). SPARQL Query Language for RDF. Available online: http:\/\/www.w3.org\/TR\/rdf-sparql-query\/."},{"key":"ref_32","unstructured":"(2023, November 02). Tinkerpop, Gremlin. Available online: https:\/\/github.com\/tinkerpop\/gremlin\/wiki."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Bratsas, C., Chondrokostas, E., Koupidis, K., and Antoniou, I. (2021). The Use of National Strategic Reference Framework Data in Knowledge Graphs and Data Mining to Identify Red Flags. Data, 6.","DOI":"10.3390\/data6010002"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1038\/scientificamerican0501-34","article-title":"The Semantic Web","volume":"284","author":"Hendler","year":"2001","journal-title":"Sci. Am."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"265","DOI":"10.14778\/2535570.2488333","article-title":"A Distributed Graph Engine for Web Scale RDF Data","volume":"6","author":"Zeng","year":"2013","journal-title":"Proc. VLDB Endow."},{"key":"ref_36","unstructured":"(2023, November 02). Property Graph Model. Available online: https:\/\/github.com\/tinkerpop\/blueprints\/wiki\/Property-Graph-Model."},{"key":"ref_37","unstructured":"(2023, November 02). Oracle Parallel Graph AnalytiX (PGX). Available online: https:\/\/www.oracle.com\/middleware\/technologies\/parallel-graph-analytix.html."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Hong, S., Depner, S., Manhardt, T., van der Lugt, J., Verstraaten, M., and Chafi, H. (2015, January 15\u201320). PGX.D: A Fast Distributed Graph Processing Engine. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Austin, TX, USA.","DOI":"10.1145\/2807591.2807620"},{"key":"ref_39","unstructured":"Trigonakis, V., Lozi, J.P., Falt\u00edn, T., Roth, N.P., Psaroudakis, I., Delamare, A., Haprian, V., Iorgulescu, C., Koupy, P., and Lee, J. (2021, January 14\u201316). aDFS: An Almost Depth-First-Search Distributed Graph-Querying System. Proceedings of the 2021 USENIX Annual Technical Conference (USENIX ATC 21), Online."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Roth, N.P., Trigonakis, V., Hong, S., Chafi, H., Potter, A., Motik, B., and Horrocks, I. (2017, January 14\u201319). PGX.D\/Async: A Scalable Distributed Graph Pattern Matching Engine. Proceedings of the GRADES, Chicago, IL, USA.","DOI":"10.1145\/3078447.3078454"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Mariappan, M., and Vora, K. (2019, January 25\u201328). GraphBolt: Dependency-Driven Synchronous Processing of Streaming Graphs. Proceedings of the EuroSys, Dresden, Germany.","DOI":"10.1145\/3302424.3303974"},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Ediger, D., Riedy, J., Bader, D.A., and Meyerhenke, H. (2011, January 16\u201320). Tracking structure of streaming social networks. Proceedings of the IPDPSW, Anchorage, AK, USA.","DOI":"10.1109\/IPDPS.2011.326"},{"key":"ref_43","unstructured":"(2023, November 02). Boost Adjacency List Documentation. Available online: https:\/\/www.boost.org\/doc\/libs\/1_67_0\/libs\/graph\/doc\/adjacency_list.html."},{"key":"ref_44","unstructured":"Besta, M., Fischer, M., Kalavri, V., Kapralov, M., and Hoefler, T. (2019). Practice of Streaming and Dynamic Graphs: Concepts, Models, Systems, and Parallelism. arXiv."},{"key":"ref_45","unstructured":"Kallimanis, N.D., and Kanellou, E. (2016, January 13\u201316). Wait-free concurrent graph objects with dynamic traversals. Proceedings of the OPODIS, Madrid, Spain."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Busato, F., Green, O., Bombieri, N., and Bader, D.A. (2018, January 25\u201327). Hornet: An Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs. Proceedings of the HPEC, Waltham, MA, USA.","DOI":"10.1109\/HPEC.2018.8547541"},{"key":"ref_47","unstructured":"Feng, G., Meng, X., and Ammar, K. (November, January 29). DISTINGER: A distributed graph data structure for massive dynamic graph processing. Proceedings of the IEEE Big Data, Santa Clara, CA, USA."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Green, O., and Bader, D.A. (2016, January 13\u201315). cuSTINGER: Supporting Dynamic Graph Algorithms for GPUs. Proceedings of the HPEC, Westin Hotel, Waltham, MA, USA.","DOI":"10.1109\/HPEC.2016.7761622"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Wheatman, B., and Xu, H. (2021, January 10\u201311). A Parallel Packed Memory Array to Store Dynamic Graphs. Proceedings of the 2021 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), Virtual.","DOI":"10.1137\/1.9781611976472.3"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Besta, M., and Hoefler, T. (2015, January 15\u201319). Accelerating Irregular Computations with Hardware Transactional Memory and Active Messages. Proceedings of the 24th International Symposium on High-Performance Parallel and Distributed Computing, Portland, OR, USA.","DOI":"10.1145\/2749246.2749263"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Herlihy, M., and Moss, J.E.B. (1993, January 16\u201319). Transactional Memory: Architectural Support for Lock-Free Data Structures. Proceedings of the 1993, ISCA \u201993, San Diego, CA, USA.","DOI":"10.1145\/165123.165164"},{"key":"ref_52","unstructured":"Paradies, M., Lehner, W., and Bornh\u00f6vd, C. (July, January 29). GRAPHITE: An Extensible Graph Traversal Framework for Relational Database Management Systems. Proceedings of the SSDBM, La Jolla, CA, USA."},{"key":"ref_53","unstructured":"(2023, November 02). Green-Marl Code. Available online: https:\/\/github.com\/stanford-ppl\/Green-Marl."},{"key":"ref_54","unstructured":"Falsafi, B., Guerraoui, R., Picorel, J., and Trigonakis, V. (2016, January 20\u201321). Unlocking Energy. Proceedings of the USENIX ATC, Denver, CO, USA."},{"key":"ref_55","unstructured":"(2023, November 02). OpenMP. Available online: https:\/\/www.openmp.org."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"1317","DOI":"10.14778\/3007263.3007270","article-title":"LDBC Graphalytics: A Benchmark for Large-Scale Graph Analysis on Parallel and Distributed Platforms","volume":"9","author":"Iosup","year":"2016","journal-title":"Proc. VLDB Endow."},{"key":"ref_57","unstructured":"(2023, November 02). LLAMA Code. Available online: https:\/\/github.com\/goatdb\/llama."},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"David, T., Guerraoui, R., and Trigonakis, V. (2013, January 3\u20136). Everything You Always Wanted to Know about Synchronization but Were Afraid to Ask. Proceedings of the SOSP \u201913, Twenty-Fourth ACM Symposium on Operating Systems Principles, Farmington, PA, USA.","DOI":"10.1145\/2517349.2522714"},{"key":"ref_59","unstructured":"Evans, J. (2006, January 16). A Scalable Concurrent malloc(3) Implementation for FreeBSD. Proceedings of the BSDCan, Ottawa, ON, Canada."},{"key":"ref_60","unstructured":"Hunter, A.H., Kennelly, C., Gove, D., Ranganathan, P., Turner, P.J., and Moseley, T.J. (2021, January 14\u201316). Beyond malloc efficiency to fleet efficiency: A hugepage-aware memory allocator. Proceedings of the OSDI, Online."}],"container-title":["Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2306-5729\/8\/11\/166\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T21:16:40Z","timestamp":1760131000000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2306-5729\/8\/11\/166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,3]]},"references-count":60,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2023,11]]}},"alternative-id":["data8110166"],"URL":"https:\/\/doi.org\/10.3390\/data8110166","relation":{},"ISSN":["2306-5729"],"issn-type":[{"type":"electronic","value":"2306-5729"}],"subject":[],"published":{"date-parts":[[2023,11,3]]}}}