PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort

Summary: PARADIS: parallel in-place radix sort with speculative permutation (stripes per core) and a parallel repair phase in a shared-nothing design. Adaptive load balancing allocates processors to buckets, addressing skew and enabling scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11218
Venue: VLDB
Year: 2015
Pagerank: 6.9501893e-05
Overall Rank: 4,021 | 72.42%
DOI: 10.14778/2824032.2824050

Incoming Non-self Citations Over Time

Authors

1. Minsik Cho (IBM)
2. Ulrich Finkler (IBM)
3. Daniel Brand (IBM)
4. Vincent Kulandaisamy (IBM)
5. Rajesh Bordawekar (IBM)
6. Ruchir Puri (IBM)

BibTeX Citation

@article{cho_vldb15,
        title = {{PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort}},
        author = {Cho, Minsik and Finkler, Ulrich and Brand, Daniel and Kulandaisamy, Vincent and Bordawekar, Rajesh and Puri, Ruchir},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {12},
        doi = {10.14778/2824032.2824050},
        url = {https://doi.org/10.14778/2824032.2824050},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,667	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD	8.2756346e-05
3,865	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0621718e-05
6,065	Vortex: Overcoming Memory Capacity Limitations in GPU-Accelerated Large-Scale Data Analytics	2025	VLDB	5.9895288e-05
6,161	Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities	2019	CIDR	5.9537202e-05
6,774	Evaluating Multi-GPU Sorting with Modern Interconnects	2022	SIGMOD	5.7778738e-05
7,242	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	5.6641994e-05
11,679	Efficient String Sort with Multi-Character Encoding and Adaptive Sampling	2021	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
105	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033877899
252	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023242719
305	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00021872796
678	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015061068
712	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.0001468812
1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011808761
2,139	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB	9.1061768e-05
3,368	CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster	2012	SIGMOD	7.4713287e-05
3,396	A Super Scalar Sort Algorithm for RISC Processors	1996	SIGMOD	7.4473906e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	678	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD
2	7,705	A Study of Sort Algorithms for Multiprocessor Database Machines	1986	VLDB
3	12,295	Permuting Data on Random-Access Block Storage	2013	VLDB
4	4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
5	6,699	Percentile Finding Algorithm for Multiple Sorted Runs	1989	VLDB
6	1,299	A Low Communication Sort Algorithm for a Parallel Database Machine	1989	VLDB
7	5,094	On the Surprising Difficulty of Simple Things: the Case of Radix Partitioning	2015	VLDB
8	11,679	Efficient String Sort with Multi-Character Encoding and Adaptive Sampling	2021	SIGMOD
9	2,667	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD
10	1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD