article

Sortledton: a Universal Graph Data Structure

Authors:

Domagoj Margan,

Jana GicevaAuthors Info & Claims

ACM SIGMOD Record, Volume 52, Issue 1

Pages 17 - 25

https://doi.org/10.1145/3604437.3604442

Published: 08 June 2023 Publication History

Abstract

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 single edge updates updates.

References

[1]

S. Beamer, K. Asanovic, and D. A. Patterson. Direction-optimizing breadth-first search. Sci. Program., 21(3--4):137--148, 2013.

[2]

S. Beamer, K. Asanovic, and D. A. Patterson. The GAP benchmark suite. CoRR, abs/1508.03619, 2015.

[3]

S. Beamer, K. Asanovic, and D. A. Patterson. Locality exists in graph processing: Workload characterization on an ivy bridge server. In IEEE IISWC, pages 56--65, 2015.

Digital Library

[4]

M. Besta, E. Peter, R. Gerstenberger, M. Fischer, M. Podstawski, C. Barthels, G. Alonso, and T. Hoefler. Demystifying graph databases: Analysis and taxonomy of data organization, system designs, and graph queries. CoRR, abs/1910.09017, 2019.

[5]

M. Capota, T. Hegeman, A. Iosup, A. Prat-P´erez, O. Erling, and P. A. Boncz. Graphalytics: A big data benchmark for graph-processing platforms. In ACM GRADES, pages 7:1--7:6, 2015.

Digital Library

[6]

D. Dechev, P. Pirkelbauer, and B. Stroustrup. Lock-free dynamically resizable arrays. In Springer OPODIS, volume 4305, pages 142--156, 2006.

[7]

L. Dhulipala, G. E. Blelloch, and J. Shun. Low-latency graph streaming using compressed purely-functional trees. In K. S. McKinley and K. Fisher, editors, Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2019, Phoenix, AZ, USA, June 22--26, 2019, pages 918--934. ACM, 2019.

Digital Library

[8]

B. Ding, K. Zeng, and W. Yu. Alibaba sponsor talk at VLDB, 2020.

[9]

V. V. dos Santos Dias, C. H. C. Teixeira, D. O. Guedes, W. M. Jr., and S. Parthasarathy. Fractal: A general-purpose graph pattern mining system. In ACM SIGMOD, pages 1357--1374, 2019.

[10]

D. Ediger, R. McColl, E. J. Riedy, and D. A. Bader. STINGER: high performance data structure for streaming graphs. In IEEE HPEC, pages 1--5, 2012.

[11]

O. Erling, A. Averbuch, J. L. Larriba-Pey, H. Chafi, A. Gubichev, A. Prat-P´erez, M. Pham, and P. A. Boncz. The LDBC social network benchmark: Interactive workload. In ACM SIGMOD, pages 619--630, 2015.

Digital Library

[12]

P. Gupta, A. Mhedhbi, and S. Salihoglu. Integrating column-oriented storage and query processing techniques into graph database management systems. CoRR, abs/2103.02284, 2021.

[13]

P. Gupta, V. Satuluri, A. Grewal, S. Gurumurthy, V. Zhabiuk, Q. Li, and J. J. Lin. Real-time twitter recommendation: Online motif detection in large dynamic graphs. Proc. VLDB Endow., 7(13):1379--1380, 2014.

Digital Library

[14]

M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew. Optimistic parallelism requires abstractions. Commun. ACM, 52(9):89--97, 2009.

Digital Library

[15]

P. Kumar and H. H. Huang. Graphone: A data store for real-time analytics on evolving graphs. In USENIX FAST, pages 249--263, 2019.

[16]

D. D. Leo and P. A. Boncz. Fast concurrent reads and updates with pmas. In ACM GRADES-NDA, pages 8:1--8:8, 2019.

Digital Library

[17]

D. D. Leo and P. A. Boncz. Teseo and the analysis of structural dynamic graphs. Proc. VLDB Endow., 14(6):1053--1066, 2021.

Digital Library

[18]

J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, June 2014.

[19]

P. Macko, V. J. Marathe, D. W. Margo, and M. I. Seltzer. LLAMA: efficient graph analytics using large multiversioned arrays. In IEEE ICDE, pages 363--374, 2015.

[20]

