Better external memory suffix array construction

ABSTRACT

Suffix arrays are a simple and powerful data structure for text processing that can be used for full text indexes, data compression, and many other applications, in particular, in bioinformatics. However, so far, it has appeared prohibitive to build suffix arrays for huge inputs that do not fit into main memory. This paper presents design, analysis, implementation, and experimental evaluation of several new and improved algorithms for suffix array construction. The algorithms are asymptotically optimal in the worst case or on average. Our implementation can construct suffix arrays for inputs of up to 4-GB in hours on a low-cost machine. As a tool of possible independent interest, we present a systematic way to design, analyze, and implement pipelined algorithms.

REFERENCES

• 1: Mohamed Ibrahim Abouelhoda , Stefan Kurtz , Enno Ohlebusch, The Enhanced Suffix Array and Its Applications to Genome Analysis, Proceedings of the Second International Workshop on Algorithms in Bioinformatics, p.449-463, September 17-21, 2002
• 2: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 3: Lars Arge , Paolo Ferragina , Roberto Grossi , Jeffrey Scott Vitter, On sorting strings in external memory (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.540-548, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258647]
• 4: Lars Arge , Octavian Procopiuc , Jeffrey Scott Vitter, Implementing I/O-efficient Data Structures Using TPIE, Proceedings of the 10th Annual European Symposium on Algorithms, p.88-100, September 17-21, 2002
• 5: Burkhardt, S. and Kärkkäinen, J. 2003. Fast lightweight suffix array construction and checking. In Proc. 14th Annual Symposium on Combinatorial Pattern Matching. LNCS, vol. 2676. Springer, New York. 55--69.
• 6: Burrows, M. and Wheeler, D. J. 1994. A block-sorting lossless data compression algorithm. Technical Report 124, SRC (digital, Palo Alto) (May).
• 7: Andreas Crauser , Paolo Ferragina, On Constructing Suffix Arrays in External Memory, Proceedings of the 7th Annual European Symposium on Algorithms, p.224-235, July 16-18, 1999
• 8: Crauser, A. and Ferragina, P. 2002. Theoretical and experimental study on the construction of suffix-arrays in external memory. Algorithmica 32, 1, 1--35.
• 9: Crauser, A. and Mehlhorn, K. 1998. LEDA-SM a platform for secondary memory computations. Tech. rep., MPII. draft.
• 10: Dementiev, R. 2005. The Stxxl library. Documentation and download at http://stxxl.sourceforge.net.
• 11: Roman Dementiev , Peter Sanders, Asynchronous parallel disk sorting, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777435]
• 12: Dementiev, R., Kettner, L., and Sanders, P. 2005. Stxxl: Standard Template Library for XXL Data Sets. In Proc. 13th Annual European Symposium on Algorithms. LNCS, vol. 3669. 640--651.
• 13: Martin Farach-Colton , Paolo Ferragina , S. Muthukrishnan, On the sorting-complexity of suffix tree construction, Journal of the ACM (JACM), v.47 n.6, p.987-1011, Nov. 2000 [doi>10.1145/355541.355547]
• 14: Gaston H. Gonnet , Ricardo A. Baeza-Yates , Tim Snider, New indices for text: PAT Trees and PAT arrays, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 15: Gropp, W., Lusk, R., and Thakur, R. 1998. Latest Advances in MPI-2. Tutorial on EuroPVM/MPI'98.
• 16: Haanpää, H. 2004. Minimum sum and difference covers of Abelian groups. Journal of Integer Sequences 7, 2, article 04.1.8.
• 17: Hon, W.-K., Lam, T.-W., Sadakane, K., and Sung, W.-K. 2003a. Constructing compressed suffix-arrays with large alphabets. In Proc. 14th International Symposium on Algorithms and Computation. LNCS, vol. 2906. Springer, New York. 240--249.
• 18: Wing-Kai Hon , Kunihiko Sadakane , Wing-Kin Sung, Breaking a Time-and-Space Barrier in Constructing Full-Text Indices, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.251, October 11-14, 2003
• 19: Ulrich Meyer , Peter Sanders , Jop Sibeyn, Algorithms for Memory Hierarchies, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 20: Juha Kärkkäinen , Peter Sanders , Stefan Burkhardt, Linear work suffix array construction, Journal of the ACM (JACM), v.53 n.6, p.918-936, November 2006 [doi>10.1145/1217856.1217858]
• 21: Kim, D. K., Sim, J. S., Park, H., and Park, K. 2003. Linear-time construction of suffix arrays. In Proc. 14th Annual Symposium on Combinatorial Pattern Matching. LNCS, vol. 2676. Springer, New York. 186--199.
• 22: Ko, P. and Aluru, S. 2003. Space efficient linear-time construction of suffix-arrays. In Proc. 14th Annual Symposium on Combinatorial Pattern Matching. LNCS, vol. 2089. Springer, New York. 200--210.
• 23: Kulla, F. and Sanders, P. 2006. Scalable parallel suffix array construction. In EuroPVM/MPI. to appear.
• 24: Tak Wah Lam , Kunihiko Sadakane , Wing-Kin Sung , Siu-Ming Yiu, A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, p.401-410, August 15-17, 2002
• 25: 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]
• 26: Giovanni Manzini , Paolo Ferragina, Engineering a Lightweight Suffix Array Construction Algorithm, Proceedings of the 10th Annual European Symposium on Algorithms, p.698-710, September 17-21, 2002
• 27: Sadakane, K. and Shibuya, T. 2001. Indexing huge genome sequences for solving various problems. Genome Informatics 12, 175--183.
• 28: Abraham Silberschatz , Henry F. Korth , S. Sudershan, Database System Concepts, McGraw-Hill, Inc., New York, NY, 1998
• 29: Vitter, J. S. and Shriver, E. A. M. 1994. Algorithms for parallel memory, I: Two level memories. Algorithmica 12, 2/3, 110--147.
• 30: Weese, D. 2006. Entwurf und Implementierung eines generischen Substring-Index. M.S. thesis, Freie Universität Berlin.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Algorithm engineering, I/O-efficient, algorithms for strings, external memory, large data sets, secondary memory, suffix array