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

tutorial

Managing and mining large graphs: systems and implementations

Authors:

Yanghua XiaoAuthors Info & Claims

SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data

Pages 589 - 592

https://doi.org/10.1145/2213836.2213907

Published: 20 May 2012 Publication History

Abstract

We are facing challenges at all levels ranging from infrastructures to programming models for managing and mining large graphs. A lot of algorithms on graphs are ad-hoc in the sense that each of them assumes that the underlying graph data can be organized in a certain way that maximizes the performance of the algorithm. In other words, there is no standard graph systems based on which graph algorithms are developed and optimized. In response to this situation, a lot of graph systems have been proposed recently. In this tutorial, we discuss several representative systems. Still, we focus on providing perspectives from a variety of standpoints on the goals and the means for developing a general purpose graph system. We highlight the challenges posed by the graph data, the constraints of architectural design, the different types of application needs, and the power of different programming models that support such needs.

This tutorial is complementary to the related tutorial "Managing and Mining Large Graphs: Patterns and Algorithms".

References

[1]

http://neo4j.org/.

[2]

https://github.com/twitter/flockdb.

[3]

http://www.facebook.com/press/info.php?statistics.

[4]

http://www.w3.org/.

[5]

http://www.worldwidewebsize.com/.

[6]

C. C. Aggarwal and H. Wang, editors. Managing and Mining Graph Data, volume 40 of Advances in Database Systems. Springer, 2010.

Digital Library

[7]

J. Cheng, J. X. Yu, B. Ding, P. S. Yu, and H. Wang. Fast graph pattern matching. In Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE '08, pages 913--922, Washington, DC, USA, 2008. IEEE Computer Society.

Digital Library

[8]

J. Cohen. Graph twiddling in a mapreduce world. Computing in Science & Engineering, pages 29--41, 2009.

Digital Library

[9]

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

Digital Library

[10]

E. Eifrem. A nosql overview and the benefits of graph databases. Nosql East 2009.

[11]

B. Iordanov. Hypergraphdb: a generalized graph database. In Proceedings of the 2010 international conference on Web-age information management, WAIM '10, pages 25--36, Berlin, Heidelberg, 2010. Springer-Verlag.

Digital Library

[12]

U. Kang, C. E. Tsourakakis, and C. Faloutsos. Pegasus: A peta-scale graph mining system implementation and observations. In Proceedings of the 2009 Ninth IEEE International Conference on Data Mining, ICDM '09, pages 229--238, Washington, DC, USA, 2009. IEEE Computer Society.

Digital Library

[13]

A. Lumsdaine, D. Gregor, B. Hendrickson, and J. W. Berry. Challenges in parallel graph processing. Parallel Processing Letters, 17(1):5--20, 2007.

[14]

G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the 2010 international conference on Management of data, SIGMOD '10, 2010.

Digital Library

[15]

B. Shao, H. Wang, and Y. Li. The Trinity graph engine. Technical Report 161291, Microsoft Research, 2012.

[16]

J. Ousterhout, P. Agrawal, D. Erickson, C. Kozyrakis, J. Leverich, D. Mazières, S. Mitra, A. Narayanan, G. Parulkar, M. Rosenblum, S. M. Rumble, E. Stratmann, and R. Stutsman. The case for ramclouds: scalable high-performance storage entirely in dram. SIGOPS Oper. Syst. Rev., 43:92--105, January 2010.

Digital Library

[17]

Z. Sun, H. Wang, B. Shao, H. Wang, and J. Li. Efficient subgraph matching on billion node graphs. In PVLDB, 2012.

Digital Library

[18]

W. Wu, H. Li, H. Wang, and K. Zhu. Probase: A probabilistic taxonomy for text understanding. In Proceedings of the 2012 international conference on Management of data, SIGMOD '12, 2012.

Digital Library

[19]

D. R. Zerbino and E. Birney. Velvet: algorithms for de novo short read assembly using de bruijn graphs. Genome Research, 18(5):821--9, 2008.

Cited By

Lazzaris JSilva MPereira TFaria VCompadrinho PMachado R(2024)Visualization of Information Through Complex Networks – An Applied Case of CMMI and OpenUp AlignmentProcedia Computer Science10.1016/j.procs.2024.06.231239(743-750)Online publication date: 2024
https://doi.org/10.1016/j.procs.2024.06.231
Bhattacharyya AChakravarty D(2024)Graph Database: Re-engineering Methodologies Relational to NOSQL DatabasesIntelligent Strategies for ICT10.1007/978-981-97-1260-1_12(131-146)Online publication date: 11-May-2024
https://doi.org/10.1007/978-981-97-1260-1_12
Gianinazzi LBesta MSchaffner YHoefler TAgrawal KAzar Y(2021)Parallel Algorithms for Finding Large Cliques in Sparse GraphsProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461800(243-253)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461800
Show More Cited By

