Efficient String Sort with Multi-Character Encoding and Adaptive Sampling

Summary: Proposes a multi-character encoding to shrink radix in string sorting, leveraging sparse alphabet use and distinguishing-prefix sparsity. Paired with adaptive sampling, it blends radix sort with sample sort, delivering ~4.85x STL, ~1.5x state-of-the-art radix, and competitive parallel performance (pS5). (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6271
Venue: SIGMOD
Year: 2021
Pagerank: 5.093636e-05
Overall Rank: 11,679 | 19.88%
DOI: 10.1145/3448016.3457319

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Wen Jin (Independent)
2. Weining Qian (East China Normal University)
3. Aoying Zhou (East China Normal University)

BibTeX Citation

@inproceedings{jin_sigmod21,
        title = {{Efficient String Sort with Multi-Character Encoding and Adaptive Sampling}},
        author = {Jin, Wen and Qian, Weining and Zhou, Aoying},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457319},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457319},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3,865	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0621718e-05
4,021	PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort	2015	VLDB	6.9501893e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,951	On Searching Compressed String Collections Cache-Obliviously	2008	PODS
2	12,033	A Study of Sorting Algorithms on Approximate Memory	2016	SIGMOD
3	712	Efficient Implementation of Sorting on Multi-Core SIMD CPU Architecture	2008	VLDB
4	1,177	A Comprehensive Study of Main-Memory Partitioning and its Application to Large-Scale Comparison- and Radix-Sort	2014	SIGMOD
5	678	Fast Sort on CPUs and GPUs: A Case for Bandwidth Oblivious SIMD Sort	2010	SIGMOD
6	2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD
7	4,021	PARADIS: An Efficient Parallel Algorithm for In-place Radix Sort	2015	VLDB
8	2,667	A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs	2017	SIGMOD
9	4,177	SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures	2015	VLDB
10	3,865	The Case for a Learned Sorting Algorithm	2020	SIGMOD