  Partitioning graphs into blocks of roughly equal size is widely used when
processing large graphs. Currently there is a gap in the space of available
partitioning algorithms. On the one hand, there are streaming algorithms that
have been adopted to partition massive graph data on small machines. In the
streaming model, vertices arrive one at a time including their neighborhood and
then have to be assigned directly to a block. These algorithms can partition
huge graphs quickly with little memory, but they produce partitions with low
solution quality. On the other hand, there are offline (shared-memory)
multilevel algorithms that produce partitions with high quality but also need a
machine with enough memory. We make a first step to close this gap by
presenting an algorithm that computes significantly improved partitions of huge
graphs using a single machine with little memory in streaming setting. First,
we adopt the buffered streaming model which is a more reasonable approach in
practice. In this model, a processing element can store a buffer, or batch, of
nodes before making assignment decisions. When our algorithm receives a batch
of nodes, we build a model graph that represents the nodes of the batch and the
already present partition structure. This model enables us to apply multilevel
algorithms and in turn compute much higher quality solutions of huge graphs on
cheap machines than previously possible. To partition the model, we develop a
multilevel algorithm that optimizes an objective function that has previously
shown to be effective for the streaming setting. This also removes the
dependency on the number of blocks k from the running time compared to the
previous state-of-the-art. Overall, our algorithm computes, on average, 75.9%
better solutions than Fennel using a very small buffer size. In addition, for
large values of k our algorithm becomes faster than Fennel.
