Parallel String Sample Sort

We discuss how string sorting algorithms can be parallelized on modern multi-core shared memory machines. As a synthesis of the best sequential string sorting algorithms and successful parallel sorting algorithms for atomic objects, we propose string sample sort. The algorithm makes effective use of the memory hierarchy, uses additional word level parallelism, and largely avoids branch mispredictions. Additionally, we parallelize variants of multikey quicksort and radix sort that are also useful in certain situations.

• Publication year

  2013

• Venue

  Embedded Systems and Applications

• Publication date

  2013-05-06

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-642-40450-4_15arXiv 1305.1157
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Engineering a Multi-core Radix Sort

  2011cited by this paper
• Engineering burstsort: Toward fast in-place string sorting

  2010cited by this paper
• Merging String Sequences by Longest Common Prefixes

  2008cited by this paper
• Engineering Radix Sort for Strings

  2008cited by this paper
• Cache Efficient Radix Sort for String Sorting

  2007cited by this paper
• Cache-efficient string sorting using copying

  2007cited by this paper
• Cache-conscious sorting of large sets of strings with dynamic tries

  2004influential reference
• Super Scalar Sample Sort

  2004influential reference
• Engineering a Sorted List Data Structure for 32 Bit Key

  2004cited by this paper
• A simple, fast parallel implementation of Quicksort and its performance evaluation on SUN Enterprise 10000

  2003cited by this paper
• Scanning Multiple Sequences via Cache Memory

  2002cited by this paper
• The string B-tree: a new data structure for string search in external memory and its applications

  1999cited by this paper
• Fast algorithms for sorting and searching strings

  1997cited by this paper
• Optimal parallel string algorithms: sorting, merging and computing the minimum

  1994cited by this paper
• Engineering Radix Sort

  1993cited by this paper
• A comparison of sorting algorithms for the connection machine CM-2

  1991cited by this paper
• Bounded Ordered Dictionaries in O(log log N) Time and O(n) Space

  1990cited by this paper

• Comparative Analysis of Sorting Algorithms: Time Complexity and Practical Applications

  2025cites this paper
• Scalable Distributed String Sorting

  2024cites this paper
• Fast, parallel, and cache-friendly suffix array construction

  2024cites this paper
• LearnedSort as a learning-augmented SampleSort: Analysis and Parallelization

  2023cites this paper
• NASCENT2: Generic Near-Storage Sort Accelerator for Data Analytics on SmartSSD

  2022cites this paper
• Efficient String Sort with Multi-Character Encoding and Adaptive Sampling

  2021influential citation
• How Many CPU Cores is an FPGA Worth? Lessons Learned from Accelerating String Sorting on a CPU-FPGA System

  2021influential citation
• Communication-Efficient String Sorting

  2020cites this paper
• LCP-Aware Parallel String Sorting

  2020cites this paper
• FPGAs in the Datacenters: the Case of Parallel Hybrid Super Scalar String Sample Sort

  2020influential citation
• Engineering faster sorters for small sets of items

  2019cites this paper
• Scalable String and Suffix Sorting: Algorithms, Techniques, and Tools

  2018cites this paper
• Kepler GPU accelerated recursive sorting using dynamic parallelism

  2017influential citation
• In-place Parallel Super Scalar Samplesort (IPSSSSo)

  2017cites this paper
• ERA Revisited: Theoretical and Experimental Evaluation

  2016cites this paper
• Analysis of Parallel and Sequential Radix Sort for Graph Exploration using OpenMP and CUDA: A Review

  2016cites this paper
• Performance Improvement for Multi-Key Quick Sort using Kepler GPUs

  2015influential citation
• Parallel Algorithms Reconsidered

  2015cites this paper
• Crowdsourcing : From Theory to Practice and Long-Term Perspectives

  2014cites this paper
• Engineering Parallel String Sorting

  2014influential citation
• Parallel and memory-efficient Burrows-Wheeler transform

  2013cites this paper