Cache efficient radix sort for string sorting

Waihong Ng; Katsuhiko Kakehi

doi:10.1093/ietfec/e90-a.2.457

Cache efficient radix sort for string sorting

Waihong Ng^*, Katsuhiko Kakehi

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

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.

Original language	English
Pages (from-to)	457-466
Number of pages	10
Journal	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Volume	E90-A
Issue number	2
DOIs	https://doi.org/10.1093/ietfec/e90-a.2.457
Publication status	Published - 2007 Feb

Keywords

Cache
High performance
Radix sort
Sorting
String sorting

ASJC Scopus subject areas

Electrical and Electronic Engineering
Hardware and Architecture
Information Systems

Access to Document

10.1093/ietfec/e90-a.2.457

Cite this

@article{cebc3fa421e1464fabbc6d8d8d329e5f,

title = "Cache efficient radix sort for string sorting",

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 = "Cache, High performance, Radix sort, Sorting, String sorting",

author = "Waihong Ng and Katsuhiko Kakehi",

year = "2007",

month = feb,

doi = "10.1093/ietfec/e90-a.2.457",

language = "English",

volume = "E90-A",

pages = "457--466",

journal = "IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences",

issn = "0916-8508",

publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",

number = "2",

}

TY - JOUR

T1 - Cache efficient radix sort for string sorting

AU - Ng, Waihong

AU - Kakehi, Katsuhiko

PY - 2007/2

Y1 - 2007/2

N2 - 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.

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.

KW - Cache

KW - High performance

KW - Radix sort

KW - Sorting

KW - String sorting

UR - http://www.scopus.com/inward/record.url?scp=33847143568&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33847143568&partnerID=8YFLogxK

U2 - 10.1093/ietfec/e90-a.2.457

DO - 10.1093/ietfec/e90-a.2.457

M3 - Article

AN - SCOPUS:33847143568

SN - 0916-8508

VL - E90-A

SP - 457

EP - 466

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 2

ER -

Cache efficient radix sort for string sorting

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this