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: h98072692e08cdea5
Venue: VLDB
Year: 2015
Pagerank: 6.8227646e-05
Overall Rank: 4,065 | 72.68%
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,487	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD	8.3979719e-05
3,714	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0769061e-05
5,541	Vortex: Overcoming Memory Capacity Limitations in GPU-Accelerated Large-Scale Data Analytics	2025	VLDB	6.0902254e-05
6,213	Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities	2019	CIDR	5.8479612e-05
6,414	Evaluating Multi-GPU Sorting with Modern Interconnects	2022	SIGMOD	5.7927521e-05
7,495	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	5.5091753e-05
11,986	Efficient String Sort with Multi-Character Encoding and Adaptive Sampling	2021	SIGMOD	4.9793485e-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
106	Quickly Generating Billion-Record Synthetic Databases	1994	SIGMOD	0.00033526937
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023143736
304	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00021604795
661	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00015003815
722	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.00014488003
1,116	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011962096
2,161	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB	8.9357193e-05
3,393	CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster	2012	SIGMOD	7.3471344e-05
3,448	A Super Scalar Sort Algorithm for RISC Processors	1996	SIGMOD	7.2934723e-05

Semantically Similar Papers

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