Skip to main content
Top
Published in: Datenbank-Spektrum 2/2017

19-06-2017 | Schwerpunktbeitrag

Big Graph Data Analytics on Single Machines – An Overview

Authors: Marcus Paradies, Hannes Voigt

Published in: Datenbank-Spektrum | Issue 2/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Driven by a multitude of use cases, graph data analytics has become a hot topic in research and industry. Particularly on big graphs, performing complex analytical queries efficiently to derive new insights is a challenging task. Systems that aim at solving the technical part of this challenge are often referred to as graph processing systems. They allow expressing and executing analytic algorithms and queries, while hiding most of the technical details related to efficiently storing and processing graph data. Since 2010, work on graph processing systems for distributed systems as well as shared memory systems has virtually exploded. In this article, we give an overview of this work with the particular focus on graph processing systems for large multiprocessor machines. We describe the state of the art established in recent years and outline trends and challenges in research and development that point towards the future of graph processing systems.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Show more products
Literature
1.
go back to reference Abadi DJ, Marcus A, Madden S, Hollenbach KJ (2007) Scalable semantic web data management using vertical partitioning. VLDB. ACM, pp 411–422 Abadi DJ, Marcus A, Madden S, Hollenbach KJ (2007) Scalable semantic web data management using vertical partitioning. VLDB. ACM, pp 411–422
2.
go back to reference Aberger CR, Tu S, Olukotun K, Ré C (2016) Emptyheaded: a relational engine for graph processing. SIGMOD, pp 431–446 Aberger CR, Tu S, Olukotun K, Ré C (2016) Emptyheaded: a relational engine for graph processing. SIGMOD, pp 431–446
3.
go back to reference Agterdenbos E, Fletcher GHL, Chan C, Vansummeren S (2016) Empirical evaluation of guarded structural indexing. EDBT, pp 714–715 Agterdenbos E, Fletcher GHL, Chan C, Vansummeren S (2016) Empirical evaluation of guarded structural indexing. EDBT, pp 714–715
4.
go back to reference Ahn J, Hong S, Yoo S, Mutlu O, Choi K (2015) A scalable processing-in-memory accelerator for parallel graph processing. ISCA. ACM, pp 105–117 Ahn J, Hong S, Yoo S, Mutlu O, Choi K (2015) A scalable processing-in-memory accelerator for parallel graph processing. ISCA. ACM, pp 105–117
5.
go back to reference Ailamaki A, DeWitt DJ, Hill MD, Wood DA (1999) DBMss on a modern processor: where does time go? VLDB. Morgan Kaufmann, pp 266–277 Ailamaki A, DeWitt DJ, Hill MD, Wood DA (1999) DBMss on a modern processor: where does time go? VLDB. Morgan Kaufmann, pp 266–277
6.
go back to reference Álvarez-García S, Brisaboa NR, Ladra S, Pedreira O (2010) A compact representation of graph databases. MLG. ACM, pp 18–25 Álvarez-García S, Brisaboa NR, Ladra S, Pedreira O (2010) A compact representation of graph databases. MLG. ACM, pp 18–25
7.
go back to reference Angles R (2012) A comparison of current graph database models. GDM. IEEE, pp 171–177 Angles R (2012) A comparison of current graph database models. GDM. IEEE, pp 171–177
9.
go back to reference Angles R, Gutierrez C (2011) Subqueries in SPARQL. AMW 749:12 Angles R, Gutierrez C (2011) Subqueries in SPARQL. AMW 749:12
10.
go back to reference Angles R, Arenas M, Barceló P, Hogan A, Reutter JL, Vrgoc D (2016) Foundations of modern graph query languages. CoRR abs/1610.06264. Angles R, Arenas M, Barceló P, Hogan A, Reutter JL, Vrgoc D (2016) Foundations of modern graph query languages. CoRR abs/1610.06264.
12.
go back to reference Blandford DK, Blelloch GE, Kash IA (2004) An experimental analysis of a compact graph representation. ALENEX. SIAM, pp 49–61 Blandford DK, Blelloch GE, Kash IA (2004) An experimental analysis of a compact graph representation. ALENEX. SIAM, pp 49–61
13.
go back to reference Boldi P, Vigna S (2004) The webgraph framework I: compression techniques. WWW. ACM, pp 595–602 Boldi P, Vigna S (2004) The webgraph framework I: compression techniques. WWW. ACM, pp 595–602
14.
go back to reference Boldi P, Rosa M, Santini M, Vigna S (2011) Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. WWW. ACM, pp 587–596 Boldi P, Rosa M, Santini M, Vigna S (2011) Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. WWW. ACM, pp 587–596
15.
go back to reference Bornea MA, Dolby J, Kementsietsidis A, Srinivas K, Dantressangle P, Udrea O, Bhattacharjee B (2013) Building an efficient RDF store over a relational database. SIGMOD. ACM, pp 121–132 Bornea MA, Dolby J, Kementsietsidis A, Srinivas K, Dantressangle P, Udrea O, Bhattacharjee B (2013) Building an efficient RDF store over a relational database. SIGMOD. ACM, pp 121–132
16.
go back to reference Bornhövd C, Kubis R, Lehner W, Voigt H, Werner H (2012) Flexible information management, exploration and analysis in SAP HANA. DATA. SciTePress, pp 15–28 Bornhövd C, Kubis R, Lehner W, Voigt H, Werner H (2012) Flexible information management, exploration and analysis in SAP HANA. DATA. SciTePress, pp 15–28
17.
go back to reference Brisaboa NR, Ladra S, Navarro G (2009) k2-trees for compact web graph representation. SPIRE, pp 18–30 Brisaboa NR, Ladra S, Navarro G (2009) k2-trees for compact web graph representation. SPIRE, pp 18–30
18.
go back to reference Buluç A, Gilbert JR (2011) The Combinatorial BLAS: design, implementation, and applications. Int J High Perform Comput Appl 25(4):496–509CrossRef Buluç A, Gilbert JR (2011) The Combinatorial BLAS: design, implementation, and applications. Int J High Perform Comput Appl 25(4):496–509CrossRef
21.
go back to reference Chen R, Shi J, Chen Y, Chen H (2015) PowerLyra: differentiated graph computation and partitioning on skewed graphs. EuroSys. ACM, pp 1:1–1:15 Chen R, Shi J, Chen Y, Chen H (2015) PowerLyra: differentiated graph computation and partitioning on skewed graphs. EuroSys. ACM, pp 1:1–1:15
22.
go back to reference Cheng J, Liu Q, Li Z, Fan W, Lui JCS, He C (2015) VENUS: Vertex-centric streamlined graph computation on a single PC. ICDE. IEEE Computer Society, pp 1131–1142 Cheng J, Liu Q, Li Z, Fan W, Lui JCS, He C (2015) VENUS: Vertex-centric streamlined graph computation on a single PC. ICDE. IEEE Computer Society, pp 1131–1142
23.
go back to reference Chong EI, Das S, Eadon G, Srinivasan J (2005) An efficient SQL-based RDF querying scheme. VLDB. ACM, pp 1216–1227 Chong EI, Das S, Eadon G, Srinivasan J (2005) An efficient SQL-based RDF querying scheme. VLDB. ACM, pp 1216–1227
24.
go back to reference Chu E, Beckmann JL, Naughton JF (2007) The case for a wide-table approach to manage sparse relational data sets. SIGMOD. ACM, pp 821–832 Chu E, Beckmann JL, Naughton JF (2007) The case for a wide-table approach to manage sparse relational data sets. SIGMOD. ACM, pp 821–832
25.
go back to reference Claude F, Navarro G (2010) Extended compact web graph representations. In: Algorithms and applications, essays dedicated to Esko Ukkonen on the occasion of his 60th birthday. Springer, Berlin Heidelberg, pp 77–91 Claude F, Navarro G (2010) Extended compact web graph representations. In: Algorithms and applications, essays dedicated to Esko Ukkonen on the occasion of his 60th birthday. Springer, Berlin Heidelberg, pp 77–91
26.
go back to reference Claude F, Navarro G (2010) Fast and compact web graph representations. ACM Trans Web 4(4):16:1–16:31CrossRef Claude F, Navarro G (2010) Fast and compact web graph representations. ACM Trans Web 4(4):16:1–16:31CrossRef
27.
go back to reference Cong G, Makarychev K (2012) Optimizing large-scale graph analysis on a multi-threaded, multi-core platform. IPDPS. IEEE, pp 414–425 Cong G, Makarychev K (2012) Optimizing large-scale graph analysis on a multi-threaded, multi-core platform. IPDPS. IEEE, pp 414–425
28.
go back to reference Cormen TH, Leiserson CE, Rivest R, Stein C (2009) Introduction to Algorithms. Third Edition. MIT Press Cormen TH, Leiserson CE, Rivest R, Stein C (2009) Introduction to Algorithms. Third Edition. MIT Press
29.
go back to reference Crauser A, Mehlhorn K, Meyer U, Sanders P (1998) A parallelization of Dijkstra’s shortest path algorithm. MFCS. Springer, Berlin Heidelberg, pp 722–731MATH Crauser A, Mehlhorn K, Meyer U, Sanders P (1998) A parallelization of Dijkstra’s shortest path algorithm. MFCS. Springer, Berlin Heidelberg, pp 722–731MATH
31.
go back to reference Deppisch U (1986) S‑tree: a dynamic balanced signature index for office retrieval. SIGIR. ACM, pp 77–87 Deppisch U (1986) S‑tree: a dynamic balanced signature index for office retrieval. SIGIR. ACM, pp 77–87
32.
go back to reference Erling O, Mikhailov I (2007) RDF Support in the Virtuoso DBMS. CSSW 113:59–68 Erling O, Mikhailov I (2007) RDF Support in the Virtuoso DBMS. CSSW 113:59–68
33.
go back to reference Fan J, Raj AGS, Patel JM (2015) The case against specialized graph analytics engines. CIDR. Fan J, Raj AGS, Patel JM (2015) The case against specialized graph analytics engines. CIDR.
34.
go back to reference Fletcher GHL, Voigt H, Yakovets N (2017) Declarative graph querying in practice and theory. EDBT, pp 598–601 Fletcher GHL, Voigt H, Yakovets N (2017) Declarative graph querying in practice and theory. EDBT, pp 598–601
35.
go back to reference Gonzalez JE, Low Y, Gu H, Bickson D, Guestrin C (2012) Powergraph: distributed graph-parallel computation on natural graphs. OSDI. USENIX Association, pp 17–30 Gonzalez JE, Low Y, Gu H, Bickson D, Guestrin C (2012) Powergraph: distributed graph-parallel computation on natural graphs. OSDI. USENIX Association, pp 17–30
36.
go back to reference Gonzalez JE, Xin RS, Dave A, Crankshaw D, Franklin MJ, Stoica I (2014) GraphX: graph processing in a distributed dataflow framework. OSDI, pp 599–613 Gonzalez JE, Xin RS, Dave A, Crankshaw D, Franklin MJ, Stoica I (2014) GraphX: graph processing in a distributed dataflow framework. OSDI, pp 599–613
37.
go back to reference Grabowski S, Bieniecki W (2011) Merging adjacency lists for efficient web graph compression. ICMMI. Springer, Berlin Heidelberg, pp 385–392 Grabowski S, Bieniecki W (2011) Merging adjacency lists for efficient web graph compression. ICMMI. Springer, Berlin Heidelberg, pp 385–392
38.
go back to reference Green O, Dukhan M, Vuduc RW (2015) Branch-avoiding graph algorithms. SPAA. ACM, pp 212–223 Green O, Dukhan M, Vuduc RW (2015) Branch-avoiding graph algorithms. SPAA. ACM, pp 212–223
39.
go back to reference Gustavson FG (1978) Two fast algorithms for sparse matrices: multiplication and permuted transposition. Trans Math Softw 4(3):250–269MathSciNetCrossRefMATH Gustavson FG (1978) Two fast algorithms for sparse matrices: multiplication and permuted transposition. Trans Math Softw 4(3):250–269MathSciNetCrossRefMATH
40.
go back to reference Han M, Daudjee K (2015) Giraph unchained: Barrierless asynchronous parallel execution in Pregel-like graph processing systems. Proc VLDB Endow 8(9):950–961CrossRef Han M, Daudjee K (2015) Giraph unchained: Barrierless asynchronous parallel execution in Pregel-like graph processing systems. Proc VLDB Endow 8(9):950–961CrossRef
41.
go back to reference Han W, Lee S, Park K, Lee J, Kim M, Kim J, Yu H (2013) Turbograph: a fast parallel graph engine handling billion-scale graphs in a single PC. SIGKDD. ACM, pp 77–85 Han W, Lee S, Park K, Lee J, Kim M, Kim J, Yu H (2013) Turbograph: a fast parallel graph engine handling billion-scale graphs in a single PC. SIGKDD. ACM, pp 77–85
42.
go back to reference Hardavellas N, Pandis I, Johnson R, Mancheril N, Ailamaki A, Falsafi B (2007) Database servers on chip multiprocessors: limitations and opportunities. CIDR, pp 79–87 Hardavellas N, Pandis I, Johnson R, Mancheril N, Ailamaki A, Falsafi B (2007) Database servers on chip multiprocessors: limitations and opportunities. CIDR, pp 79–87
43.
go back to reference Harshvardhan FA, Amato NM, Rauchwerger L (2014) KLA: a new algorithmic paradigm for parallel graph computations. PACT. ACM, pp 27–38 Harshvardhan FA, Amato NM, Rauchwerger L (2014) KLA: a new algorithmic paradigm for parallel graph computations. PACT. ACM, pp 27–38
44.
go back to reference Hartig O (2014) Reconciliation of RDF* and property graphs. CoRR abs/1409.3288. Hartig O (2014) Reconciliation of RDF* and property graphs. CoRR abs/1409.3288.
45.
go back to reference Hauck M, Paradies M, Fröning H, Lehner W, Rauhe H (2015) Highspeed graph processing exploiting main-memory column stores. Euro-Par, pp 503–514 Hauck M, Paradies M, Fröning H, Lehner W, Rauhe H (2015) Highspeed graph processing exploiting main-memory column stores. Euro-Par, pp 503–514
46.
go back to reference Herrmann K, Voigt H, Lehner W (2014) Cinderella – adaptive online partitioning of irregularly structured data. SMDB. IEEE Computer Society, pp 284–291 Herrmann K, Voigt H, Lehner W (2014) Cinderella – adaptive online partitioning of irregularly structured data. SMDB. IEEE Computer Society, pp 284–291
47.
go back to reference Herrmann K, Voigt H, Lehner W (2014) Online horizontal partitioning of heterogeneous data. Inf Technol 56(1):4–12 Herrmann K, Voigt H, Lehner W (2014) Online horizontal partitioning of heterogeneous data. Inf Technol 56(1):4–12
48.
go back to reference Hong S, Oguntebi T, Olukotun K (2011) Efficient parallel graph exploration on multi-core CPU and GPU. PACT. IEEE Computer Society, pp 78–88 Hong S, Oguntebi T, Olukotun K (2011) Efficient parallel graph exploration on multi-core CPU and GPU. PACT. IEEE Computer Society, pp 78–88
49.
go back to reference Hong S, Chafi H, Sedlar E, Olukotun K (2012) Green-Marl: a DSL for easy and efficient graph analysis. ASPLOS. ACM, pp 349–362 Hong S, Chafi H, Sedlar E, Olukotun K (2012) Green-Marl: a DSL for easy and efficient graph analysis. ASPLOS. ACM, pp 349–362
50.
go back to reference Hong S, Lugt JVD, Welc A, Raman R, Chafi H (2013) Early experiences in using a domain-specific language for large-scale graph analysis. GRADES, p 5 Hong S, Lugt JVD, Welc A, Raman R, Chafi H (2013) Early experiences in using a domain-specific language for large-scale graph analysis. GRADES, p 5
51.
go back to reference Hong S, Rodia NC, Olukotun K (2013) On fast parallel detection of Strongly Connected Components (SCC) in small-world graphs. SC. ACM, pp 92:1–92:11 Hong S, Rodia NC, Olukotun K (2013) On fast parallel detection of Strongly Connected Components (SCC) in small-world graphs. SC. ACM, pp 92:1–92:11
52.
go back to reference Hong S, Salihoglu S, Widom J, Olukotun K (2014) Simplifying scalable graph processing with a domain-specific language. CGO. ACM, pp 208–218 Hong S, Salihoglu S, Widom J, Olukotun K (2014) Simplifying scalable graph processing with a domain-specific language. CGO. ACM, pp 208–218
53.
go back to reference Hong S, Depner S, Manhardt T, Lugt JVD, Verstraaten M, Chafi H (2015) PGX.D: a fast distributed graph processing engine. SC. ACM, pp 58:1–58:12 Hong S, Depner S, Manhardt T, Lugt JVD, Verstraaten M, Chafi H (2015) PGX.D: a fast distributed graph processing engine. SC. ACM, pp 58:1–58:12
54.
go back to reference Jindal A, Madden S (2014) GRAPHiQL: A graph intuitive query language for relational databases. BD. IEEE, pp 441–450 Jindal A, Madden S (2014) GRAPHiQL: A graph intuitive query language for relational databases. BD. IEEE, pp 441–450
55.
go back to reference Junghanns M, Petermann A, Neumann M, Rahm E (2017) Management and analysis of big graph data: current systems and open challenges. In: Handbook of big data technologies. Springer, Berlin Heidelberg, pp 457–505CrossRef Junghanns M, Petermann A, Neumann M, Rahm E (2017) Management and analysis of big graph data: current systems and open challenges. In: Handbook of big data technologies. Springer, Berlin Heidelberg, pp 457–505CrossRef
56.
go back to reference Junghanns M, Petermann A, Rahm E (2017) Distributed grouping of property graphs with GRADOOP. BTW. Junghanns M, Petermann A, Rahm E (2017) Distributed grouping of property graphs with GRADOOP. BTW.
57.
go back to reference Khan A, Elnikety S (2014) Systems for big-graphs. Proc VLDB Endow 7(13):1709–1710CrossRef Khan A, Elnikety S (2014) Systems for big-graphs. Proc VLDB Endow 7(13):1709–1710CrossRef
58.
go back to reference Khayyat Z, Awara K, Alonazi A, Jamjoom H, Williams D, Kalnis P (2013) Mizan: a system for dynamic load balancing in large-scale graph processing. EuroSys. ACM, pp 169–182 Khayyat Z, Awara K, Alonazi A, Jamjoom H, Williams D, Kalnis P (2013) Mizan: a system for dynamic load balancing in large-scale graph processing. EuroSys. ACM, pp 169–182
59.
go back to reference Kiefer T, Schlegel B, Lehner W (2013) Experimental evaluation of NUMA effects on database management systems. BTW 214:185–204 Kiefer T, Schlegel B, Lehner W (2013) Experimental evaluation of NUMA effects on database management systems. BTW 214:185–204
60.
go back to reference Kyrola A, Blelloch GE, Guestrin C (2012) Graphchi: large-scale graph computation on just a PC. OSDI. USENIX Association, pp 31–46 Kyrola A, Blelloch GE, Guestrin C (2012) Graphchi: large-scale graph computation on just a PC. OSDI. USENIX Association, pp 31–46
61.
go back to reference Leiserson CE (2010) The Cilk++ concurrency platform. J Supercomput 51(3):244–257CrossRef Leiserson CE (2010) The Cilk++ concurrency platform. J Supercomput 51(3):244–257CrossRef
62.
go back to reference Lin Z, Kahng M, Sabrin KM, Chau DHP, Lee H, Kang U (2014) Mmap: fast billion-scale graph computation on a PC via memory mapping. Big Data. IEEE, pp 159–164 Lin Z, Kahng M, Sabrin KM, Chau DHP, Lee H, Kang U (2014) Mmap: fast billion-scale graph computation on a PC via memory mapping. Big Data. IEEE, pp 159–164
63.
go back to reference Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein JM (2010) Graphlab: a new framework for parallel machine learning. UAI, pp 340–349 Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein JM (2010) Graphlab: a new framework for parallel machine learning. UAI, pp 340–349
64.
go back to reference Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein JM (2012) Distributed graphlab: a framework for machine learning in the cloud. Proc VLDB Endow 5(8):716–727CrossRef Low Y, Gonzalez J, Kyrola A, Bickson D, Guestrin C, Hellerstein JM (2012) Distributed graphlab: a framework for machine learning in the cloud. Proc VLDB Endow 5(8):716–727CrossRef
65.
go back to reference Macko P, Marathe VJ, Margo DW, Seltzer MI (2015) LLAMA: Efficient graph analytics using Large Multiversioned Arrays. ICDE. IEEE, pp 363–374 Macko P, Marathe VJ, Margo DW, Seltzer MI (2015) LLAMA: Efficient graph analytics using Large Multiversioned Arrays. ICDE. IEEE, pp 363–374
66.
go back to reference MacQueen JB (1967) Some methods for classification and analysis of multivariate observations. In: Proceedings 5‑th Berkeley Symposium on Mathematical Statistics and Probability, June 21 - July 18, 1965. vol 1. University of California Press, Berkeley CA, pp 281–297 MacQueen JB (1967) Some methods for classification and analysis of multivariate observations. In: Proceedings 5‑th Berkeley Symposium on Mathematical Statistics and Probability, June 21 - July 18, 1965. vol 1. University of California Press, Berkeley CA, pp 281–297
67.
go back to reference Malewicz G, Austern MH, Bik AJC, Dehnert JC, Horn I, Leiser N, Czajkowski G (2010) Pregel: a system for large-scale graph processing. SIGMOD. ACM, pp 135–146 Malewicz G, Austern MH, Bik AJC, Dehnert JC, Horn I, Leiser N, Czajkowski G (2010) Pregel: a system for large-scale graph processing. SIGMOD. ACM, pp 135–146
68.
go back to reference Martínez-Bazan N, Muntés-Mulero V, Gómez-Villamor S, Nin J, Sánchez-Martínez M, Larriba-Pey J (2007) DEX: high-performance exploration on large graphs for information retrieva. CIKM. ACM, pp 573–582 Martínez-Bazan N, Muntés-Mulero V, Gómez-Villamor S, Nin J, Sánchez-Martínez M, Larriba-Pey J (2007) DEX: high-performance exploration on large graphs for information retrieva. CIKM. ACM, pp 573–582
69.
go back to reference Martínez-Bazan N, Gómez-Villamor S, Escale-Claveras F (2011) DEX: a high-performance graph database management system. GDM. IEEE, pp 124–127 Martínez-Bazan N, Gómez-Villamor S, Escale-Claveras F (2011) DEX: a high-performance graph database management system. GDM. IEEE, pp 124–127
70.
go back to reference McCune RR, Weninger T, Madey G (2015) Thinking like a vertex: a survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Comput Surv 48(2):25:1–25:39CrossRef McCune RR, Weninger T, Madey G (2015) Thinking like a vertex: a survey of vertex-centric frameworks for large-scale distributed graph processing. ACM Comput Surv 48(2):25:1–25:39CrossRef
71.
go back to reference Meyer U, Sanders P (2003) Delta-stepping: a parallelizable shortest path algorithm. J Algorithm 49(1):114–152CrossRefMATH Meyer U, Sanders P (2003) Delta-stepping: a parallelizable shortest path algorithm. J Algorithm 49(1):114–152CrossRefMATH
73.
go back to reference Nelson J, Myers B, Hunter AH, Briggs P, Ceze L, Ebeling C, Grossman D, Kahan S, Oskin M (2011) Crunching large graphs with commodity processors. HotPar. USENIX Association, Nelson J, Myers B, Hunter AH, Briggs P, Ceze L, Ebeling C, Grossman D, Kahan S, Oskin M (2011) Crunching large graphs with commodity processors. HotPar. USENIX Association,
74.
go back to reference Nenov Y, Piro R, Motik B, Horrocks I, Wu Z, Banerjee J (2015) RDFox: A Highly-Scalable RDF Store. ISWC. vol. 9367. Springer, Berlin Heidelberg, pp 3–20 Nenov Y, Piro R, Motik B, Horrocks I, Wu Z, Banerjee J (2015) RDFox: A Highly-Scalable RDF Store. ISWC. vol. 9367. Springer, Berlin Heidelberg, pp 3–20
75.
go back to reference Neumann T, Weikum G (2008) RDF-3X: a RISC-style Engine for RDF. Proc VLDB Endow 1(1):647–659CrossRef Neumann T, Weikum G (2008) RDF-3X: a RISC-style Engine for RDF. Proc VLDB Endow 1(1):647–659CrossRef
76.
go back to reference Nguyen D, Lenharth A, Pingali K (2013) A lightweight infrastructure for graph analytics. SOSP, pp 456–471 Nguyen D, Lenharth A, Pingali K (2013) A lightweight infrastructure for graph analytics. SOSP, pp 456–471
77.
go back to reference Nurvitadhi E, Weisz G, Wang Y, Hurkat S, Nguyen M, Hoe JC, Martínez JF, Guestrin C (2014) Graphgen: An FPGA framework for vertex-centric graph computation. FCCM. IEEE Computer Society, pp 25–28 Nurvitadhi E, Weisz G, Wang Y, Hurkat S, Nguyen M, Hoe JC, Martínez JF, Guestrin C (2014) Graphgen: An FPGA framework for vertex-centric graph computation. FCCM. IEEE Computer Society, pp 25–28
78.
go back to reference Ogata H, Fujibuchi W, Goto S, Kanehisa M (2000) A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters. Nucleic Acids Res 28(20):4021–4028CrossRef Ogata H, Fujibuchi W, Goto S, Kanehisa M (2000) A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters. Nucleic Acids Res 28(20):4021–4028CrossRef
79.
go back to reference Pandis I, Johnson R, Hardavellas N, Ailamaki A (2010) Data-oriented transaction execution. Proc VLDB Endow 3(1):928–939CrossRef Pandis I, Johnson R, Hardavellas N, Ailamaki A (2010) Data-oriented transaction execution. Proc VLDB Endow 3(1):928–939CrossRef
80.
go back to reference Pandit S, Chau DH, Wang S, Faloutsos C (2007) Netprobe: a fast and scalable system for fraud detection in Online auction networks. WWW. ACM, pp 201–210 Pandit S, Chau DH, Wang S, Faloutsos C (2007) Netprobe: a fast and scalable system for fraud detection in Online auction networks. WWW. ACM, pp 201–210
81.
go back to reference Paradies M, Lehner W, Bornhövd C (2015) GRAPHITE: An extensible graph traversal framework for relational database management systems. SSDBM. ACM, pp 29:1–29:12 Paradies M, Lehner W, Bornhövd C (2015) GRAPHITE: An extensible graph traversal framework for relational database management systems. SSDBM. ACM, pp 29:1–29:12
82.
go back to reference Pham M, Passing L, Erling O, Boncz PA (2015) Deriving an emergent relational schema from RDF data. WWW. ACM, pp 864–874 Pham M, Passing L, Erling O, Boncz PA (2015) Deriving an emergent relational schema from RDF data. WWW. ACM, pp 864–874
83.
go back to reference Picalausa F, Luo Y, Fletcher GHL, Hidders J, Vansummeren S (2012) A structural approach to indexing triples. ESWC. Springer, Berlin Heidelberg, pp 406–421 Picalausa F, Luo Y, Fletcher GHL, Hidders J, Vansummeren S (2012) A structural approach to indexing triples. ESWC. Springer, Berlin Heidelberg, pp 406–421
84.
go back to reference Prabhakaran V, Wu M, Weng X, McSherry F, Zhou L, Haradasan M (2012) Managing large graphs on multi-cores with graph awareness. ATC. USENIX Association, pp 41–52 Prabhakaran V, Wu M, Weng X, McSherry F, Zhou L, Haradasan M (2012) Managing large graphs on multi-cores with graph awareness. ATC. USENIX Association, pp 41–52
85.
go back to reference Raman R, van Rest O, Hong S, Wu Z, Chafi H, Banerjee J (2014) PGX.ISO: parallel and efficient in-memory engine for subgraph isomorphism. GRADES. ACM, pp 1–6 Raman R, van Rest O, Hong S, Wu Z, Chafi H, Banerjee J (2014) PGX.ISO: parallel and efficient in-memory engine for subgraph isomorphism. GRADES. ACM, pp 1–6
86.
go back to reference van Rest O, Hong S, Kim J, Meng X, Chafi H (2016) PGQL: a property graph query language. GRADES. ACM, van Rest O, Hong S, Kim J, Meng X, Chafi H (2016) PGQL: a property graph query language. GRADES. ACM,
87.
go back to reference Robinson I, Webber J, Eifrem E (2015) Graph databases, 2nd edn. O’Reilly, Sebastopol, CA, USA Robinson I, Webber J, Eifrem E (2015) Graph databases, 2nd edn. O’Reilly, Sebastopol, CA, USA
88.
go back to reference Rodriguez MA (2015) The gremlin graph traversal machine and language. DBPL. ACM Rodriguez MA (2015) The gremlin graph traversal machine and language. DBPL. ACM
89.
go back to reference Rodriguez MA, Neubauer P (2010) Constructions from dots and lines. Bull Am Soc Inf Sci Technol 36(6):35–41CrossRef Rodriguez MA, Neubauer P (2010) Constructions from dots and lines. Bull Am Soc Inf Sci Technol 36(6):35–41CrossRef
90.
go back to reference Roy A, Mihailovic I, Zwaenepoel W (2013) X‑stream: edge-centric graph processing using streaming partitions. SIGOPS. ACM, pp 472–488 Roy A, Mihailovic I, Zwaenepoel W (2013) X‑stream: edge-centric graph processing using streaming partitions. SIGOPS. ACM, pp 472–488
91.
go back to reference Rudolf M, Paradies M, Bornhövd C, Lehner W (2013) The graph story of the SAP HANA database. BTW 214:403–420 Rudolf M, Paradies M, Bornhövd C, Lehner W (2013) The graph story of the SAP HANA database. BTW 214:403–420
92.
go back to reference Seo J, Park J, Shin J, Lam MS (2013) Distributed Socialite: a datalog-based language for large-scale graph analysis. Proc VLDB Endow 6(14):1906–1917CrossRef Seo J, Park J, Shin J, Lam MS (2013) Distributed Socialite: a datalog-based language for large-scale graph analysis. Proc VLDB Endow 6(14):1906–1917CrossRef
93.
go back to reference Seo J, Guo S, Lam MS (2015) Socialite: An efficient graph query language based on Datalog. IEEE Trans Knowl Data Eng 27(7):1824–1837CrossRef Seo J, Guo S, Lam MS (2015) Socialite: An efficient graph query language based on Datalog. IEEE Trans Knowl Data Eng 27(7):1824–1837CrossRef
94.
go back to reference Sevenich M, Hong S, Welc A, Chafi H (2014) Fast in-memory triangle listing for large real-world graphs. SNA. ACM, pp 2:1–2:9 Sevenich M, Hong S, Welc A, Chafi H (2014) Fast in-memory triangle listing for large real-world graphs. SNA. ACM, pp 2:1–2:9
95.
go back to reference Shao B, Wang H, Li Y (2013) Trinity: a distributed graph engine on a memory cloud. SIGMOD. ACM, pp 505–516 Shao B, Wang H, Li Y (2013) Trinity: a distributed graph engine on a memory cloud. SIGMOD. ACM, pp 505–516
96.
go back to reference Shun J, Blelloch GE (2013) Ligra: a lightweight graph processing framework for shared memory. PPoPP, pp 135–146 Shun J, Blelloch GE (2013) Ligra: a lightweight graph processing framework for shared memory. PPoPP, pp 135–146
97.
go back to reference Slota GM, Rajamanickam S, Madduri K (2014) BFS and coloring-based parallel algorithms for strongly connected components and related problems. IPDPS. IEEE Computer Society, pp 550–559 Slota GM, Rajamanickam S, Madduri K (2014) BFS and coloring-based parallel algorithms for strongly connected components and related problems. IPDPS. IEEE Computer Society, pp 550–559
98.
go back to reference Sun W, Fokoue A, Srinivas K, Kementsietsidis A, Hu G, Xie GT (2015) SQLgraph: an efficient relational-based property graph store. SIGMOD. ACM, pp 1887–1901 Sun W, Fokoue A, Srinivas K, Kementsietsidis A, Hu G, Xie GT (2015) SQLgraph: an efficient relational-based property graph store. SIGMOD. ACM, pp 1887–1901
99.
go back to reference Sundaram N, Satish N, Patwary MMA, Dulloor S, Anderson MJ, Vadlamudi SG, Das D, Dubey P (2015) Graphmat: high performance graph analytics made productive. Proc VLDB Endow 8(11):1214–1225CrossRef Sundaram N, Satish N, Patwary MMA, Dulloor S, Anderson MJ, Vadlamudi SG, Das D, Dubey P (2015) Graphmat: high performance graph analytics made productive. Proc VLDB Endow 8(11):1214–1225CrossRef
100.
go back to reference Tanase IG, Xia Y, Nai L, Liu Y, Tan W, Crawford J, Lin C (2014) A highly efficient runtime and graph library for large-scale graph analytics. GRADES. ACM, pp 10:1–10:6 Tanase IG, Xia Y, Nai L, Liu Y, Tan W, Crawford J, Lin C (2014) A highly efficient runtime and graph library for large-scale graph analytics. GRADES. ACM, pp 10:1–10:6
101.
go back to reference Tas MK, Kaya K, Saule E (2017) Greed is good: optimistic algorithms for bipartite-graph partial coloring on Multicore architectures. CoRR abs/1701.02628. Tas MK, Kaya K, Saule E (2017) Greed is good: optimistic algorithms for bipartite-graph partial coloring on Multicore architectures. CoRR abs/1701.02628.
102.
go back to reference Tian Y, Balmin A, Corsten SA, Tatikonda S, McPherson J (2013) From ‘think like a vertex’ to ‘think like a graph’. Proc VLDB Endow 7(3):193–204CrossRef Tian Y, Balmin A, Corsten SA, Tatikonda S, McPherson J (2013) From ‘think like a vertex’ to ‘think like a graph’. Proc VLDB Endow 7(3):193–204CrossRef
104.
go back to reference Valiant LG (1990) A bridging model for parallel computation. Commun ACM 33(8):103–111CrossRef Valiant LG (1990) A bridging model for parallel computation. Commun ACM 33(8):103–111CrossRef
105.
go back to reference Voigt H (2016) Declarative multidimensional graph queries. Business Intelligence – 6th European Summer School, eBISS, Tours, France, July 3‑8, 2016. Tutorial Lectures (2017). Voigt H (2016) Declarative multidimensional graph queries. Business Intelligence – 6th European Summer School, eBISS, Tours, France, July 3‑8, 2016. Tutorial Lectures (2017).
108.
go back to reference Wang G, Xie W, Demers AJ, Gehrke J (2013) Asynchronous large-scale graph processing made easy. CIDR. Wang G, Xie W, Demers AJ, Gehrke J (2013) Asynchronous large-scale graph processing made easy. CIDR.
109.
go back to reference Weiss C, Karras P, Bernstein A (2008) Hexastore: sextuple indexing for semantic web data management. Proc VLDB Endow 1(1):1008–1019CrossRef Weiss C, Karras P, Bernstein A (2008) Hexastore: sextuple indexing for semantic web data management. Proc VLDB Endow 1(1):1008–1019CrossRef
110.
go back to reference Wood PT (2012) Query languages for graph databases. SIGMOD Rec 41(1):50–60CrossRef Wood PT (2012) Query languages for graph databases. SIGMOD Rec 41(1):50–60CrossRef
111.
go back to reference Xia Y, Tanase IG, Nai L, Tan W, Liu Y, Crawford J, Lin C (2014) Graph analytics and storage. Big Data. IEEE, pp 942–951 Xia Y, Tanase IG, Nai L, Tan W, Liu Y, Crawford J, Lin C (2014) Graph analytics and storage. Big Data. IEEE, pp 942–951
112.
go back to reference Xie C, Chen R, Guan H, Zang B, Chen H (2015) SYNC or ASYNC: time to fuse for distributed graph-parallel computation. PPoPP. ACM, pp 194–204 Xie C, Chen R, Guan H, Zang B, Chen H (2015) SYNC or ASYNC: time to fuse for distributed graph-parallel computation. PPoPP. ACM, pp 194–204
113.
go back to reference Yan D, Bu Y, Tian Y, Deshpande A, Cheng J (2016) Big graph analytics systems. SIGMOD. ACM, pp 2241–2243 Yan D, Bu Y, Tian Y, Deshpande A, Cheng J (2016) Big graph analytics systems. SIGMOD. ACM, pp 2241–2243
114.
go back to reference Yuan P, Zhang W, Xie C, Jin H, Liu L, Lee K (2014) Fast iterative graph computation: a path centric approach. SC. IEEE Computer Society, pp 401–412 Yuan P, Zhang W, Xie C, Jin H, Liu L, Lee K (2014) Fast iterative graph computation: a path centric approach. SC. IEEE Computer Society, pp 401–412
115.
go back to reference Zhang K, Chen R, Chen H (2015) NUMA-aware graph-structured analytics. PPoPP, pp 183–193 Zhang K, Chen R, Chen H (2015) NUMA-aware graph-structured analytics. PPoPP, pp 183–193
116.
go back to reference Zheng D, Mhembere D, Burns RC, Vogelstein JT, Priebe CE, Szalay AS (2015) Flashgraph: processing billion-node graphs on an array of commodity SSDs. FAST. USENIX Association, pp 45–58 Zheng D, Mhembere D, Burns RC, Vogelstein JT, Priebe CE, Szalay AS (2015) Flashgraph: processing billion-node graphs on an array of commodity SSDs. FAST. USENIX Association, pp 45–58
117.
go back to reference Zhu X, Han W, Chen W (2015) Gridgraph: large-scale graph processing on a single machine using 2‑level hierarchical partitioning. ATC. USENIX Association, pp 375–386 Zhu X, Han W, Chen W (2015) Gridgraph: large-scale graph processing on a single machine using 2‑level hierarchical partitioning. ATC. USENIX Association, pp 375–386
118.
go back to reference Zou L, Özsu MT, Chen L, Shen X, Huang R, Zhao D (2014) gStore: a graph-based SPARQL query engine. VLDB J 23(4):565–590CrossRef Zou L, Özsu MT, Chen L, Shen X, Huang R, Zhao D (2014) gStore: a graph-based SPARQL query engine. VLDB J 23(4):565–590CrossRef
Metadata
Title
Big Graph Data Analytics on Single Machines – An Overview
Authors
Marcus Paradies
Hannes Voigt
Publication date
19-06-2017
Publisher
Springer Berlin Heidelberg
Published in
Datenbank-Spektrum / Issue 2/2017
Print ISSN: 1618-2162
Electronic ISSN: 1610-1995
DOI
https://doi.org/10.1007/s13222-017-0255-8

Other articles of this Issue 2/2017

Datenbank-Spektrum 2/2017 Go to the issue

Editorial

Editorial

Premium Partner