Induced sorting suffixes in external memory

Ge NONG, Wai Hong CHAN, Sheng Qing HU, Yi WU

Research output: Contribution to journalArticle

15 Citations (Scopus)

Abstract

We present in this article an external memory algorithm, called disk SA-IS (DSA-IS), to exactly emulate the induced sorting algorithm SA-IS previously proposed for sorting suffixes in RAM. DSA-IS is a new disk-friendly method for sequentially retrieving the preceding character of a sorted suffix to induce the order of the preceding suffix. For a sizen string of a constant or integer alphabet, given the RAM capacity Ω ((nW)⁰˙⁵), where W is the size of each I/O buffer that is large enough to amortize the overhead of each access to disk, both the CPU time and peak disk use of DSA-IS are O(n). Our experimental study shows that on average, DSA-IS achieves the best time and space results of all of the existing external memory algorithms based on the induced sorting principle. Copyright © 2015 ACM.
Original languageEnglish
Article number12
JournalACM Transactions on Information Systems (TOIS)
Volume33
Issue number3
DOIs
Publication statusPublished - Mar 2015

Fingerprint

Sorting
Random access storage
Data storage equipment
Program processors

Citation

Nong, G., Chan, W. H., Hu, S. Q., & Wu, Y. (2015). Induced sorting suffixes in external memory. CM Transactions on Information Systems (TOIS), 33(3), Article 12.