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

^*この研究の対応する著者

研究成果: Article › 査読

5 被引用数 (Scopus)

抄録

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.

本文言語	English
ページ（範囲）	457-466
ページ数	10
ジャーナル	IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
巻	E90-A
号	2
DOI	https://doi.org/10.1093/ietfec/e90-a.2.457
出版ステータス	Published - 2007 2月

ASJC Scopus subject areas

電子工学および電気工学
ハードウェアとアーキテクチャ
情報システム

文献へのアクセス

10.1093/ietfec/e90-a.2.457

他のファイルとリンク

引用スタイル

@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

抄録

ASJC Scopus subject areas

文献へのアクセス

他のファイルとリンク

フィンガープリント

引用スタイル