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

research-article

Constructing Bisimulation Summaries on a Multi-Core Graph Processing Framework

Authors:

Shahan Khatchadourian,

Mariano P. ConsensAuthors Info & Claims

GRADES'15: Proceedings of the GRADES'15

Article No.: 8, Pages 1 - 7

https://doi.org/10.1145/2764947.2764955

Published: 31 May 2015 Publication History

Abstract

Bisimulation summaries of graph data have multiple applications, including facilitating graph exploration and enabling query optimization techniques, but efficient, scalable, summary construction is challenging. The literature describes parallel construction algorithms using message-passing, and these have been recently adapted to MapReduce environments. The fixpoint nature of bisimulation is well suited to iterative graph processing, but the existing MapReduce solutions do not drastically decrease per-iteration times as the computation progresses.

In this paper, we focus on leveraging parallel multi-core graph frameworks with the goal of constructing summaries in roughly the same amount of time that it takes to input the data into the framework (for a range of real world data graphs) and output the summary. To achieve our goal we introduce a singleton optimization that significantly reduces per-iteration times after only a few iterations. We present experimental results validating that our scalable GraphChi implementation achieves our goal with bisimulation summaries of million to billion edge graphs.

References

[1]

Big data: The next frontier for innovation, competition, and productivity. McKinsey & Company, May 2011.

[2]

R. Appuswamy, C. Gkantsidis, D. Narayanan, O. Hodson, and A. Rowstron. Scale-up vs Scale-out for Hadoop: Time to rethink? SOCC, 2013.

Digital Library

[3]

S. Blom and S. Orzan. A distributed algorithm for strong bisimulation reduction of state spaces. Electr. Notes Theor. Comput. Sci., 68(4):523--538, 2002.

[4]

A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, and J. Wiener. Graph structure in the web. Comput. Netw., 33(1-6):309--320, June 2000.

Digital Library

[5]

M. P. Consens, V. Fionda, S. Khatchadourian, and G. Pirrò. Rewriting Queries over Summaries of Big Data Graphs. AMW, 2014.

[6]

J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. Commun. ACM, 51(1):107--113, 2008.

Digital Library

[7]

A. Dovier, C. Piazza, and A. Policriti. An efficient algorithm for computing bisimulation equivalence. Theor. Comput. Sci., 311(1-3):221--256, 2004.

Digital Library

[8]

R. Goldman and J. Widom. DataGuides: Enabling query formulation and optimization in semistructured databases. In VLDB, pages 436--445, 1997.

Digital Library

[9]

O. Hassanzadeh and M. P. Consens. Linked movie data base. In LDOW, 2009.

[10]

M. R. Henzinger, T. A. Henzinger, and P. W. Kopke. Computing simulations on finite and infinite graphs. In Foundations of Computer Science, pages 453--462, 1995.

Digital Library

[11]

P. C. Kanellakis and S. A. Smolka. CCS expressions, finite state processes, and three problems of equivalence. Information and Computation, 86(1):43--68, 1990.

Digital Library

[12]

S. Khatchadourian and M. P. Consens. ExpLOD: Summary-Based Exploration of Interlinking and RDF Usage in the Linked Open Data Cloud. In ESWC, pages 272--287, 2010.

Digital Library

[13]

A. Kumar, J. Gluck, A. Deshpande, and J. Lin. Hone: "Scaling Down" Hadoop on Shared-Memory Systems. PVLDB, 6(12):1354--1357, 2013.

Digital Library

[14]

H. Kwak, C. Lee, H. Park, and S. Moon. What is Twitter, a social network or a news media? In WWW, pages 591--600. ACM, 2010.

Digital Library

[15]

A. Kyrola, G. Blelloch, and C. Guestrin. GraphChi: Large-scale graph computation on just a PC. In OSDI, pages 31--46, 2012.

Digital Library

[16]

Y. Luo, G. H. L. Fletcher, J. Hidders, P. De Bra, and Y. Wu. Regularities and dynamics in bisimulation reductions of big graphs. GRADES, 2013.

Digital Library

[17]

Y. Luo, Y. Lange, G. H. Fletcher, P. Bra, J. Hidders, and Y. Wu. Bisimulation Reduction of Big Graphs on MapReduce. In BNCOD, volume 7968, pages 189--203. 2013.

Digital Library

[18]

