Back to search

University of British Columbia

2GP : two-phase graph partitioner

Abstract

dc:description

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.

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
  • Sinaee, Hadi
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/86218

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

Sinaee, Hadi. 2GP : two-phase graph partitioner. master's thesis, University of British Columbia, 2023. http://hdl.handle.net/2429/86218