Suffix arrays: what are they good for?

ABSTRACT

Recently the theoretical community has displayed a flurry of interest in suffix arrays, and compressed suffix arrays. New, asymptotically optimal algorithms for construction, search, and compression of suffix arrays have been proposed. In this talk we will present our investigations into the practicalities of these latest developments. In particular, we investigate whether suffix arrays can indeed replace inverted files, as suggested in recent literature on suffix arrays.

REFERENCES

• 1: Mohamed Ibrahim Abouelhoda , Stefan Kurtz , Enno Ohlebusch, Replacing suffix trees with enhanced suffix arrays, Journal of Discrete Algorithms, v.2 n.1, p.53-86, March 2004 [doi>10.1016/S1570-8667(03)00065-0]
• 2: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 3: P. Ferragina , G. Manzini, Opportunistic data structures with applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.390, November 12-14, 2000
• 4: Paolo Ferragina , Giovanni Manzini, An experimental study of an opportunistic index, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 07-09, 2001, Washington, D.C., United States
• 5: Roberto Grossi , Jeffrey Scott Vitter, Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching, SIAM Journal on Computing, v.35 n.2, p.378-407, 2005 [doi>10.1137/S0097539702402354]
• 6: Roberto Grossi , Ankur Gupta , Jeffrey Scott Vitter, When indexing equals compression: experiments with compressing suffix arrays and applications, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 7: Knuth, D. E., Morris, J. H. & Pratt, V. R. (1977), 'Fast pattern matching in strings', SIAM Journal on Computing 6(2), 323-350.
• 8: Veli Mäkinen, Compact Suffix Array, Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, p.305-319, June 21-23, 2000
• 9: Mäakinen, V. & Navarro, G. (2004), Compressed compact suffix arrays, in 'Combinatorial Pattern Matching: 15th Annual Symposium, CPM 2004', Vol. LNCS 3109, Springer-Verlag GmbH, pp. 420-433.
• 10: Mäkinen, V. & Navarro, G. (2005), 'Succinct suffix arrays based on run-length encoding', Nordic Journal of Computing 12(2), 40-66.
• 11: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
• 12: Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, SIAM Journal on Computing, v.22 n.5, p.935-948, Oct. 1993 [doi>10.1137/0222058]
• 13: Gonzalo Navarro, Indexing text using the Ziv-Lempel trie, Journal of Discrete Algorithms, v.2 n.1, p.87-114, March 2004 [doi>10.1016/S1570-8667(03)00066-2]
• 14: Simon J. Puglisi , William F. Smyth , Andrew Turpin, The Performance of Linear Time Suffix Sorting Algorithms, Proceedings of the Data Compression Conference, p.358-367, March 29-31, 2005 [doi>10.1109/DCC.2005.87]
• 15: Puglisi, S. J., Turpin, A. H. & Smyth, W. F. (2005b), A taxonomy of suffix array construction algorithms, in 'Proceedings of the Prague Stringology Conference', Czech Technical University, Prague, pp. 1-30.
• 16: Kunihiko Sadakane, Compressed Text Databases with Efficient Query Algorithms Based on the Compressed Suffix Array, Proceedings of the 11th International Conference on Algorithms and Computation, p.410-421, December 18-20, 2000
• 17: Kunihiko Sadakane, Succinct representations of lcp information and improvements in the compressed suffix arrays, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.225-232, January 06-08, 2002, San Francisco, California
• 18: Sadakane, K. & Shibuya, T. (2001), 'Indexing huge genome sequences for solving various problems', Genome Informatics 12, 175-183.
• 19: Sim, J. S., Kim, D. K., Park, H. & Park, K. (2003), Linear-time search in suffix arrays, in 'Proc. 14th Australian Workshop Combinatorial Alg. (AWOCA)', pp. 139-146.
• 20: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 21: Zobel, J. & Moffat, A. (n.d.), 'Inverted files for text search engines'. Submitted for publication.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  E. Data
  E.5 FILES
      Subjects: Organization/structure
  E.m MISCELLANEOUS

General Terms:
Design, Performance