Open Collections

Trostanovsky, Alex

University of British Columbia

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.

Text

2023-10-12

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/86136

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/