Abstract
A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in space. Some implementation considerations are discussed, and new work on the modification of these search trees in response to incremental changes in the strings they index (the update problem) is presented.
Keywords
SubstringSuffix treeAlgorithmGeneralized suffix treeComputer scienceSearch treeSuffixSpace (punctuation)Tree (set theory)Search algorithmTheoretical computer scienceMathematicsData structureCombinatorics
Affiliated Institutions
Related Publications
The K-D-B-tree
The problem of retrieving multikey records via range queries from a large, dynamic index is considered. By large it is meant that most of the index must be stored on secondary m...
ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees
Evolutionary histories can be discordant across the genome, and such discordances need to be considered in reconstructing the species phylogeny. ASTRAL is one of the leading met...
A linear space algorithm for computing maximal common subsequences
The problem of finding a longest common subsequence of two strings has been solved in quadratic time and space. An algorithm is presented which will solve this problem in quadra...
GHOSTX: An Improved Sequence Homology Search Algorithm Using a Query Suffix Array and a Database Suffix Array
DNA sequences are translated into protein coding sequences and then further assigned to protein families in metagenomic analyses, because of the need for sensitivity. However, h...
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects
The problem of indexing multidimensional objects is considered. First, a classification of existing methods is given along with a discussion of the major issues involved in mult...
Publication Info
- Year
- 1976
- Type
- article
- Volume
- 23
- Issue
- 2
- Pages
- 262-272
- Citations
- 1502
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
1502
OpenAlex
Cite This
Edward M. McCreight
(1976).
A Space-Economical Suffix Tree Construction Algorithm.
Journal of the ACM
, 23
(2)
, 262-272.
https://doi.org/10.1145/321941.321946
Identifiers
- DOI
- 10.1145/321941.321946