Conference In: orcid
PK-Graph: Partitioned k²-Trees to Enable Compact and Dynamic Graphs in Spark GraphX
Cooperative Information Systems – 28th International Conference, CoopIS 2022, Bozen-Bolzano, Italy, October 4–7, 2022, Proceedings
— 2022 — Springer, Cham
Key information
Authors:
Published in
September 25, 2022
Abstract
Graphs are becoming increasingly larger, with datasets having millions of vertices and billions (or even trillions) of edges. As a result, the ability to fit the entire graph into the main memory of a single machine faces challenges in common hardware, even more so in edge/IoT-like devices (i.e., more energy efficient but also more resource constrained). Reading the graph from secondary storage may pose in itself significant overhead, negatively impacting query performance and storage requirements. It thus becomes relevant to explore techniques to optimize the storage of graphs, specially in memory, in a way that circumvents space limitations, while avoiding compromising the performance of processing. We observe that current graph storage systems manage the graph representation by storing graphs in an uncompressed format, either: i) in a shared architecture which leads to a higher space overhead and the inability to represent the graph entirely in main memory, or ii) in a distributed architecture, where the graph dataset is partitioned over a cluster of machines with each one storing in main memory only a fragment (shard) of the (uncompressed) graph. We present PK-Graph, our proposal which extends a distributed graph processing system, highly used in academia and industry (Spark GraphX), in order to deploy the use of a compressed graph representation, with added support for dynamic updatable graphs (not currently supported in GraphX). Our experimental results show that PK-Graph can achieve up to 50% lower graph memory usage, while maintaining competitive performance in executing typical graph operations used in common applications.
Publication details
Authors in the community:
Miguel E. Coimbra
ist162460
Luís Manuel Antunes Veiga
ist14191
Publisher
Springer, Cham
Link to the publisher's version
https://link.springer.com/chapter/10.1007/978-3-031-17834-4_9
Title of the publication container
Cooperative Information Systems – 28th International Conference, CoopIS 2022, Bozen-Bolzano, Italy, October 4–7, 2022, Proceedings
Location of the conference
Bozen-Bolzano, Italy
Conference date start
October 4, 2022
Conference date end
October 7, 2022
First page or article number
149
Last page
167
Volume
13591
ISBN
978-3-031-17834-4
ISSN
1611-3349
WoS (Web of Science)
Fields of Science and Technology (FOS)
computer-and-information-sciences - Computer and information sciences
Keywords
- Compression
- Graph databases
- Graph processing systems
- Graph representation
- Optimization
Publication language (ISO code)
eng - English
Rights type:
Only metadata available