External Memory Suffix Array Construction

Jens Mehnert <mail@jmehnertATmpi-sbDOTmpgDOTde>

November 2004

Diploma thesis, Department of Computer Science, Saarland University
supervisor: Prof. Dr. Peter Sanders, University Karlsruhe


In the recent years, a lot of theoretical work has been done on suffix tree and suffix array construction. In 2000, it was shown that suffix trees and thereby suffix arrays (converted from the suffix trees) over an integer alphabet, can be constructed in linear time. In 2003, three linear suffix array construction algorithms were published which do not require suffix trees. We have adapted one of these algorithms to external memory  and applied several improvements to it and other external memory suffix array construction algorithms. One of these improvement is called pipelining which reduces the I/Os of the algorithms, significantly.



Reference Manual (incl. Source Browsing)