A. Mhedhbi and S. Salihoglu. Optimizing subgraph queries by combining binary and worst-case optimal joins. Proc. VLDB Endow., 12(11):1692--1704, 2019.

Digital Library

[21]

P. Pandey, B. Wheatman, H. Xu, and A. Bulu¸c. Terrace: A hierarchical graph container for skewed dynamic graphs. In G. Li, Z. Li, S. Idreos, and D. Srivastava, editors, SIGMOD '21: International Conference on Management of Data, Virtual Event, China, June 20--25, 2021, pages 1372--1385. ACM, 2021.

[22]

K. Platz, N. Mittal, and S. Venkatesan. Concurrent unrolled skiplist. In IEEE ICDCS, pages 1579--1589, 2019.

[23]

X. Qiu, W. Cen, Z. Qian, Y. Peng, Y. Zhang, X. Lin, and J. Zhou. Real-time constrained cycle detection in large dynamic graphs. Proc. VLDB Endow., 11(12):1876--1888, 2018.

Digital Library

[24]

J. Reinders. Intel threading building blocks - outfitting C++ for multi-core processor parallelism. O'Reilly, 2007.

[25]

S. Sahu, A. Mhedhbi, S. Salihoglu, J. Lin, and M. T. ¨Ozsu. The ubiquity of large graphs and surprising challenges of graph processing. Proc. VLDB Endow., 11(4):420--431, 2017.

Digital Library

[26]

A. Sharma, J. Jiang, P. Bommannavar, B. Larson, and J. J. Lin. Graphjet: Real-time content recommendations at twitter. Proc. VLDB Endow., 9(13):1281--1292, 2016.

Digital Library

[27]

J. Shun and G. E. Blelloch. Ligra: a lightweight graph processing framework for shared memory. In ACM SIGPLAN PPoPP, pages 135--146, 2013.

Digital Library

[28]

X. Zhu, M. Serafini, X. Ma, A. Aboulnaga, W. Chen, and G. Feng. Livegraph: A transactional graph storage system with purely sequential adjacency list scans. Proc. VLDB Endow., 13(7):1020--1034, 2020.

Digital Library

Cited By

Chen CGao DZhang YWang QFu ZZhang XZhu JGu YYu G(2023)NeutronStream: A Dynamic GNN Training Framework with Sliding Window for Graph StreamsProceedings of the VLDB Endowment10.14778/3632093.363210817:3(455-468)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.14778/3632093.3632108

Recommendations

Technical Perspective: Sortledton: a Universal Graph Data Structure

Graph processing is becoming ubiquitous due to the proliferation of interconnected data in several domains, including life sciences, social networks, cybersecurity, finance and logistics, to name a few. In parallel with the growth of the underlying ...
Universal graphs
Local structure in graph classes

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 52, Issue 1

March 2023

118 pages

ISSN:0163-5808

DOI:10.1145/3604437

Editors:
Rada Chirkova
North Carolina State University
,
Vanessa Braganholo
Universidade Federal Fluminense
,
Wim Martens
University of Bayreuth
,
Manos Athanassoulis
DBrainstorming
,
Marcelo Arenas
Research Highlights
,
Marianne Winslett
University of Illinois
,
Susan B. Davidson
The Future of Data(base) Education
,
Lyublena Antova
Datometry
,
Aaron J. Elmore
University of Chicago
,
Kyriakos Mouratidis
Singapore Management University
,
Dan Olteanu
University of Oxford
,
Immanuel Trummer
Cornell University
,
Yannis Velegrakis
Utrecht University
,
Renata Borovica-Gajic
Surveys
,
Tamer Özsu
University of Waterloo
,
Pınar Tözün
IT University of Copenhagen
,
Wook-Shin Han
Research and Vision columns
,
Kenneth Ross
Research Highlights
,
Alfons Kemper
Technical University of Munich
,
Samuel Madden
MIT

Issue’s Table of Contents

Copyright © 2023 Copyright is held by the owner/author(s).

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2023

Published in SIGMOD Volume 52, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
152
Total Downloads

Downloads (Last 12 months)77
Downloads (Last 6 weeks)2

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen CGao DZhang YWang QFu ZZhang XZhu JGu YYu G(2023)NeutronStream: A Dynamic GNN Training Framework with Sliding Window for Graph StreamsProceedings of the VLDB Endowment10.14778/3632093.363210817:3(455-468)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.14778/3632093.3632108

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents