2016/09/30 by Matevž Jekovec, Jekovec, Matevž, Andrej Brodnik +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1609.09654
openalex publication_date 2016/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Efficient construction of the suffix tree given an input text is an active area of research from the time it was first introduced. Both theoretical computer scientists and engineers tackled the problem. In this paper we focus on the fastest practical suffix tree construction algorithm to date, ERA. We first provide a theoretical analysis of the algorithm assuming the uniformly random text as an input and using the PEM model of computation with respect to the lower bounds. Secondly, we empirically confirm the theoretical results in different test scenarios exposing the critical terms. Thirdly, we discuss the fundamental characteristics of the input text where the fastest suffix tree construction algorithms in practice fail. This paper serves as a foundation for further research in the parallel text indexing area.