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.6974353e-05
Overall Rank: 4,243 | 71.56%
DOI: 10.14778/2809974.2809988
PDF: Download (CC BY-NC-ND 3.0)

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,485	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD	8.3800709e-05
3,715	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0549546e-05
5,603	Database Processing-in-Memory: An Experimental Study	2020	VLDB	6.0518498e-05
6,414	Evaluating Multi-GPU Sorting with Modern Interconnects	2022	SIGMOD	5.7763032e-05
7,492	Fast Multi-Column Sorting in Main-Memory Column-Stores	2016	SIGMOD	5.4981253e-05
8,390	Interleaved Multi-Vectorizing	2020	VLDB	5.325009e-05
9,145	Efficiently Joining Large Relations on Multi-GPU Systems	2025	VLDB	5.2067758e-05
11,937	Origami: A High-Performance Mergesort Framework	2022	VLDB	4.9605343e-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
212	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00024786576
250	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023080446
289	Implementing Database Operations Using SIMD Instructions	2002	SIGMOD	0.00021955394
304	GPUTeraSort: High Performance Graphics Co-processor Sorting for Large Database Management	2006	SIGMOD	0.00021569633
662	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD	0.00014972958
722	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB	0.00014470465
1,119	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD	0.00011927356
2,173	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB	8.9089575e-05
2,988	Faster Set Intersection with SIMD instructions by Reducing Branch Mispredictions	2015	VLDB	7.7659651e-05
3,403	CloudRAMSort: Fast and Efficient Large-Scale Distributed RAM Sort on Shared-Nothing Cluster	2012	SIGMOD	7.3213995e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,377	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
2	2,173	CellSort: High Performance Sorting on the Cell Processor	2007	VLDB
3	2,248	Cache-Efficient Aggregation: Hashing Is Sorting	2015	SIGMOD
4	627	Rethinking SIMD Vectorization for In-Memory Databases	2015	SIGMOD
5	4,677	Dynamic Memory Adjustment for External Mergesort	1997	VLDB
6	11,937	Origami: A High-Performance Mergesort Framework	2022	VLDB
7	2,485	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD
8	1,119	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD
9	662	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