A. Mislove, M. Marcon, K. P. Gummadi, P. Druschel, and B. Bhattacharjee. Measurement and analysis of online social networks. In SIGCOMM Conference on Internet Measurement, pages 29--42, 2007.

Digital Library

[19]

R. Paige and R. E. Tarjan. Three partition refinement algorithms. SIAM Journal on Computing, 16(6):973--989, 1987.

Digital Library

[20]

M. Rudolf, M. Paradies, C. Bornhövd, and W. Lehner. Synopsys: large graph analytics in the SAP HANA database through summarization. In GRADES, 2013.

Digital Library

[21]

D. Sangiorgi. On the origins of bisimulation and coinduction. Trans. Program. Lang. Syst., 31(4), 2009.

Digital Library

[22]

A. Schätzle, A. Neu, G. Lausen, and M. Przyjaciel-Zablocki. Large-scale bisimulation of RDF graphs. SWIM, 2013.

Digital Library

[23]

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

Digital Library

Cited By

Goasdoué FGuzewicz PManolescu I(2020)RDF graph summarization for first-sight structure discoveryThe VLDB Journal10.1007/s00778-020-00611-yOnline publication date: 30-Apr-2020
https://doi.org/10.1007/s00778-020-00611-y
Zneika MVodislav DKotzinos DThakker DSchwabe DGarcía RKozaki KBrambilla MDimitrova V(2019)Quality metrics for RDF graph summarizationSemantic Web10.3233/SW-19034610:3(555-584)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.3233/SW-190346
Guzewicz PManolescu I(2019)Parallel quotient summarization of RDF graphsProceedings of the International Workshop on Semantic Big Data10.1145/3323878.3325809(1-6)Online publication date: 5-Jul-2019
https://dl.acm.org/doi/10.1145/3323878.3325809
Show More Cited By

Index Terms

Constructing Bisimulation Summaries on a Multi-Core Graph Processing Framework
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Frameworks

Recommendations

Big Graph Processing Systems: State-of-the-Art and Open Challenges
BIGDATASERVICE '15: Proceedings of the 2015 IEEE First International Conference on Big Data Computing Service and Applications

Graph is a fundamental data structure that captures relationships between different data entities. In practice, graphs are widely used for modeling complicated data in different application domains such as social networks, protein networks, ...
Constructing connected bicritical graphs with edge-connectivity 2

A graph G is said to be bicritical if the removal of any pair of vertices decreases the domination number of G . For a bicritical graph G with the domination number t , we say that G is t -bicritical. Let λ ( G ) denote the edge-connectivity of G . In 2]...
Apache Spark Graph Processing

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GRADES'15: Proceedings of the GRADES'15

May 2015

54 pages

ISBN:9781450336116

DOI:10.1145/2764947

Copyright © 2015 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 the author(s) 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

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

SIGMOD/PODS'15

Sponsor:

SIGMOD

SIGMOD/PODS'15: International Conference on Management of Data

May 31 - June 4, 2015

VIC, Melbourne, Australia

Acceptance Rates

Overall Acceptance Rate 29 of 61 submissions, 48%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
120
Total Downloads

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

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Goasdoué FGuzewicz PManolescu I(2020)RDF graph summarization for first-sight structure discoveryThe VLDB Journal10.1007/s00778-020-00611-yOnline publication date: 30-Apr-2020
https://doi.org/10.1007/s00778-020-00611-y
Zneika MVodislav DKotzinos DThakker DSchwabe DGarcía RKozaki KBrambilla MDimitrova V(2019)Quality metrics for RDF graph summarizationSemantic Web10.3233/SW-19034610:3(555-584)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.3233/SW-190346
Guzewicz PManolescu I(2019)Parallel quotient summarization of RDF graphsProceedings of the International Workshop on Semantic Big Data10.1145/3323878.3325809(1-6)Online publication date: 5-Jul-2019
https://dl.acm.org/doi/10.1145/3323878.3325809
Čebirić ŠGoasdoué FKondylakis HKotzinos DManolescu ITroullinou GZneika M(2019)Summarizing semantic graphsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-018-0528-328:3(295-327)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1007/s00778-018-0528-3
Guzewicz PManolescu I(2018)Quotient RDF Summaries Based on Type Hierarchies2018 IEEE 34th International Conference on Data Engineering Workshops (ICDEW)10.1109/ICDEW.2018.00018(66-71)Online publication date: Apr-2018
https://doi.org/10.1109/ICDEW.2018.00018

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