Engineering a fast online persistent suffix tree construction

Online persistent suffix tree construction has been con-sidered impractical due to its excessive I/O costs. However, these prior studies have not taken into account the effects of the buffer management policy and the internal node struc-ture of the suffix tree on I/O behavior of construction and subsequent retrievals over the tree. In this paper, we study these two issues in detail in the context of large genomic DNA and Protein sequences. In particular, we make the fol-lowing contributions: (i) a novel, low-overhead buffering policy called TOP-Q which improves the on-disk behavior of suffix tree construction and subsequent retrievals, and (ii) empirical evidence that the space efficient linked-list rep-resentation of suffix tree nodes provides significantly infe-rior performance when compared to the array represen-tation. These results demonstrate that a careful choice of implementation strategies can make online persistent suf-fix tree construction considerably more scalable – in terms of length of sequences indexed with a fixed memory bud-get, than currently perceived. 1