title: MMap: Fast Billion-Scale Graph Computation on a PC via Memory Mapping.
abstract: Graph computation approaches such as GraphChi and TurboGraph recently demonstrated that a single PC can perform efficient computation on billion-node graphs. To achieve high speed and scalability, they often need sophisticated data structures and memory management strategies. We propose a minimalist approach that forgoes such requirements, by leveraging the fundamentalmemory mapping(MMap) capability found on operating systems. We contribute: (1) a new insight that MMap is a viable technique for creating fast and scalable graph algorithms that surpasses some of the best techniques; (2) the design and implementation of popular graph algorithms for billion-scale graphs with little code, thanks to memory mapping; (3) extensive experiments on real graphs, including the 6.6 billion edge YahooWeb graph, and show that this new approach is significantly faster or comparable to the highly-optimized methods (e.g., 9.5× faster than GraphChi for computing PageRank on 1.47B edge Twitter graph). We believe our work provides a new direction in the design and development of scalable algorithms. Our packaged code is available at http://poloclub.gatech.edu/mmap/.
authors: Georgia Tech, Atlanta, Georgia.
authors: Zhiyuan
authors: Z
authors: Lin
authors: Georgia Tech, Atlanta, Georgia.
authors: Minsuk
authors: M
authors: Kahng
authors: Georgia Tech, Atlanta, Georgia.
authors: Kaeser Md
authors: KM
authors: Sabrin
authors: Georgia Tech, Atlanta, Georgia.
authors: Duen Horng Polo
authors: DH
authors: Chau
authors: KAIST, Daejeon, Republic of Korea.
authors: Ho
authors: H
authors: Lee
authors: KAIST, Daejeon, Republic of Korea.
authors: U
authors: U
authors: Kang