Streaming Graph Partitioning for Large Graphs with Limited Memory

摘要

With the graph data scale constantly expanding, the personal computer has brought in severe challenge for the traditional graph partitioning because of its limited memory capacity. The streaming model has been applied in graph partitioning in recent years because it is more efficient than offline partitioning. However, the cache storage structure of original streaming method is inefficient for searching operations on the one hand, on the other hand, the efficiency gradually is reduced with the number of vertices which have been allocated increased because there is no space left for storing more in memory. A caching strategy for streaming algorithm is put forward in this paper including efficient cache storage structure, which uses the vertex and its neighbors' subset information as basic entry. The cache management module manages cache content. Our method is effective on the condition whether it has limitation to cache capacity or not. By using our cache strategy, it only takes about 25 minutes for partitioning twitter-2010 that have 1.4 billion edges while the original streaming method needs 42 minutes, As can prove the effectiveness and superiority of our method.