Efficient suffix trees on secondary storage

Abstract

We present a new representation for suffix trees, a data structure used in full text searching, that uses little more storage than the log n bits per index point required to store the list of index points. We also show algorithms for maintaining the structure on secondary storage in such a way that we minimize the number of disk accesses while searching and we can efficiently handle changes to the text. Using this new representation, suffix trees are competitive in terms of space with, and actually offer significantly better performance than, existing methods for full text searching. While we present new algorithms and data structures in this paper, the emphasis is on practical searching methods that have been empirically verified against real data.