Cache Efficient Radix Sort for String Sorting
Summary :
In this paper, we propose CRadix sort, a new string sorting algorithm based on MSD radix sort. CRadix sort causes fewer cache misses than MSD radix sort by uniquely associating a small block of main memory called the key buffer to each key and temporarily storing a portion of each key into its corresponding key buffer. Experimental results in running time comparisons with other string sorting algorithms are provided for showing the effectiveness of CRadix sort.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.2 pp.457-466
- Publication Date
- 2007/02/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e90-a.2.457
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Waihong NG, Katsuhiko KAKEHI, "Cache Efficient Radix Sort for String Sorting" in IEICE TRANSACTIONS on Fundamentals,
vol. E90-A, no. 2, pp. 457-466, February 2007, doi: 10.1093/ietfec/e90-a.2.457.
Abstract: In this paper, we propose CRadix sort, a new string sorting algorithm based on MSD radix sort. CRadix sort causes fewer cache misses than MSD radix sort by uniquely associating a small block of main memory called the key buffer to each key and temporarily storing a portion of each key into its corresponding key buffer. Experimental results in running time comparisons with other string sorting algorithms are provided for showing the effectiveness of CRadix sort.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.2.457/_p
Copy
@ARTICLE{e90-a_2_457,
author={Waihong NG, Katsuhiko KAKEHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Cache Efficient Radix Sort for String Sorting},
year={2007},
volume={E90-A},
number={2},
pages={457-466},
abstract={In this paper, we propose CRadix sort, a new string sorting algorithm based on MSD radix sort. CRadix sort causes fewer cache misses than MSD radix sort by uniquely associating a small block of main memory called the key buffer to each key and temporarily storing a portion of each key into its corresponding key buffer. Experimental results in running time comparisons with other string sorting algorithms are provided for showing the effectiveness of CRadix sort.},
keywords={},
doi={10.1093/ietfec/e90-a.2.457},
ISSN={1745-1337},
month={February},}
Copy
TY - JOUR
TI - Cache Efficient Radix Sort for String Sorting
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 457
EP - 466
AU - Waihong NG
AU - Katsuhiko KAKEHI
PY - 2007
DO - 10.1093/ietfec/e90-a.2.457
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2007
AB - In this paper, we propose CRadix sort, a new string sorting algorithm based on MSD radix sort. CRadix sort causes fewer cache misses than MSD radix sort by uniquely associating a small block of main memory called the key buffer to each key and temporarily storing a portion of each key into its corresponding key buffer. Experimental results in running time comparisons with other string sorting algorithms are provided for showing the effectiveness of CRadix sort.
ER -
English
