LFGraph: Simple and fast distributed graph analytics

Imranul Hoque, Indranil Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Distributed graph analytics frameworks must offer low and balanced communication and computation, low preprocessing overhead, low memory footprint, and scalability. We present LFGraph, a fast, scalable, distributed, in-memory graph analytics engine intended primarily for directed graphs. LFGraph is the first system to satisfy all of the above requirements. It does so by relying on cheap hash-based graph partitioning, while making iterations faster by using publish-subscribe information flow along directed edges, fetch-once communication, singlepass computation, and in-neighbor storage. Our analytical and experimental results show that when applied to real-life graphs, LFGraph is faster than the best graph analytics frameworks by factors of 1x-5x when ignoring partitioning time and by 1x-560x when including partitioning time.

Original languageEnglish (US)
Title of host publicationProceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013
PublisherAssociation for Computing Machinery, Inc
ISBN (Electronic)9781450324632
DOIs
StatePublished - Nov 3 2013
Event1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013 - Farmington, United States
Duration: Nov 3 2013Nov 6 2013

Publication series

NameProceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013

Other

Other1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013
CountryUnited States
CityFarmington
Period11/3/1311/6/13

    Fingerprint

ASJC Scopus subject areas

  • Computer Science Applications
  • Software
  • Computational Theory and Mathematics

Cite this

Hoque, I., & Gupta, I. (2013). LFGraph: Simple and fast distributed graph analytics. In Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013 (Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013). Association for Computing Machinery, Inc. https://doi.org/10.1145/2524211.2524218