Back to papers
A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort
Summary: Comprehensive study of main-memory partitioning across the memory hierarchy, revisiting in-cache pitfalls and introducing out-of-cache, in-place, and NUMA-aware partitioning variants. Proposes three NUMA-aware sorts—stable LSB radix, in-place MSB radix, and a wide-fanout comparison-sort with a cache-resident range index—achieving fastest billion-scale performance for dense and sparse keys and enabling building other ops (joins, aggregation).
(summarized by gpt-5-nano on Feb 09 2026)
Paper ID
4955
Venue
SIGMOD
Year
2014
Pagerank
0.00011808761
Overall Rank
1,177 | 91.93%
DOI
10.1145/2588555.2610522
Incoming Non-self Citations Over Time
BibTeX Citation
@inproceedings{polychroniou_sigmod14,
title = {{A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort}},
author = {Polychroniou, Orestis and Ross, Kenneth A.},
series = {{SIGMOD} '14},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/2588555.2610522},
url = {https://dl.acm.org/doi/10.1145/2588555.2610522},
year = {2014}
}
Incoming Citations (Sorted by Pagerank)
Showing 35 of 35 citing papers.
Rank
Citing Paper
Year
Venue
Pagerank
634
Rethinking SIMD Vectorization for In-Memory Databases 2015
SIGMOD
0.00015533814
976
The End of Slow Networks: It's Time for a Redesign 2016
VLDB
0.00012864533
1,466
A Study of the Fundamental Performance Characteristics of GPUs and CPUs for Database Analytics 2020
SIGMOD
0.0001068941
1,761
ByteSlice: Pushing the Envelop of Main Memory Data Processing with a New Storage Layout 2015
SIGMOD
9.8154969e-05
1,974
Track Join: Distributed Joins with Minimal Network Traffic 2014
SIGMOD
9.3658402e-05
2,250
Cache-Efficient Aggregation: Hashing Is Sorting 2015
SIGMOD
8.8694486e-05
2,667
A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs 2017
SIGMOD
8.2756346e-05
2,962
To Partition, or Not to Partition, That is the Join Question in a Real System 2021
SIGMOD
7.9170451e-05
3,344
RUMA has it: Rewired User-space Memory Access is Possible! 2016
VLDB
7.4980897e-05
3,598
Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017
SIGMOD
7.2718988e-05
4,021
PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort 2015
VLDB
6.9501893e-05
4,177
SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures 2015
VLDB
6.8499317e-05
4,780
Can Learned Models Replace Hash Functions? 2023
VLDB
6.5118885e-05
4,840
FPGA-based Data Partitioning 2017
SIGMOD
6.483442e-05
5,039
Holistic Indexing in Main-memory Column-stores 2015
SIGMOD
6.3909067e-05
5,094
On the Surprising Difficulty of Simple Things: the Case of Radix Partitioning 2015
VLDB
6.3657592e-05
5,947
Revisiting Reuse in Main Memory Database Systems 2017
SIGMOD
6.0323707e-05
6,161
Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities 2019
CIDR
5.9537202e-05
6,187
Robust Performance of Main Memory Data Structures by Configuration 2020
SIGMOD
5.9485755e-05
6,263
Database Technology for the Masses: Sub-Operators as First-Class Entities 2021
VLDB
5.936052e-05
6,665
MorphStore: Analytical Query Engine with a Holistic Compression-Enabled Processing Model 2020
VLDB
5.8089595e-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
7,287
Is Perfect Hashing Practical for OLAP Systems? 2024
CIDR
5.6544795e-05
7,899
Modularis: Modular Relational Analytics over Heterogeneous Distributed Platforms 2021
VLDB
5.5195553e-05
8,636
Adaptive Code Generation for Data-Intensive Analytics 2021
VLDB
5.3954959e-05
8,880
Entropy-Learned Hashing: Constant Time Hashing with Controllable Uniformity 2022
SIGMOD
5.3524255e-05
9,887
Adaptive Indexing of Objects with Spatial Extent 2023
VLDB
5.2006273e-05
9,986
Thriving in the No Man’s Land between Compilers and Databases 2019
CIDR
5.1832796e-05
10,409
TQEx: Tensor-based Query Engine Enhanced by Bridging the Gap 2026
SIGMOD
5.093636e-05
11,200
High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance 2024
SIGMOD
5.093636e-05
11,348
Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets 2024
VLDB
5.093636e-05
11,437
Cracking-Like Join for Trusted Execution Environments 2023
VLDB
5.093636e-05
11,579
Origami: A High-Performance Mergesort Framework 2022
VLDB
5.093636e-05
12,033
A Study of Sorting Algorithms on Approximate Memory 2016
SIGMOD
5.093636e-05
Outgoing Citations (Sorted by Pagerank)
Showing 12 of 12 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
Semantically Similar Papers
#
Overall Rank
Paper
Year
Venue
1
7,705
A Study of Sort Algorithms for Multiprocessor Database Machines 1986
VLDB
2
7,242
Fast Multi-Column Sorting in Main-Memory Column-Stores 2016
SIGMOD
3
252
Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited 2014
VLDB
4
4,607
Adaptive NUMA-aware data placement and task scheduling for analytical workloads in main-memory column-stores 2017
VLDB
5
6,161
Data Partitioning for In-Memory Systems: Myths, Challenges, and Opportunities 2019
CIDR
6
2,667
A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs 2017
SIGMOD
7
4,177
SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures 2015
VLDB
8
678
Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort 2010
SIGMOD
9
5,094
On the Surprising Difficulty of Simple Things: the Case of Radix Partitioning 2015
VLDB
10
423
Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems 2012
VLDB