Master's Thesis
PK-Graph: Partitioned K²-Tree Graph
— 2021
Key information
Authors:
Supervisors:
Published in
November 16, 2021
Abstract
Graphs are becoming increasingly larger, having millions of vertices and billions (or even trillions) of edges in some cases. As a result, it's becoming harder and harder to fit the entire graph into the main-memory of a single machine. This may lead to significant overhead by having to read the graph from secondary storage. Thus causing an impact in the performance of queries and the storage requirements of the system. It is relevant to try to minimize the storage requirements of the graph data without degrading access time and, ideally, even improving it. Current graph storage systems store their graphs in an uncompressed format, either in a shared architecture, leading to high space overhead and the inability to store the entire graph in main memory or a distributed architecture, in which the entire graph is partitioned over a cluster of machines and each machine stores only a fragment of the graph in main memory. Our solution extends a distributed graph processing system to utilize a compressed representation of a graph while still allowing to update the graph data, all while maintaining the same processing performance and ideally even improving it.
Publication details
Authors in the community:
Bruno Alexandre Coimbra Morais
ist197321
Supervisors of this institution:
Luís Manuel Antunes Veiga
ist14191
Fields of Science and Technology (FOS)
electrical-engineering-electronic-engineering-information-engineering - Electrical engineering, electronic engineering, information engineering
Publication language (ISO code)
eng - English
Rights type:
Embargo lifted
Date available:
October 9, 2022
Institution name
Instituto Superior Técnico