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

Data storage equipment
Communication
Directed graphs
Scalability
Engines

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

LFGraph : Simple and fast distributed graph analytics. / Hoque, Imranul; Gupta, Indranil.

Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013. Association for Computing Machinery, Inc, 2013. (Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013).

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

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, 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013, Farmington, United States, 11/3/13. https://doi.org/10.1145/2524211.2524218
Hoque I, Gupta I. LFGraph: Simple and fast distributed graph analytics. In Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013. Association for Computing Machinery, Inc. 2013. (Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013). https://doi.org/10.1145/2524211.2524218
Hoque, Imranul ; Gupta, Indranil. / LFGraph : Simple and fast distributed graph analytics. Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013. Association for Computing Machinery, Inc, 2013. (Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013).
@inproceedings{2c5ebdaa94d14157a9ad4f69d1a42464,
title = "LFGraph: Simple and fast distributed graph analytics",
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.",
author = "Imranul Hoque and Indranil Gupta",
year = "2013",
month = "11",
day = "3",
doi = "10.1145/2524211.2524218",
language = "English (US)",
series = "Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013",
publisher = "Association for Computing Machinery, Inc",
booktitle = "Proceedings of the 1st ACM SIGOPS Conference on Timely Results in Operating Systems, TRIOS 2013",

}

TY - GEN

T1 - LFGraph

T2 - Simple and fast distributed graph analytics

AU - Hoque, Imranul

AU - Gupta, Indranil

PY - 2013/11/3

Y1 - 2013/11/3

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84958281064&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958281064&partnerID=8YFLogxK

U2 - 10.1145/2524211.2524218

DO - 10.1145/2524211.2524218

M3 - Conference contribution

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

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

PB - Association for Computing Machinery, Inc

ER -