  Distributed systems that manage and process graph-structured data internally
solve a graph partitioning problem to minimize their communication overhead and
query run-time. Besides computational complexity -- optimal graph partitioning
is NP-hard -- another important consideration is the memory overhead.
Real-world graphs often have an immense size, such that loading the complete
graph into memory for partitioning is not economical or feasible. Currently,
the common approach to reduce memory overhead is to rely on streaming
partitioning algorithms. While the latest streaming algorithms lead to
reasonable partitioning quality on some graphs, they are still not completely
competitive to in-memory partitioners. In this paper, we propose a new system,
Hybrid Edge Partitioner (HEP), that can partition graphs that fit partly into
memory while yielding a high partitioning quality. HEP can flexibly adapt its
memory overhead by separating the edge set of the graph into two sub-sets. One
sub-set is partitioned by NE++, a novel, efficient in-memory algorithm, while
the other sub-set is partitioned by a streaming approach. Our evaluations on
large real-world graphs show that in many cases, HEP outperforms both in-memory
partitioning and streaming partitioning at the same time. Hence, HEP is an
attractive alternative to existing solutions that cannot fine-tune their memory
overheads. Finally, we show that using HEP, we achieve a significant speedup of
distributed graph processing jobs on Spark/GraphX compared to state-of-the-art
partitioning algorithms.
