Induced Sorting Suffixes in External Memory

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

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on information systems 2015-03, Vol.33 (3), p.1-15
Main Authors: Nong, Ge, Chan, Wai Hong, Hu, Sheng Qing, Wu, Yi
Format: Article
Language:English
Subjects:
Algorithms
Buffers
Constants
Disks
Information systems
Random access memory
Sorting
Strings
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 size n string of a constant or integer alphabet, given the RAM capacity Ω (( nW ) 0.5 ), 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.
ISSN:1046-8188
1558-2868
DOI:10.1145/2699665