Show simple item record

dc.contributor.authorSabrin, Kaeser Md.
dc.contributor.authorLin, Zhiyuan
dc.contributor.authorChau, Duen Horng (Polo)
dc.contributor.authorLee, Ho
dc.contributor.authorKang, U.
dc.date.accessioned2013-10-17T19:43:19Z
dc.date.available2013-10-17T19:43:19Z
dc.date.issued2013
dc.identifier.urihttp://hdl.handle.net/1853/49226
dc.descriptionResearch area: Graph Mining Algorithmsen_US
dc.description.abstractLarge graphs with billions of nodes and edges are increasingly common, calling for new kinds of scalable computation frameworks. State-of-the-art approaches such as GraphChi and TurboGraph recently demonstrated that a single PC can efficiently perform advanced computation on billion-node graphs. Although fast, they use sophisticated data structures, explicit memory management, and optimization techniques to achieve high speed and scalability. We propose a minimalist approach that forgoes such complexities, by leveraging the fundamental memory mapping (MMap) capability found on operating systems. We present multiple, major findings; we contribute: (1) our crucial insight that MMap can be a viable technique for creating fast, scalable graph algorithms that surpass some of the best techniques; (2) a counterintuitive result that we can do less and gain more ; MMap enables us to use a much simpler data structure (edge list) and algorithm design, and to defer memory management to the OS, while offering significantly faster or comparable performance as highly-optimized methods (e.g., 10 X as fast as GraphChi PageRank on 1.47 billion edge Twitter graph); (3) we performed extensive experiments on real and synthetic graphs, including the 6.6 billion edge YahooWeb graph, and show that MMap’s benefits sustain in most conditions. We hope this work will inspire others to explore how memory mapping may help improve other methods or algorithms to further increase their speed and scalability.en_US
dc.language.isoen_USen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesCSE Technical Reports ; GT-CSE-13-04en_US
dc.subjectGraph miningen_US
dc.subjectMemory mappingen_US
dc.subjectScalable algorithmsen_US
dc.subjectSingle machineen_US
dc.titleMMAP: Mining Billion-Scale Graphs on a PC with Fast, Minimalist Approach via Memory Mappingen_US
dc.typeTechnical Reporten_US
dc.contributor.corporatenameGeorgia Institute of Technology. College of Computingen_US
dc.contributor.corporatenameGeorgia Institute of Technology. School of Computational Science and Engineeringen_US
dc.contributor.corporatenameKorea Advanced Institute of Science and Technology. Dept. of Computer Scienceen_US
dc.embargo.termsnullen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record