Induced sorting suffixes in external memory

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

Research output: Contribution to journalArticles

18 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

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.

Fingerprint Dive into the research topics of 'Induced sorting suffixes in external memory'. Together they form a unique fingerprint.