University of British Columbia
Vertex-and-edge ordering for faster parallel graph processing
Abstract
dc:descriptionGraph 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