SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures

Summary: A SIMD- and cache-aware multiway mergesort for arrays of structures, avoiding the scattered-record rearrangement that bottlenecks packed key-index sorting. Delivers up to 2.1× higher single-core performance and stronger multicore scalability, especially for large records. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hb506dbe237bebbc3
Venue: VLDB
Year: 2015
Pagerank: 6.7207703e-05
Overall Rank: 4,225 | 71.60%
DOI: 10.14778/2809974.2809988

Incoming Non-self Citations Over Time

Authors

1. Hiroshi Inoue (IBM)
2. Kenjiro Taura (University of Tokyo)

BibTeX Citation

@article{inoue_vldb15,
        title = {{SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures}},
        author = {Inoue, Hiroshi and Taura, Kenjiro},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {11},
        pages = {1274--1285},
        doi = {10.14778/2809974.2809988},
        url = {https://doi.org/10.14778/2809974.2809988},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 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,598	Database Processing-in-Memory: An Experimental Study	2020	VLDB	6.0713144e-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
8,380	Interleaved Multi-Vectorizing	2020	VLDB	5.3429493e-05
9,429	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.1786456e-05
11,887	Origami: A High-Performance Mergesort Framework	2022	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
210	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024851502
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023143736
287	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00021970198
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,289	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.4528818e-05
3,393	CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster	2012	SIGMOD	7.3471344e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,328	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
2	2,161	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB
3	2,245	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD
4	627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD
5	4,692	Dynamic Memory Adjustment for External Mergesort	1997	VLDB
6	11,887	Origami: A High-Performance Mergesort Framework	2022	VLDB
7	2,487	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD
8	1,116	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD
9	661	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD
10	722	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB