The performance of linear time suffix sorting algorithms

S.J. Puglisi; W.F. Smyth; A. Turpin

doi:10.1109/DCC.2005.87

Back

The performance of linear time suffix sorting algorithms

Conference paper

Open access

The performance of linear time suffix sorting algorithms

S.J. Puglisi, W.F. Smyth and A. Turpin

Data Compression Conference, pp.358-367

Data Compression Conference (DCC) 2005 (Snowbird, Utah, USA, 29/03/2005–31/03/2005)

2005

DOI: https://doi.org/10.1109/DCC.2005.87

Files and links (2)

pdf

linear_time_suffix.pdfDownload View

Published (Version of Record) Open Access

url

Link to Published Version *Subscription may be requiredView

Abstract

We have illustrated that the superior asymptotic complexity of linear time suffix sorting algorithms does not readily translate into faster suffix sorting, compared to implementations of supralinear algorithms. We have also resolved the ambiguity surrounding the practicality of the Algorithm KA: it is slower than supralinear approaches on real data. We described several optimizations to the O(n) KS algorithm that significantly improve performance for real world inputs, but still fall short of some supralinear approaches. It is worth noting that most of the optimizations we describe could also be applied to Algorithm KB, which may then outperform the well tuned suffix sorter of Manzini and Ferragina (2004).

Details

Title: The performance of linear time suffix sorting algorithms
Authors/Creators: S.J. Puglisi (Author/Creator) - Curtin University
W.F. Smyth (Author/Creator) - McMaster University
A. Turpin (Author/Creator) - The University of Melbourne
Publication Details: Data Compression Conference, pp.358-367
Conference: Data Compression Conference (DCC) 2005 (Snowbird, Utah, USA, 29/03/2005–31/03/2005)
Identifiers: 991005540623507891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Conference paper

Metrics

256 File views/ downloads

107 Record Views