Theoretical aspects of ERa, the fastest practical suffix tree construction algorithm

TitleTheoretical aspects of ERa, the fastest practical suffix tree construction algorithm
Publication TypeConference Paper
Year of Publication2013
AuthorsJekovec, M.
Conference NameMATCOS-13
Date Published2013/10
PublisherUniversity of Primorska
Conference LocationKoper
Abstract

Efficient construction of the suffix tree given an input text is an active area of research for the past 40 years. Both theoretical computer scientists and engineers trickled the problem. Unfortunately in the last decade not many results were acknowledged between the two communities. In this paper we narrow this gap by providing formal analysis of the practically fastest to date parallel algorithm for suffix tree construction using the well-accepted Parallel External Memory model of computation.

URLhttp://lusy.fri.uni-lj.si/sites/lusy.fri.uni-lj.si/files/publications/jekovec2013-matcos13-paper.pdf