{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:16:43Z","timestamp":1758709003397,"version":"3.37.3"},"reference-count":60,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T00:00:00Z","timestamp":1605484800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T00:00:00Z","timestamp":1605484800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Big Data"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Sorting algorithms are among the most commonly used algorithms in computer science and modern software. Having efficient implementation of sorting is necessary for a wide spectrum of scientific applications. This paper describes the sorting algorithm written using the partitioned global address space (PGAS) model, implemented using the Parallel Computing in Java (PCJ) library. The iterative implementation description is used to outline the possible performance issues and provide means to resolve them. The key idea of the implementation is to have an efficient building block that can be easily integrated into many application codes. This paper also presents the performance comparison of the PCJ implementation with the MapReduce approach, using Apache Hadoop<jats:italic>TeraSort<\/jats:italic>implementation. The comparison serves to show that the performance of the implementation is good enough, as the PCJ implementation shows similar efficiency to the Hadoop implementation.<\/jats:p>","DOI":"10.1186\/s40537-020-00376-9","type":"journal-article","created":{"date-parts":[[2020,11,16]],"date-time":"2020-11-16T13:17:48Z","timestamp":1605532668000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Comparison of sort algorithms in Hadoop and PCJ"],"prefix":"10.1186","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5665-9670","authenticated-orcid":false,"given":"Marek","family":"Nowicki","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,16]]},"reference":[{"issue":"7","key":"376_CR1","first-page":"321","volume":"4","author":"CA Hoare","year":"1961","unstructured":"Hoare CA. Algorithm 65: find. Commun ACM. 1961;4(7):321\u20132.","journal-title":"Commun ACM"},{"key":"376_CR2","doi-asserted-by":"crossref","unstructured":"Sun W, Ma Z. Count sort for GPU computing. In: 2009 15th international conference on parallel and distributed systems. IEEE; 2009. p. 919\u2013924.","DOI":"10.1109\/ICPADS.2009.30"},{"issue":"18","key":"376_CR3","doi-asserted-by":"publisher","first-page":"2365","DOI":"10.1002\/cpe.1776","volume":"23","author":"V Kolonias","year":"2011","unstructured":"Kolonias V, Voyiatzis AG, Goulas G, Housos E. Design and implementation of an efficient integer count sort in CUDA GPUs. Concurr Comput. 2011;23(18):2365\u201381.","journal-title":"Concurr Comput"},{"issue":"02","key":"376_CR4","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1142\/S0129626411000187","volume":"21","author":"D Merrill","year":"2011","unstructured":"Merrill D, Grimshaw A. High Performance and Scalable Radix Sorting: a Case Study of Implementing Dynamic Parallelism for GPU Computing. Parallel Processing Letters. 2011;21(02):245\u201372.","journal-title":"Parallel Processing Letters."},{"key":"376_CR5","doi-asserted-by":"crossref","unstructured":"Gogoli\u0144ska A, Mikulski \u0141, Pi\u0105tkowski M. GPU Computations and Memory Access Model Based on Petri Nets. In: Transactions on Petri Nets and Other Models of Concurrency XIII. Springer; 2018: 136\u2013157.","DOI":"10.1007\/978-3-662-58381-4_7"},{"issue":"1","key":"376_CR6","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean J, Ghemawat S. MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM. 2008;51(1):107\u201313.","journal-title":"Communications of the ACM."},{"key":"376_CR7","unstructured":"Zaharia M, Chowdhury M, Das T, Dave A, Ma J, McCauley M, et\u00a0al. 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. USENIX Association; 2012:2."},{"key":"376_CR8","first-page":"4","volume":"36","author":"P Carbone","year":"2015","unstructured":"Carbone P, Katsifodimos A, Ewen S, Markl V, Haridi S, Tzoumas K. Apache Flink: stream and batch processing in a single engine. Bull IEEE Comput Soc Tech Committ Data Eng. 2015;36:4.","journal-title":"Bull IEEE Comput Soc Tech Committ Data Eng."},{"key":"376_CR9","first-page":"173","volume-title":"Applications of Hadoop Ecosystems Tools NoSQL","author":"P Mishra","year":"2017","unstructured":"Mishra P, Mishra M, Somani AK. Applications of Hadoop Ecosystems Tools NoSQL. New York: Chapman and Hall; 2017. p. 173\u201390."},{"key":"376_CR10","unstructured":"PCJ homepage. https:\/\/pcj.icm.edu.pl. Accessed 26 Nov 2019."},{"key":"376_CR11","doi-asserted-by":"crossref","unstructured":"Nowicki M, G\u00f3rski \u0141, Ba\u0142a P. Evaluation of the parallel performance of the Java and PCJ on the Intel KNL based systems. In: International conference on parallel processing and applied mathematics. 2017; p. 288\u201397.","DOI":"10.1007\/978-3-319-78054-2_27"},{"key":"376_CR12","unstructured":"Nowicki M, G\u00f3rski \u0141, Ba\u0142a P. Performance evaluation of parallel computing and Big Data processing with Java and PCJ library. Cray User Group. 2018;."},{"issue":"11","key":"376_CR13","doi-asserted-by":"publisher","first-page":"e1005834","DOI":"10.1371\/journal.pcbi.1005834","volume":"13","author":"F Rakowski","year":"2017","unstructured":"Rakowski F, Karbowski J. Optimal synaptic signaling connectome for locomotory behavior in Caenorhabditis elegans: design minimizing energy cost. PLoS Comput Biol. 2017;13(11):e1005834.","journal-title":"PLoS Comput Biol."},{"key":"376_CR14","doi-asserted-by":"crossref","unstructured":"G\u00f3rski \u0141, Rakowski F, Ba\u0142a P. Parallel differential evolution in the PGAS programming model implemented with PCJ Java library. In: International conference on parallel processing and applied mathematics. Springer; 2015. p. 448\u201358.","DOI":"10.1007\/978-3-319-32149-3_42"},{"key":"376_CR15","doi-asserted-by":"crossref","unstructured":"G\u00f3rski \u0141, Ba\u0142a P, Rakowski F. A case study of software load balancing policies implemented with the PGAS programming model. In: 2016 International conference on high performance computing simulation (HPCS); 2016. p. 443\u20138.","DOI":"10.1109\/HPCSim.2016.7568368"},{"key":"376_CR16","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1007\/978-3-319-65482-9_36","volume-title":"International conference on algorithms and architectures for parallel processing","author":"M Nowicki","year":"2017","unstructured":"Nowicki M, Bzhalava D, Ba\u0142a P. Massively parallel sequence alignment with BLAST through work distribution implemented using PCJ library. In: Ibrahim S, Choo KK, Yan Z, Pedrycz W, editors. International conference on algorithms and architectures for parallel processing. Cham: Springer; 2017. p. 503\u201312."},{"issue":"8","key":"376_CR17","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1089\/cmb.2018.0079","volume":"25","author":"M Nowicki","year":"2018","unstructured":"Nowicki M, Bzhalava D, Ba\u0142a P. Massively Parallel Implementation of Sequence Alignment with Basic Local Alignment Search Tool using Parallel Computing in Java library. J Comput Biol. 2018;25(8):871\u201381.","journal-title":"J Comput Biol"},{"key":"376_CR18","doi-asserted-by":"crossref","unstructured":"Tampuu A, Bzhalava Z, Dillner J, Vicente R. ViraMiner: deep learning on raw DNA sequences for identifying viral genomes in human samples. BioRxiv. 2019:602656.","DOI":"10.1101\/602656"},{"key":"376_CR19","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-319-32152-3_21","volume-title":"Parallel processing and applied mathematics","author":"M Ryczkowska","year":"2016","unstructured":"Ryczkowska M, Nowicki M, Ba\u0142a P. The performance evaluation of the Java implementation of Graph500. In: Wyrzykowski R, Deelman E, Dongarra J, Karczewski K, Kitowski J, Wiatr K, editors. Parallel processing and applied mathematics. Cham: Springer; 2016. p. 221\u201330."},{"key":"376_CR20","doi-asserted-by":"crossref","unstructured":"Ryczkowska M, Nowicki M, Ba\u0142a P. Level-synchronous BFS algorithm implemented in Java using PCJ library. In: 2016 International conference on computational science and computational intelligence (CSCI). IEEE; 2016. p. 596\u2013601.","DOI":"10.1109\/CSCI.2016.0118"},{"key":"376_CR21","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/978-3-319-78054-2_29","volume-title":"Parallel processing and applied mathematics","author":"R Istrate","year":"2018","unstructured":"Istrate R, Barkoutsos PK, Dolfi M, Staar PWJ, Bekas C. Exploring graph analytics with the PCJ toolbox. In: Wyrzykowski R, Dongarra J, Deelman E, Karczewski K, editors. Parallel processing and applied mathematics. Cham: Springer International Publishing; 2018. p. 308\u2013317."},{"key":"376_CR22","doi-asserted-by":"crossref","unstructured":"Dong H, Zhou S, Grove D. X10-enabled MapReduce. In: Proceedings of the fourth conference on partitioned global address space programming model; 2010. p. 1\u20136.","DOI":"10.1145\/2020373.2020382"},{"key":"376_CR23","doi-asserted-by":"crossref","unstructured":"Teijeiro C, Taboada GL, Tourino J, Doallo R. Design and implementation of MapReduce using the PGAS programming model with UPC. In: 2011 IEEE 17th international conference on parallel and distributed systems. IEEE; 2011. p. 196\u2013203.","DOI":"10.1109\/ICPADS.2011.162"},{"key":"376_CR24","doi-asserted-by":"crossref","unstructured":"Aday S, Darkhan AZ, Madina M. PGAS approach to implement mapreduce framework based on UPC language. In: International conference on parallel computing technologies. Springer; 2017. p. 342\u201350.","DOI":"10.1007\/978-3-319-62932-2_33"},{"key":"376_CR25","unstructured":"O\u2019Malley O. TeraByte Sort on Apache Hadoop. Yahoo. http:\/\/sortbenchmark.org\/YahooHadoop.pdf. 2008. p. 1\u20133."},{"issue":"3","key":"376_CR26","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1145\/321592.321600","volume":"17","author":"WD Frazer","year":"1970","unstructured":"Frazer WD, McKellar AC. Samplesort: a sampling approach to minimal storage tree sorting. JACM. 1970;17(3):496\u2013507.","journal-title":"JACM"},{"key":"376_CR27","first-page":"1539","volume-title":"Encyclopedia of parallel computing","author":"G Almasi","year":"2011","unstructured":"Almasi G. PGAS (Partitioned Global Address Space) Languages. In: Padua D, editor. Encyclopedia of parallel computing. Boston: Springer; 2011. p. 1539\u20131545."},{"issue":"4","key":"376_CR28","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1145\/2716320","volume":"47","author":"M De Wael","year":"2015","unstructured":"De Wael M, Marr S, De Fraine B, Van Cutsem T, De Meuter W. Partitioned Global Address Space languages. ACM Comput Surv. 2015;47(4):62.","journal-title":"ACM Comput Surv"},{"key":"376_CR29","doi-asserted-by":"crossref","unstructured":"Culler DE, Dusseau A, Goldstein SC, Krishnamurthy A, Lumetta S, Von\u00a0Eicken T, et\u00a0al. Parallel programming in Split-C. In: Supercomputing\u201993. Proceedings of the 1993 ACM\/IEEE conference on supercomputing. IEEE; 1993. p. 262\u201373.","DOI":"10.1145\/169627.169724"},{"key":"376_CR30","unstructured":"Deitz SJ, Chamberlain BL, Hribar MB. Chapel: Cascade High-Productivity Language. An overview of the chapel parallel programming model. Cray User Group. 2006."},{"key":"376_CR31","doi-asserted-by":"crossref","unstructured":"Numrich RW, Reid J. Co-array Fortran for parallel programming. In: ACM SIGPLAN Fortran Forum, vol.\u00a017. ACM; 1998:1\u201331.","DOI":"10.1145\/289918.289920"},{"issue":"11\u201313","key":"376_CR32","first-page":"825","volume":"10","author":"K Yelick","year":"1998","unstructured":"Yelick K, Semenzato L, Pike G, Miyamoto C, Liblit B, Krishnamurthy A, et al. Titanium: a high-performance Java dialect. Concurr Comput. 1998;10(11\u201313):825\u201336.","journal-title":"Concurr Comput"},{"key":"376_CR33","unstructured":"Consortium U, et\u00a0al. UPC Language Specifications v1.2. Ernest Orlando Lawrence Berkeley NationalLaboratory, Berkeley, CA (US); 2005."},{"key":"376_CR34","doi-asserted-by":"crossref","unstructured":"Charles P, Grothoff C, Saraswat V, Donawa C, Kielstra A, Ebcioglu K, et\u00a0al. X10: an Object-oriented approach to non-uniform cluster computing. In: ACM SIGPLAN Notices, vol.\u00a040. ACM; 2005. p. 519\u201338.","DOI":"10.1145\/1103845.1094852"},{"key":"376_CR35","doi-asserted-by":"crossref","unstructured":"Tardieu O. The APGAS library: resilient parallel and distributed programming in Java 8. In: Proceedings of the ACM SIGPLAN workshop on X10; 2015. p. 25\u20136.","DOI":"10.1145\/2771774.2771780"},{"key":"376_CR36","first-page":"46","volume":"1","author":"L Dagum","year":"1998","unstructured":"Dagum L, Menon R. OpenMP: an industry-standard API for shared-memory programming. Comput Sci Eng. 1998;1:46\u201355.","journal-title":"Comput Sci Eng"},{"key":"376_CR37","doi-asserted-by":"crossref","unstructured":"Clarke L, Glendinning I, Hempel R. The MPI message passing interface standard. In: Programming environments for massively parallel distributed systems. Springer; 1994. p. 213\u201318.","DOI":"10.1007\/978-3-0348-8534-8_21"},{"key":"376_CR38","first-page":"66","volume":"36","author":"M Nowicki","year":"2016","unstructured":"Nowicki M, Ryczkowska M, G\u00f3rski \u0141, Szynkiewicz M, Ba\u0142a P. PCJ-a Java library for heterogenous parallel computing. Recent Adv Inf Sci. 2016;36:66\u201372.","journal-title":"Recent Adv Inf Sci"},{"key":"376_CR39","doi-asserted-by":"crossref","unstructured":"Nowicki M, G\u00f3rski \u0141, Ba\u0142a P. PCJ\u2013Java Library for Highly Scalable HPC and Big Data Processing. In: 2018 international conference on high performance computing and simulation (HPCS). IEEE; 2018. p. 12\u201320.","DOI":"10.1109\/HPCS.2018.00017"},{"key":"376_CR40","doi-asserted-by":"crossref","unstructured":"Ryczkowska M, Nowicki M. Performance comparison of graph BFS implemented in MapReduce and PGAS programming models. In: International conference on parallel processing and applied mathematics. Springer; 2017. p. 328\u201337.","DOI":"10.1007\/978-3-319-78054-2_31"},{"key":"376_CR41","first-page":"318","volume-title":"International conference on parallel processing and applied mathematics","author":"M Nowicki","year":"2017","unstructured":"Nowicki M, Ryczkowska M, G\u00f3rski \u0141, Ba\u0142a P. Big Data analytics in Java with PCJ library: performance comparison with Hadoop. In: Wyrzykowski R, Dongarra J, Deelman E, Karczewski K, editors. International conference on parallel processing and applied mathematics. Cham: Springer; 2017. p. 318\u201327."},{"key":"376_CR42","unstructured":"Apache Hadoop TeraSort package. https:\/\/hadoop.apache.org\/docs\/r3.2.1\/api\/org\/apache\/hadoop\/examples\/terasort\/package-summary.html. Accessed 26 Nov 2019."},{"key":"376_CR43","volume-title":"Handbook of data structures and applications","author":"S Sahni","year":"2004","unstructured":"Sahni S. Tries. In: Mehta DP, Sahni S, editors. Handbook of data structures and applications. New York: CRC; 2004."},{"key":"376_CR44","unstructured":"Hadoop implementation of the TeraSort benchmark. https:\/\/github.com\/apache\/hadoop\/tree\/780d4f416e3cac3b9e8188c658c6c8438c6a865b\/hadoop-mapreduce-project\/hadoop-mapreduce-examples\/src\/main\/java\/org\/apache\/hadoop\/examples\/terasort. Accessed 10 Jan 2020."},{"key":"376_CR45","unstructured":"AlDanial\/cloc: cloc counts blank lines, comment lines, and physical lines of source code in many programming languages. https:\/\/github.com\/AlDanial\/cloc. Accessed 28 Jan 2020."},{"key":"376_CR46","unstructured":"Artur Bosch \/ lloc - Logical Lines of Code. https:\/\/gitlab.com\/arturbosch\/lloc\/tree\/7f5efaf797d33a5eebb338c21637807571022fab. Accessed 28 Jan 2020."},{"key":"376_CR47","unstructured":"Nowicki M. Benchmarking the Sort Algorithm on Ethernet Cluster. Technical Report. In:\u00a0HPI Future SOC Lab: Proceedings 2019 (in press)."},{"key":"376_CR48","doi-asserted-by":"crossref","unstructured":"Pasetto D, Akhriev A. A comparative study of parallel sort algorithms. In: Proceedings of the ACM international conference companion on Object oriented programming systems languages and applications companion. ACM; 2011:203\u2013204.","DOI":"10.1145\/2048147.2048207"},{"key":"376_CR49","unstructured":"Arrays (Java SE 13 & JDK 13). https:\/\/docs.oracle.com\/en\/java\/javase\/13\/docs\/api\/java.base\/java\/util\/Arrays.html#sort(java.lang.Object%5B%5D). Accessed 07 Jul 2020."},{"key":"376_CR50","unstructured":"Python timsort. http:\/\/svn.python.org\/projects\/python\/trunk\/Objects\/listsort.txt. Accessed 07 Jul 2020."},{"key":"376_CR51","unstructured":"McIlroy P. Optimistic sorting and information theoretic complexity. In: Proceedings of the fourth annual ACM-SIAM symposium on discrete algorithms; 1993. p. 467\u201374."},{"key":"376_CR52","unstructured":"PCJ implementations of the TeraSort benchmark. https:\/\/github.com\/hpdcj\/PCJ-TeraSort\/tree\/a1c2cb339511e9bcd3befb892f82c522c7fbd1c3\/src\/main\/java\/pl\/umk\/mat\/faramir\/terasort. Accessed 01 July 2020."},{"key":"376_CR53","unstructured":"Hortonworks Documentation: 11. Determine YARN and MapReduce memory configuration settings. https:\/\/docs.cloudera.com\/HDPDocuments\/HDP2\/HDP-2.0.6.0\/bk_installing_manually_book\/content\/rpm-chap1-11.html. Accessed 5 Nov 2020."},{"key":"376_CR54","unstructured":"IBM Knowledge Center: Memory calculator worksheet. https:\/\/www.ibm.com\/support\/knowledgecenter\/en\/SSPT3X_4.0.0\/com.ibm.swg.im.infosphere.biginsights.dev.doc\/doc\/biga_caching_worksheet.html.\u00a0\u00a0Accessed 5 Nov 2020."},{"key":"376_CR55","unstructured":"GraySort Benchmark. Sort Benchmark Home Page. http:\/\/sortbenchmark.org. Accessed 6 Oct 2020."},{"key":"376_CR56","doi-asserted-by":"crossref","unstructured":"Posner J, Reitz L, Fohry C. Comparison of the HPC and big data Java libraries spark, PCJ and APGAS. In: 2018 IEEE\/ACM parallel applications workshop, alternatives To MPI (PAW-ATM). IEEE; 2018. p. 11\u201322.","DOI":"10.1109\/PAW-ATM.2018.00007"},{"key":"376_CR57","doi-asserted-by":"crossref","unstructured":"Menon RK, Bhat GP, Schatz MC. Rapid Parallel Genome Indexing with MapReduce. In: Proceedings of the second international workshop on MapReduce and its applications; 2011. p. 51\u20138.","DOI":"10.1145\/1996092.1996104"},{"key":"376_CR58","first-page":"21","volume":"1","author":"O Wodo","year":"2015","unstructured":"Wodo O, Zola J, Pokuri BSS, Du P, Ganapathysubramanian B. Automated, high throughput exploration of process-structure-property relationships using the MapReduce paradigm. Mater Disc. 2015;1:21\u20138.","journal-title":"Mater Disc"},{"key":"376_CR59","unstructured":"Nowicki M. Benchmarking Java on Ethernet Cluster. Technical Report.\u00a0In:\u00a0HPI Future SOC Lab: Proceedings 2019 (in press)."},{"key":"376_CR60","unstructured":"Nowicki M. Benchmarking the TeraSort algorithm on Ethernet Cluster. Technical Report. In:\u00a0HPI Future SOC Lab: Proceedings 2020 (in press)."}],"container-title":["Journal of Big Data"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-020-00376-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s40537-020-00376-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-020-00376-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,17]],"date-time":"2024-08-17T13:19:57Z","timestamp":1723900797000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofbigdata.springeropen.com\/articles\/10.1186\/s40537-020-00376-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,16]]},"references-count":60,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["376"],"URL":"https:\/\/doi.org\/10.1186\/s40537-020-00376-9","relation":{},"ISSN":["2196-1115"],"issn-type":[{"type":"electronic","value":"2196-1115"}],"subject":[],"published":{"date-parts":[[2020,11,16]]},"assertion":[{"value":"30 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 November 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The author declares that he has no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"101"}}