Practical compressed suffix trees
type: Item
instance of: scholarly article
title: Practical compressed suffix trees
zbMATH Open document ID: 1461.68060
author: Andrés Abeliuk
author: Rodrigo Cánovas
author: Gonzalo Navarro
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: The suffix tree is an extremely important data structure in bioinformatics. Classical implementations require much space, which renders them useless to handle large sequence collections. Recent research has obtained various compressed representations for suffix trees, with widely different space-time tradeoffs. In this paper we show how the use of \textit{range min-max trees} yields novel representations achieving practical space/time tradeoffs. In addition, we show how those trees can be modified to index highly repetitive collections, obtaining the first compressed suffix tree representation that effectively adapts to that scenario.
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 7042163
zbMATH Keywords: suffix trees
zbMATH Keywords: compressed data structures
zbMATH Keywords: repetitive sequence collections
zbMATH Keywords: bioinformatics
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6020319
OpenAlex ID: W2059029449
cites work: A Space-Economical Suffix Tree Construction Algorithm
cites work: Q3690245
cites work: Algorithms on Strings, Trees and Sequences
cites work: Suffix Arrays: A New Method for On-Line String Searches
cites work: Replacing suffix trees with enhanced suffix arrays
cites work: Space efficient suffix trees
cites work: Q4828936
cites work: Compressed suffix trees with full functionality
cites work: New text indexing functionalities of the compressed suffix arrays
cites work: Fully-Compressed Suffix Trees
cites work: Fully compressed suffix trees
cites work: Compressed representations of sequences and full-text indexes
cites work: An analysis of the Burrows—Wheeler transform
cites work: An(other) Entropy-Bounded Compressed Suffix Tree
cites work: Faster entropy-bounded compressed suffix trees
cites work: Wee LCP
cites work: Engineering a compressed suffix tree implementation
cites work: Q5417613
cites work: Succinct Trees in Practice
cites work: Self-indexing Based on LZ77
cites work: Self-indexed Text Compression Using Straight-Line Programs
cites work: Compressed text indexes
cites work: Compressed Text Indexes with Fast Locate
cites work: Q5708460
cites work: Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
cites work: Practical Entropy-Compressed Rank/Select Dictionary
cites work: Space-Time Tradeoffs for Longest-Common-Prefix Array Computation
cites work: Permuted Longest-Common-Prefix Array
cites work: A simple optimal representation for balanced parentheses
cites work: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
cites work: Practical Compact Indexes for Top-kDocument Retrieval
cites work: A fully linear-time approximation algorithm for grammar-based compression
DOI: 10.3390/A6020319
description: scientific article; zbMATH DE number 7042163