Open Collections

Sinaee, Hadi

University of British Columbia

Graph partitioning is a crucial problem for processing and analyzing large graphs. The two main classes of graph partitioners are in-memory partitioners and streaming partitioners. In-memory partitioners require that the entire graph be read into memory before being partitioned into some number of partitions. Conversely, a streaming partitioner reads the graph one edge at a time and immediately places the source and destination vertices in a partition, unless they have already been placed. While in-memory partitioners produce higher-quality partitions, they require a large amount of memory and are slow, which makes them less practical for larger graphs. Streaming partitioners can partition large graphs quickly. However, since they lack more information about the overall graph, their placement decisions are not as good as in-memory partitioners, leading to lower-quality partitions. We designed and evaluated a two-phase partitioning algorithm (2GP) that combines the best of both worlds. 2GP has two phases: first, it read a portion of a graph into memory and partitions it using an in-memory partitioner. Then, it partitions the remaining graph using a streaming partitioner. 2GP achieves better partition quality than a state-of-the-art streaming partitioner with significantly better performance.

Text

2023-10-19

Attribution-NonCommercial-NoDerivatives 4.0 International

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

Computer Science

University of British Columbia

UBCV

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