Journal of East China Normal University(Natural Science) >

2016 , Vol. 2016 >Issue 5: 121 - 130

DOI: https://doi.org/10.3969/j.issn.1000-5641.2016.05.014

Sorting algorithm analysis of distributed data based on Map/Reduce

  • YU Sheng-jun ,
  • GONG Xue-qing ,
  • ZHU jun ,
  • QIAN Wei-ning
Expand
  • Institute for Data Science and Engineering, East China Normal University, Shanghai 200062, China

Received date: 2016-06-27

  Online published: 2016-11-29

Fold

Abstract

Distributed system has been widely applied in recent years to tackle the storage and calculation of big data. Sorting of large-scale dataset in the distributed system has become the fundamental problem to affect a varieties of application performances which is not only concerning about the selection of sorting algorithm at each node, but also about the development of distributed algorithms to coordinate at each node. This paper summarizes the common distributed sorting algorithms which are applied in the distributed system. Analysis has been conducted to the implementation process, cost model and applicable field of each algorithm. And the analysis results have been verified by experiments. This work can help developers choose and optimize the big data sorting
algorithm in distributed environments.

Key words： distributed system; sorting algorithm; cost model

Cite this article

YU Sheng-jun , GONG Xue-qing , ZHU jun , QIAN Wei-ning . Sorting algorithm analysis of distributed data based on Map/Reduce[J]. Journal of East China Normal University(Natural Science), 2016 , 2016(5) : 121 -130 . DOI: 10.3969/j.issn.1000-5641.2016.05.014

References

[ 1 ] KNUTH D E. The Art of Computer Programming: Sorting and Searching [M]. 2nd ed. Indianapolis: Addison-Wesley Professional, 1998.
[ 2 ] BORTHAKUR D. The hadoop distributed file system: Architecture and design [J]. Hadoop Project Website, 2007, 11: 1-10.
[ 3 ] DEAN J, GHEMAWAT S. MapReduce: Simplified data processing on large clusters [J]. Communications of the ACM, 2008, 51(1): 107-113.
[ 4 ] CHRIS NYBERG, MEHUL SHAH. Sort Benchmark Home Page [EB/OL]. (2015) [2016-04-20]. http://sortbenchmark.org/.
[ 5 ] BORTHAKUR D, GRAY J, SARMA J S, et al. Apache Hadoop goes realtime at Facebook [C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. ACM, 2011: 1071-1080.
[ 6 ] MANE S B, SAWANT Y, KAZI S, et al. Real time sentiment analysis of twitter data using hadoop [J]. International Journal of Computer Science and Information Technolo, 2014, 5(3): 3098-3100.
[ 7 ] O’MALLEY O, MURTHY A C. Winning a 60 second dash with a yellow elephant [J]. Proceedings of Sort Benchmark, 2009, 1810(9): 1-9.
[ 8 ] WANG J, WU Y, CAI H, et al. Fuxi Sort [EB/OL]. (2015) [2016-04-20]. http://sortbenchmark.org/Fux-iSort2015.pdf.
[ 9 ] GRIFFITHS N. Nmon performance: A free tool to analyze AIX and Linux performance [EB/OL]. (2003-11-04)[2016-04-20]. http://www.ibm.com/developerworks/aix/library/au-analyze aix/.

Options
Outlines

/

〈 〉