Back to search

University of British Columbia

Vertex-and-edge ordering for faster parallel graph processing

Abstract

dc:description

Graph structured data, which models complex relationships, describes data in myriad domains, such as social network analysis, protein structure analysis, and supply chain management. As the size of graph data grows, researchers develop modern systems to handle massive datasets with trillions of entries. To accelerate processing, systems optimize the data layout of vertices and edges in memory or on disk, but, to date, researchers have treated the performance improvements due to vertex and edge orderings separately. This work investigates the interaction between vertex and edge orderings. We explore whether combining these orderings improves performance. An extensive performance study of different orderings finds that a specific combination, the SlashBurn vertex order and the Hilbert edge order, consistently provides the fastest runtimes for scale-free graphs. These results motivate our development of a parallelized SlashBurn and the Rhubarb edge ordering and blocking technique. Using 14 cores, Parallel SlashBurn is up to 11.96× faster than the sequential implementation. Rhubarb enables the scalable implementation of parallel edge-centric algorithms using the Hilbert curve and offers end-to-end performance speedup for the Collaborative Filtering application of up to more than 2.5× over modern parallel Graph Processing Systems.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Trostanovsky, Alex
Contributors dc:contributor
  • Seltzer, Margo

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/86136

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Trostanovsky, Alex. Vertex-and-edge ordering for faster parallel graph processing. master's thesis, University of British Columbia, 2023. http://hdl.handle.net/2429/86136