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

Bruno Morais; Miguel E. Coimbra; Luís Veiga — 2022 — Springer, Cham

Key information

Authors:

Bruno Morais; Miguel E. Coimbra (Miguel E. Coimbra); Luís Veiga (Luís Manuel Antunes Veiga)

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

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)

WOS:000882964000009

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