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: 11194
Venue: VLDB
Year: 2015
Pagerank: 6.8499317e-05
Overall Rank: 4,177 | 71.35%
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,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
5,536	Database Processing-in-Memory: An Experimental Study	2020	VLDB	6.1822684e-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
8,238	Interleaved Multi-Vectorizing	2020	VLDB	5.4599422e-05
9,333	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.2887551e-05
11,579	Origami: A High-Performance Mergesort Framework	2022	VLDB	5.093636e-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
209	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024932174
252	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023242719
293	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00022259273
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,212	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.6328776e-05
3,368	CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster	2012	SIGMOD	7.4713287e-05

Semantically Similar Papers

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