Index Terms

Managing and mining large graphs: systems and implementations
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Information systems
  1. Data management systems
    1. Database management system engines
      1. Parallel and distributed DBMSs

Recommendations

Managing and mining large graphs: patterns and algorithms
SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data

Graphs are everywhere: social networks, the World Wide Web, biological networks, and many more. The sizes of graphs are growing at unprecedented rate, spanning millions and billions of nodes and edges. What are the patterns in large graphs, spanning ...
Large Induced Forests in Graphs

In this article, we prove three theorems. The first is that every connected graph of order n and size m has an induced forest of order at least 8n-2m-2/9 with equality if and only if such a graph is obtained from a tree by expanding every vertex to a ...
Connectivity of k-extendable graphs with large k
Discrete mathematics and theoretical computer science (DMTCS)

Let G be a simple connected graph on 2n vertices with perfect matching. For a given positive integer k (0 ≤ k ≤ n - 1), G is k-extendable if any matching of size k in G is contained in a perfect matching of G. It is proved that if G is a k-extendable ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data

May 2012

886 pages

ISBN:9781450312479

DOI:10.1145/2213836

General Chairs:
K. Selçuk Candan
Arizona State University
,
Yi Chen
Arizona State University
,
Richard Snodgrass
University of Arizona
,
Program Chair:
Luis Gravano
Columbia University
,
Publications Chair:
Ariel Fuxman
Microsoft Research

Copyright © 2012 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

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 May 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Tutorial

Conference

SIGMOD/PODS '12

Sponsor:

SIGMOD

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

May 20 - 24, 2012

Arizona, Scottsdale, USA

Acceptance Rates

SIGMOD '12 Paper Acceptance Rate 48 of 289 submissions, 17%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
1,171
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lazzaris JSilva MPereira TFaria VCompadrinho PMachado R(2024)Visualization of Information Through Complex Networks – An Applied Case of CMMI and OpenUp AlignmentProcedia Computer Science10.1016/j.procs.2024.06.231239(743-750)Online publication date: 2024
https://doi.org/10.1016/j.procs.2024.06.231
Bhattacharyya AChakravarty D(2024)Graph Database: Re-engineering Methodologies Relational to NOSQL DatabasesIntelligent Strategies for ICT10.1007/978-981-97-1260-1_12(131-146)Online publication date: 11-May-2024
https://doi.org/10.1007/978-981-97-1260-1_12
Gianinazzi LBesta MSchaffner YHoefler TAgrawal KAzar Y(2021)Parallel Algorithms for Finding Large Cliques in Sparse GraphsProceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3409964.3461800(243-253)Online publication date: 6-Jul-2021
https://dl.acm.org/doi/10.1145/3409964.3461800
Stergiopoulos GDedousis PGritzalis D(2021)Automatic analysis of attack graphs for risk mitigation and prioritization on large-scale and complex networks in Industry 4.0International Journal of Information Security10.1007/s10207-020-00533-4Online publication date: 27-Feb-2021
https://doi.org/10.1007/s10207-020-00533-4
Rost CGomez KTäschner MFritzsche PSchons LChrist LAdameit TJunghanns MRahm E(2021)Distributed temporal graph analytics with GRADOOPThe VLDB Journal10.1007/s00778-021-00667-431:2(375-401)Online publication date: 19-May-2021
https://doi.org/10.1007/s00778-021-00667-4
Junghanns MKießling MTeichmann NGómez KPetermann ARahm E(2018)Declarative and distributed graph analytics with GRADOOPProceedings of the VLDB Endowment10.14778/3229863.323624611:12(2006-2009)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.14778/3229863.3236246
Slota GRajamanickam S(2018)Experimental Design of Work Chunking for Graph Algorithms on High Bandwidth Memory Architectures2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2018.00097(875-884)Online publication date: May-2018
https://doi.org/10.1109/IPDPS.2018.00097
Zhou NZhou XZhang XWang S(2017)An I/O-Efficient Buffer Batch Replacement Policy for Update-Intensive Graph DatabasesData Science and Engineering10.1007/s41019-016-0026-91:4(231-241)Online publication date: 11-Jan-2017
https://doi.org/10.1007/s41019-016-0026-9
Jarrah MAl-Quraan MJararweh YAl-Ayyoub M(2017)MedGraphMultimedia Tools and Applications10.1007/s11042-016-3262-076:2(2769-2785)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1007/s11042-016-3262-0
Pan X(2016)A comparative evaluation of open-source graph processing platforms2016 17th IEEE/ACIS International Conference on Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing (SNPD)10.1109/SNPD.2016.7515920(325-330)Online publication date: May-2016
https://doi.org/10.1109/SNPD.2016.7515920
Show More Cited By

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