Sparse suffix tree construction in small space

DOI10.1007/978-3-642-39206-1_13MaRDI QIDQ5326557zbMATH OpenOpenAlexWikidataFDO

Authors Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj

Publication date 6 August 2013

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.1135

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Abstract: We consider the problem of constructing a sparse suffix tree (or suffix array) for $b$ suffixes of a given text $T$ of size $n$, using only $O(b)$ words of space during construction time. Breaking the naive bound of $Omega(nb)$ time for this problem has occupied many algorithmic researchers since a different structure, the (evenly spaced) sparse suffix tree, was introduced by K{"a}rkk{"a}inen and Ukkonen in 1996. While in the evenly spaced sparse suffix tree the suffixes considered must be evenly spaced in $T$, here there is no constraint on the locations of the suffixes. We show that the sparse suffix tree can be constructed in $O(nlo{g}^{2}b)$ time. To achieve this we develop a technique, which may be of independent interest, that allows to efficiently answer $b$ longest common prefix queries on suffixes of $T$, using only $O(b)$ space. We expect that this technique will prove useful in many other applications in which space usage is a concern. Furthermore, additional tradeoffs between the space usage and the construction time are given.

Recommendations

• Sparse text indexing in small space
• Sparse suffix tree construction in optimal time and space
• Faster sparse suffix sorting
• Space efficient suffix trees
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching

Cited in

(13)

• Space-efficient representation of truncated suffix trees, with applications to Markov order estimation
• Deterministic Sparse Suffix Sorting on Rewritable Texts
• Orthogonal range searching for text indexing
• The property suffix tree with dynamic properties
• Faster sparse suffix sorting
• Sparse and truncated suffix trees on variable-length codes
• Sparse suffix tree construction in optimal time and space
• Space-efficient construction algorithm for the circular suffix tree
• Sparse text indexing in small space
• Optimal Substring Equality Queries with Applications to Sparse Text Indexing
• On-Line Linear-Time Construction of Word Suffix Trees
• Deterministic Sparse Suffix Sorting in the Restore Model
• Sparse suffix trees

This page was built for publication: Sparse suffix tree construction in small space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326557)