Catalog Home Page

The performance of linear time suffix sorting algorithms

Puglisi, S.J., Smyth, W.F. and Turpin, A. (2005) The performance of linear time suffix sorting algorithms. In: Data Compression Conference (DCC) 2005, 29 - 31 March 2005, Snowbird, Utah, USA pp. 358-367.

[img]
Preview
PDF - Published Version
Download (136kB)
Link to Published Version: http://dx.doi.org/10.1109/DCC.2005.87
*Subscription may be required

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

Publication Type: Conference Paper
URI: http://researchrepository.murdoch.edu.au/id/eprint/27921
Item Control Page Item Control Page

Downloads

Downloads per month over past year