More Web Proxy on the site http://driver.im/

research-article

GiraphAsync: Supporting Online and Offline Graph Processing via Adaptive Asynchronous Message Processing

Authors:

Zhiguo FanAuthors Info & Claims

CIKM '16: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management

Pages 479 - 488

https://doi.org/10.1145/2983323.2983726

Published: 24 October 2016 Publication History

Abstract

It is highly desired for existing distributed graph processing systems to support both offline analytics and online queries adaptively. Existing offline graph analytics systems are mostly based on synchronous model. Although achieving high throughput, they suffer relatively high latency in answering simple queries due to synchronization overhead and slow convergence. On the other hand, online graph query systems adopting asynchronous model can response at any time, while incur overwhelmed messages and network packets, making them unable to meet the high throughput demand of offline analytics. In this work, we propose an adaptive asynchronous message processing (AAMP) method, which improves the efficiency of network communication while maintains low latency, to efficiently support offline analytics and online queries in one graph processing framework. We then design GiraphAsync, an implementation of AAMP on top of Apache Giraph, and evaluate it using several representative offline analytics and online queries on large graph datasets. Experimental results show that GiraphAsync gains an up to 10X improvement over synchronous model systems for graph analytics, while performs as well as specialized systems for online graph queries.

References

[1]

Apache Giraph. http://incubator.apache.org/giraph/.

[2]

Jena. http://jena.apache.org/.

[3]

Neo4j. http://neo4j.com/.

[4]

M. Atre, V. Chaoji, M. J. Zaki, and J. A. Hendler. Matrix "bit" loaded: a scalable lightweight join query processor for rdf data. In WWW, pages 41--50, 2010.

Digital Library

[5]

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 3rd edition.

Digital Library

[6]

J. Gao, C. Zhou, J. Zhou, and J. X. Yu. Continuous pattern detection over billion-edge graph using distributed framework. In ICDE, pages 556--567, 2014.

[7]

G.Malewicz, M.H.Austern, A.J.C.Bik, J.C.Dehnert, I.Horn, N.Leiser, and G.Czajkowski. Pregel: a system for large-scale graph processing. In SIGMOD, pages 135--146, 2010.

Digital Library

[8]

Y. Guo, Z. Pan, and J. Heflin. Lubm: A benchmark for owl knowledge base systems. Journal of Web Semantics, 3(2--3):158--182, 2005.

Digital Library

[9]

M. Han and K. Daudjee. Giraph unchained: Barrierless asynchronous parallel execution in pregel-like graph processing systems. PVLDB, 8(9), 2015.

Digital Library

[10]

M. Han, K. Daudjee, K. Ammar, M. Tamerozsu, X. Wang, and T. Jin. An experimental comparison of pregel-like graph processing systems. PVLDB, 7(12):1047--1058, 2014.

Digital Library

[11]

B. Iordanov. Hypergraphdb: a generalized graph database. In WAIM, pages 25--36. Springer, 2010.

Digital Library

[12]

K.Haewoon, L.Changhyun, P.Hosung, and M.Sue. What is Twitter, a social network or a news media? In WWW, pages 591--600, 2010.

Digital Library

[13]

A. Kyrola, G. Blelloch, and C. Guestrin. Graphchi:large-scale graph computation on just a pc. OSDI, pages 31--46, 2012.

Digital Library

[14]

Y. Low, D. Bickson, J. Gonzalez, C. Guestrin, A. Kyrola, and J. M. Hellerstein. Distributed graphlab: A framework for machine learning and data mining in the cloud. PVLDB, 5(8):716--727, 2012.

Digital Library

[15]

Y. Lu, J. Cheng, D. Yan, and H. Wu. Large-scale distributed graph computing systems: An experimental evaluation. PVLDB, 8(3):281--292, 2014.

Digital Library

[16]

R. R. McCune, T. Weninger, and G. Madey. Thinking like a vertex: a survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Comput. Surv., 48(2), 2015.

Digital Library

[17]

T. Neumann and G. Weikum. Rdf-3x: a risc-style engine for rdf. PVLDB, 1(1), 2008.

Digital Library

[18]

M. Sarwat, S. Elnikety, Y. He, and M. F. Mokbel. Horton

[19]

: A distributed system for processing declarative reachability queries over partitioned graphs. PVLDB, 6(14), 2013.

Digital Library

[20]

B. Shao, H. Wang, and Y. Li. Trinity: A distributed graph engine on a memory cloud. In SIGMOD, pages 505--516, 2013.

Digital Library

[21]

Y. Tian, A. Balmin, S. A. Corsten, S. Tatikonda, and J. McPherson. From "think like a vertex" to "think like a graph". PVLDB, 7(3):193--204, 2013.

Digital Library

[22]

U.Kang, C.E.Tsourakakis, and C.Faloutsos. Pegasus: A peta-scale graph mining system. In ICDE, pages 229--238, 2009.

Digital Library

[23]

L. G. Valiant. A bridging model for parallel computation. Commun. ACM, 33(8):103--111, 1990.

