Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
The Journal of Supercomputing
Published in: The Journal of Supercomputing 1/2020

26-10-2019

Survey of external memory large-scale graph processing on a multi-core system

Authors: Jianqiang Huang, Wei Qin, Xiaoying Wang, Wenguang Chen

Published in: The Journal of Supercomputing | Issue 1/2020

Log in

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

search-config
loading …

Abstract

The fast development of big data computing contributes to the fact that large-scale graph processing has become a basic computing model in both academic and industrial communities, and it has been applied in many actual big data computing works, such as social network analysis, Web search, and product promotion. These computing works include large-scale graphs of billions of vertices and trillions of edges. Such scale has brought many challenges to large-scale graph processing. This paper mainly introduces the essential features and challenges of large-scale graph processing and how we can handle billions of edges on a multi-core machine, for which we represent out-of-core processing system and semi-external memory processing systems. This paper also summarizes the key technologies in graph processing systems and forecasts the future development of large-scale graph processing systems.
previous article Optimizing the parameters of the Lustre-file-system-based HPC system for reverse time migration
next article Effective data prediction method for in-memory database applications

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

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!

inform now

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!

inform 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!

inform now
Literature
1.
Knuth DE (1993) The Stanford GraphBase: a platform for combinatorial computing. ACM Press, New YorkMATH
2.
Siek JG, Lee L-Q, Lumsdaine A (2002) The boost graph library: user guide and reference manual. Addison-Wesley, Boston
3.
Gregor D (2005) Lumsdaine A The parallel BGL: a generic library for distributed graph computations. Proc Parallel Object Oriented Sci Comput 2:1–18
4.
Chan A, Dehne F, Taylor R (2005) CGMGRAPH/CGMLIB: implementing and testing CGM graph algorithms on PC clusters and shared memory machines. Int J High Perform Comput Appl 19(1):81–97CrossRef
5.
6.
7.
Shvachko K, Kuang H, Radia S et al (2010) The hadoop distributed file system. In: Proceedings of the 26th IEEE symposium on mass storage systems and technologies, pp 1–10
8.
Dean J, Ghemawat S (2008) MapReduce: simplified data processing on large clusters. Commun ACM 51(1):107–113CrossRef
9.
Zaharia M, Chowdhury M, Franklin MJ et al (2010) Spark: cluster computing with working sets. In: Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, p 10
10.
Zaharia M, Chowdhury M, Das T et al (2012) Resilient distributed datasets: a fault tolerant abstraction for in-memory cluster computing. In: Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation, p 2
11.
Malewicz G, Austern MH, Bik AJ et al (2010) Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, ACM New York, NY, USA, pp 135–146
12.
Low Y, Bickson D, Gonzalez J et al (2012) Distributed GraphLab: a framework for machine learning and data mining in the cloud. Proc VLDB Endow 5(8):716–727CrossRef
13.
Gonzalez JE, Low Y, Gu H et al (2012) PowerGraph: distributed graph parallel computation on natural graphs. In: Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, pp 17–30
14.
Kyrola A, Blelloch GE, Guestrin C (2012) GraphChi: large-scale graph computation on just a PC. In: Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, pp 31–46
15.
Roy A, Mihailovic I, Zwaenepoel W (2013) X-stream: edge-centric graph processing using streaming partitions. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, ACM New York, NY, USA, pp 472–488
16.
Zhu X, Han W, Chen W (2015) GridGraph: largescale graph processing on a single machine using 2-level hierarchical partitioning. In: Proceedings of the 2015 USENIX Annual Technical Conference, pp 375–386
17.
Prabhakaran V, Wu M, Weng X et al (2012) Managing large graphs on multicores with graph awareness. In: Proceedings of the 2012 USENIX Annual Technical Conference, pp 41–52
18.
Han WS, Lee S, Park K et al (2013) TurboGraph: a fast parallel graph engine handling billionscale graphs in a single PC. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, pp 77–85
19.
Cheng J, Liu Q, Li Z et al (2015) VENUS: vertex-centric streamlined graph computation on a single PC. In Proceedings of the 2015 IEEE 31st International Conference on Data Engineering IEEE, pp 1131–1142
20.
Zheng D, Mhembere D, Burns R et al (2015) FlashGraph: processing billion-node graphs on an array of commodity SSDs. In Proceedings of the 13th USENIX Conference on File and Storage Technologies, pp 45–58
21.
22.
Feng Z, Heng L, Jidong Z, Jie C, Dingyi X, Jizhong L, Yunpeng C, Xiaoyong D (2018) An adaptive breadth-first search algorithm on integrated architectures. J Supercomput 74(11):6135–6155CrossRef
23.
Zhang M, Wu Y, Zhuo Y, Qian X, Huan C, Chen K (2018) Wonderland: a novel abstraction-based out-of-core graph processing system. In: ASPLOS, pp 608–621. ACM
24.
Vora K, Xu GH, Gupta R (2016) Load the edges you need: a generic I/O optimization for disk-based graph processing. In: USENIX ATC, pp 507–522
25.
Vora K, Gupta R, Xu G (2017) KickStarter: fast and accurate computations on streaming graphs via trimmed approximations. In: ASPLOS, pp 237–251
26.
Maass S, Min C, Kashyap S, Kang W, Kumar M, Kim T (2017) Mosaic: processing a trillion-edge graph on a single machine. In: EuroSys, pp 527–543. ACM
27.
Ai Z, Zhang M, Wu Y, Qian X, Chen K, Zheng W (2017) Squeezing out all the value of loaded data: an out-of-core graph processing system with reduced disk I/O. In: USENIX ATC, pp 125–137
28.
Jun S-W, Wright A, Zhang S, Xu S (2018) Using accelerated flash storage for external graph analytics. In: ISCA. IEEE, GraFBoost
29.
Jin-zhong L, Peng-jie T, Jie-wu X et al (2015) Advances in iterative MapReduce. Comput Eng Appl 51(12):123–132
30.
Bu Y, How B, Balazinska M et al (2012) The HaLoop approach to large scale iterative data analysis. VLDB J 21(2):169–190CrossRef
31.
Bu Y, How B, Balazinska M et al (2010) HaLoop: efficient iterative data processing on large clusters. Proc VLDB Endow 3(1):285–296CrossRef
32.
Ekanayake J, Li H, Zhang B et al (2010) Twister: a runtime for iterative Mapreduce. In: Proceedings of the 19th ACM international symposium on high performance distributed computing, pp 810–818
33.
Zhang Y, Gao Q, Gao L et al (2012) iMapReduce: a distributed computing framework for iterative computation. J Grid Comput 10(1):47–68CrossRef
34.
Zhang Y, Gao Q, Gao L et al (2013) PrIter: a distributed framework for prioritizing iterative computations. IEEE Trans Parallel Distrib Syst 24(9):1884–1893CrossRef
35.
Kang U, Tsourakakis CE, Faloutsos C (2009) Pegasus: a petascale graph mining system implementation and observations. In: Proceedings of the Ninth IEEE International Conference on Data Mining, IEEE, pp 229–238
36.
Chen R, Weng X, He B et al (2010) Large graph processing in the cloud. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, ACM, pp 1123–1126
37.
Ceze L, Tuck J, Montesinos P et al (2007) BulkSC: bulk enforcement of sequential consistency. In: Proceedings of the 34th annual international symposium on computer architecture, pp 278–289
38.
Shun J, Blelloch GE (2013) Ligra: a lightweight graph processing framework for shared memory. In: Proceedings of the 18th ACM SIGPLAN symposium on principles and practice of parallel programming, ACM New York, NY, USA, pp 135–146
39.
Han TD, Abdelrahman TS (2011) hi CUDA: high-level GPGPU programming. IEEE Trans Parallel Distrib Syst 22(1):78–90CrossRef
40.
41.
Lee S, Min S, Eigenmann R (2009) Open MP to GPGPU: a compiler framework for automatic translation and optimization. In: Proceedings of the 14th ACM SIGPLAN symposium on principles and practice of parallel programming, pp 101–110
42.
Harish P, Narayanan PJ (2007) Accelerating large graph algorithms on the GPU using CUDA. In: Proceedings of the 14th International Conference on High Performance Computing, pp 197–208
43.
Luo L, Wong M, Hwu W (2010) An effective GPU implementation of breadth-first search. In: Proceedings of the 47th Design Automation Conference, pp 52–55
44.
Katz GJ, Kider Jr JT (2008) All-pairs shortest-paths for large graphs on the GPU. In: Proceedings of the 23rd ACM SIGGRAPH symposium on graphics hardware, pp 47–55
45.
Hong S, Oguntebi T, Olukotun K (2011) Efficient parallel graph exploration on multi-core CPU and GPU. In: Proceedings of the 20th International Conference on Parallel Architectures and Compilation Techniques, ACM New York, NY, USA, pp 78–88
46.
47.
Robinson I, Webber J, Eifrem E (2015) Graph databases: new opportunities for connected data. O’Reilly Media Inc., Sebastopol
48.
Zhong J, He B (2012) An overview of medusa: simplified graph processing on GPUs. In: Proceedings of the 17th ACM SIGPLAN symposium on principles and practice of parallel programming, ACM New York, NY, USA, pp 283–284
49.
Khorasani F, Vora K, Gupta R et al (2014) CuSha: vertex-centric graph processing on GPUs. In: Proceedings of the 23rd international symposium on high-performance parallel and distributed computing, ACM New York, NY, USA, pp 239–252
50.
Lingxiao M, Zhi Y, Han C, Jilong X, Yafei D (2017) Garaph: efficient GPU-accelerated graph processing on a single machine with balanced replication. In: USENIX Annual Technical Conference (ATC’), Santa Clara, CA, USA, pp 195–207
51.
Zhisong F, Michael P, Bryan T (2014) MapGraph: a high level API for fast development of high performance graph analytics on GPUs. In: Proceedings of workshop on graph data management experiences and systems (GRADES’14). ACM, New York, NY, USA, Article 2
52.
53.
Ben-Nun T, Sutton M, Pai S et al (2017) Groute: an asynchronous multi-GPU programming model for irregular computations. In: Proceedings of the 23rd ACM SIGPLAN symposium on principles and practice of parallel programming, Austin, pp 235–248
54.
Sha M, Li Y, He B et al (2017) Accelerating dynamic graph analytics on GPUs. Proc VLDB Endow 11:107–120CrossRef
55.
Zhang JL, Li J (2018) Degree-aware hybrid graph traversal on FPGA-HMC platform. In: Proceedings of the 26th ACM/SIGDA international symposium on field-programmable gate arrays, Monterey, pp 229–238
56.
Zhou SJ, Prasanna VK (2017) Accelerating graph analytics on CPU-FPGA heterogeneous platform. In: Proceedings of the 29th international symposium on computer architecture and high performance computing, Campinas, pp 137–144
57.
Zhang MX, Zhuo YW, Wang C et al (2018) GraphP: reducing communication for PIM-based graph processing with efficient data partition. In: Proceedings of the 24th IEEE international symposium on high-performance computer architecture, Vienna, pp 544–557
58.
Dai G, Huang T, Chi Y et al (2017) Fore-graph: exploring large-scale graph processing on multi-FPGA architecture. In: Proceedings of the 25th ACM/SIGDA international symposium on field-programmable gate arrays, Monterey, pp 217–226
59.
Shi XH, Liang JL, Di S et al (2015) Optimization of asynchronous graph processing on GPU with hybrid coloring model. In: Proceedings of the 20th ACM SIGPLAN symposium on principles and practice of parallel programming, San Francisco, pp 271–272
60.
61.
Kang U, Tong H, Sun J et al (2012) GBASE: an efficient analysis platform for large graphs. VLDB J 21(5):637–650CrossRef
62.
Valiant LG (1990) A bridging model for parallel computation. Commun ACM 33(8):103–111CrossRef
63.
Tasci S, Demirbas M (2013) Giraphx: parallel yet serializable largescale graph processing. In: Proceedings of European Conference on Parallel Processing. Springer, Berlin, pp 458–469
64.
Khayyat Z, Awara K, Alonazi A et al (2013) Mizan: a system for dynamic load balancing in largescale graph processing. In: Proceedings of the 8th ACM European Conference on Computer Systems. ACM, pp 169–182
65.
Yan D, Cheng J, Lu Y et al (2015) Effective techniques for message reduction and load balancing in distributed graph computation. In: Proceedings of the 24th International Conference on World Wide Web. ACM, pp 1307–1317
66.
Bao NT, Suzumura T (2013) Towards highly scalable pregel based graph processing platform with x10. In: Proceedings of the 22nd International Conference on World Wide Web Companion, International World Wide Web Conferences Steering Committee, pp 501–508
67.
Donald N, Andrew L, Keshav P (2013) A lightweight infrastructure for graph analytics. In: Proceedings of the twenty-fourth symposium on operating systems principles (SOSP’13), ACM, pp 456–471
68.
Zhang K, Chen R, Chen H (2015) NUMA-aware graph-structured analytics. In: Proceedings of the 20th ACM SIGPLAN symposium on principles and practice of parallel programming, PPoPP, pp 183–193
69.
Abdullah G, Beltrao CL, Elizeu S-N, Matei R (2012) A yoke of oxen and a thousand chickens for heavy lifting graph processing. In: Proceedings of the 21st International Conference on Parallel Architectures and Compilation Techniques (PACT’12). ACM, New York, NY, USA, pp 345–354
70.
Brandes U (2001) A faster algorithm for betweenness centrality. J Math Sociol 25(2):163–177CrossRef
71.
Broder A, Kumar R, Maghoul F, Raghavan P, Rajagopalan S, Stata R, Tomkins A, Wiener J (2000) Graph structure in the web. Comput Netw 33(1):309–320CrossRef
72.
Su BY, Keutzer K (2012) clSpMV: a cross-platform OpenCL SpMV framework on GPUs. In: Proceedings of the 26th ACM International Conference on Supercomputing, ACM, pp 353–364
73.
Backstrom L, Huttenlocher D, Kleinberg J, Lan X (2006) Group formation in large social networks: membership, growth, and evolution. In: Proceedings of KDD, pp 44–54
74.
Kwak H, Lee C, Park H, Moon S (2010) What is Twitter, a social network or a news media? In: Proceedings of WWW, pp 591–600
75.
Boldi P, Rosa M, Santini M, Vigna S (2011) Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks. In: Proceedings of WWW, pp 587–596
76.
Metadata
Title
Survey of external memory large-scale graph processing on a multi-core system
Authors
Jianqiang Huang
Wei Qin
Xiaoying Wang
Wenguang Chen
Publication date
26-10-2019
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 1/2020
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-019-03023-0

Other articles of this Issue 1/2020

The Journal of Supercomputing 1/2020 Go to the issue

OriginalPaper

An optimisation tool for robust community detection algorithms using content and topology information

OriginalPaper

Reinforcement R-learning model for time scheduling of on-demand fog placement

OriginalPaper

The curse of indecomposable aggregates for big data exploratory analysis with a case for frequent pattern cubes

OriginalPaper

Cognitive learning performance assessment and analysis with CSCL applied on the NetGuru platform and CSPL applied on the TAoD platform for the network experiment class

OriginalPaper

Interference cancellation in cognitive radio-based MC-CDMA system using pre-coding technique

OriginalPaper

Energy-efficient data dissemination algorithm based on virtual hexagonal cell-based infrastructure and multi-mobile sink for wireless sensor networks

Premium Partner

    Image Credits