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
Published in:
Integrating Map-Reduce and Stream-Processing for Efficiency (MRSP) Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Sorting Data on Ultra-Large Scale with RADULS

New Incarnation of Radix Sort

Authors : Marek Kokot, Sebastian Deorowicz, Agnieszka Debudaj-Grabysz

Published in: Beyond Databases, Architectures and Structures. Towards Efficient Solutions for Data Analysis and Knowledge Representation

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

The paper introduces RADULS, a new parallel sorter based on radix sort algorithm, intended to organize ultra-large data sets efficiently. For example 4 G 16-byte records can be sorted with 16 threads in less than 15 s on Intel Xeon-based workstation. The implementation of RADULS is not only highly optimized to gain such an excellent performance, but also parallelized in a cache friendly manner to make the most of modern multicore architectures. Besides, our parallel scheduler launches a few different procedures at runtime, according to the current parameters of the execution, for proper workload management. All experiments show RADULS to be superior to competing algorithms.

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!

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"

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
previous chapter Optimization of Memory Operations in Generalized Search Trees of PostgreSQL
next chapter Serendipitous Recommendations Through Ontology-Based Contextual Pre-filtering
Literature
1.
2.
Cho, M., Brand, D., Bordawekar, R., Finkler, U., Kulandaisamy, V., Puri, R.: PARADIS: an efficient parallel algorithm for in-place radix sort. In: Proceedings of the VLDB Endowment—Proceedings of the 41st International Conference on Very, pp. 1518–1529 (2015)
3.
4.
5.
Gray, J., Sundaresan, P., Englert, S., Baclawski, K., Weinberger, P.: Quickly generating billion-record synthetic databases. In: Proceedings of the SIGMOD, pp. 243–252 (1994)
6.
7.
8.
9.
Knuth, D.: The Art of Computer Programming. Addison-Wesley, Boston (1968)MATH
10.
Musser, D.: Introspective sorting and selection algorithms. Softw.: Pract. Exp. 27(8), 983–993 (1997)
11.
Satish, N., Kim, C., Chhugani, J., Nguyen, AD., Lee, V., Kim, D., Dubey, P.: Fast sort on CPUs and GPUs: a case for bandwidth oblivious simd sort. In: Proceedings of the 2010 International Conference on Management of Data, pp. 351–362 (2010)
12.
Sedgewick, R.: Algorithms in C++, Parts 1–4: Fundamentals, Data Structure, Sorting, Searching. Addison-Wesley-Longman, Harlow (1998)MATH
13.
Shell, D.: A high-speed sorting procedure. Commun. ACM 2(7), 30–32 (1959)CrossRef
14.
Singler, J., Sanders, P., Putze, F.: MCSTL: the multi-core standard template library. In: Kermarrec, A.-M., Bougé, L., Priol, T. (eds.) Euro-Par 2007. LNCS, vol. 4641, pp. 682–694. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-74466-5_​72 CrossRef
15.
Williams, J.: Algorithm 232: Heapsort. Commun. ACM 7(6), 347–348 (1964)
Metadata
Title
Sorting Data on Ultra-Large Scale with RADULS
Authors
Marek Kokot
Sebastian Deorowicz
Agnieszka Debudaj-Grabysz
Copyright Year
2017
Book
Beyond Databases, Architectures and Structures. Towards Efficient Solutions for Data Analysis and Knowledge Representation

Print ISBN: 978-3-319-58273-3

Electronic ISBN: 978-3-319-58274-0

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-58274-0_20

Premium Partner

    Image Credits