Digital Library

[24]

G. Wang, W. Xie, A. Demers, and J. Gehrke. Asynchronous large-scale graph processing made easy. In CIDR, 2013.

[25]

C. Xie, R. Chen, H. Guan, B. Zang, and H. Chen. ync or async: Time to fuse for distributed graph-parallel computation. PPoPP, 2015.

Digital Library

[26]

Y. Zhang, Q. Gao, L. Gao, and C. Wang. Accelerate large-scale iterative computation through asynchronous accumulative updates. In ScienceCloud '12, pages 13--22, 2012.

Digital Library

[27]

C. Zhou, J. Gao, B. Sun, and J. X. Yu. Mocgraph: Scalable distributed graph processing using message online computing. PVLDB, 8(4):377--388, 2014.

Digital Library

Cited By

IWASAKI HEMOTO KMORIHATA AMATSUZAKI KHU Z(2022)Fregel: a functional domain-specific language for vertex-centric large-scale graph processingJournal of Functional Programming10.1017/S095679682100027732Online publication date: 20-Jan-2022
https://doi.org/10.1017/S0956796821000277
Coimbra MFrancisco AVeiga L(2021)An analysis of the graph processing landscapeJournal of Big Data10.1186/s40537-021-00443-98:1Online publication date: 9-Apr-2021
https://doi.org/10.1186/s40537-021-00443-9
Wang XWei XGao SLiu YLi Z(2019)A Novel Auction-Based Query Pricing SchemaInternational Journal of Parallel Programming10.1007/s10766-017-0534-x47:4(759-780)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s10766-017-0534-x
Show More Cited By

Index Terms

GiraphAsync: Supporting Online and Offline Graph Processing via Adaptive Asynchronous Message Processing
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Hypergraphs

Recommendations

A survey of current challenges in partitioning and processing of graph-structured data in parallel and distributed systems
Abstract
One of the concepts that attracts attention since entering of big data era is the graph-structured data. Suitable frameworks to handle such data would face several constraints, especially scalability, partitioning challenges, processing complexity ...
Random Walk TripleRush: Asynchronous Graph Querying and Sampling
WWW '15: Proceedings of the 24th International Conference on World Wide Web

Most Semantic Web applications rely on querying graphs, typically by using SPARQL with a triple store. Increasingly, applications also analyze properties of the graph structure to compute statistical inferences. The current Semantic Web infrastructure, ...
PMGraph: Accelerating Concurrent Graph Queries over Streaming Graphs
There are usually a large number of concurrent graph queries (CGQs) requirements in streaming graphs. However, existing graph processing systems mainly optimize a single graph query in streaming graphs or CGQs in static graphs. They have a large number of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '16: Proceedings of the 25th ACM International on Conference on Information and Knowledge Management

October 2016

2566 pages

ISBN:9781450340731

DOI:10.1145/2983323

General Chairs:
Snehasis Mukhopadhyay
Indiana University Purdue University Indianapolis, USA
,
ChengXiang Zhai
University of Illinois at Urbana-Champaign, USA
,
Program Chairs:
Elisa Bertino
Purdue University
,
Fabio Crestani
University of Lugano
,
Javed Mostafa
University of North Carolina
,
Jie Tang
Tsinghua University
,
Luo Si
Alibaba Group Inc & Purdue University
,
Xiaofang Zhou
University of Queensland
,
Yi Chang
Yahoo Research
,
Yunyao Li
IBM Research - Almaden
,
Parikshit Sondhi
WalmartLabs

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 24 October 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CIKM'16

Sponsor:

CIKM'16: ACM Conference on Information and Knowledge Management

October 24 - 28, 2016

Indiana, Indianapolis, USA

Acceptance Rates

CIKM '16 Paper Acceptance Rate 160 of 701 submissions, 23%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
239
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

IWASAKI HEMOTO KMORIHATA AMATSUZAKI KHU Z(2022)Fregel: a functional domain-specific language for vertex-centric large-scale graph processingJournal of Functional Programming10.1017/S095679682100027732Online publication date: 20-Jan-2022
https://doi.org/10.1017/S0956796821000277
Coimbra MFrancisco AVeiga L(2021)An analysis of the graph processing landscapeJournal of Big Data10.1186/s40537-021-00443-98:1Online publication date: 9-Apr-2021
https://doi.org/10.1186/s40537-021-00443-9
Wang XWei XGao SLiu YLi Z(2019)A Novel Auction-Based Query Pricing SchemaInternational Journal of Parallel Programming10.1007/s10766-017-0534-x47:4(759-780)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s10766-017-0534-x
Morihata AEmoto KMatsuzaki KHu ZIwasaki H(2018)Optimizing Declarative Parallel Distributed Graph Processing by Using Constraint SolversFunctional and Logic Programming10.1007/978-3-319-90686-7_11(166-181)Online publication date: 24-Apr-2018
https://doi.org/10.1007/978-3-319-90686-7_11

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents