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.
*Subscription may be required
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|
|Item Control Page|
Downloads per month over past year