Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)

DOI10.1145/335305.335351zbMATH Open1296.68035OpenAlexW2056707490MaRDI QIDQ3192007FDOQ3192007

Jeffrey Scott Vitter, Roberto Grossi

Publication date: 26 September 2014

Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/335305.335351

Recommendations

• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Space efficient suffix trees
• Combinatorial Pattern Matching
• A categorization theorem on suffix arrays with applications to space efficient text indexes
• New text indexing functionalities of the compressed suffix arrays

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data structures (68P05) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cited In (61)

• Optimized binary search and text retrieval
• Succinct representations of permutations and functions
• Title not available (Why is that?)
• On the Structure of Consistent Partitions of Substring Set of a Word
• Title not available (Why is that?)
• Title not available (Why is that?)
• Indexing text using the Ziv--Lempel trie
• A framework for designing space-efficient dictionaries for parameterized and order-preserving matching
• Combinatorial Pattern Matching
• Replacing suffix trees with enhanced suffix arrays
• Title not available (Why is that?)
• Space efficient suffix trees
• Title not available (Why is that?)
• An index data structure for matrices, with applications to fast two-dimensional pattern matching
• A linear lower bound on index size for text retrieval
• Improved and extended locating functionality on compressed suffix arrays
• Wheeler graphs: a framework for BWT-based data structures
• A linear lower bound on index size for text retrieval
• Counting suffix arrays and strings
• Title not available (Why is that?)
• An experimental study of a compressed index
• Algorithms and Computation
• Compressed indexes for text with wildcards
• On compressing and indexing repetitive sequences
• Approximate string matching using compressed suffix arrays
• Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays
• Compressed indexes for approximate string matching
• Locally compressed suffix arrays
• Compressed data structures: Dictionaries and data-aware measures
• Time-space trade-offs for compressed suffix arrays.
• Forty Years of Text Indexing
• Ranked document retrieval for multiple patterns
• Title not available (Why is that?)
• Succinct non-overlapping indexing
• Title not available (Why is that?)
• Self-indexing Based on LZ77
• Succincter Text Indexing with Wildcards
• Using static suffix array in dynamic application: case of text compression by longest first substitution
• Algorithms for Indexing Highly Similar DNA Sequences
• On-line construction of compact directed acyclic word graphs
• Ranked Document Retrieval with Forbidden Pattern
• Reducing space for index implementation.
• Constructing suffix arrays in linear time
• Succinct Non-overlapping Indexing
• Distribution-aware compressed full-text indexes
• An artificial neural network based approach for online string matching/filtering of large databases
• Linear Time Suffix Array Construction Using D-Critical Substrings
• Improved characters distance sampling for online and offline text searching
• The cell probe complexity of succinct data structures
• Wavelet trees for all
• Time-space trade-offs for Lempel-Ziv compressed indexing
• New text indexing functionalities of the compressed suffix arrays
• Improved approximate string matching using compressed suffix data structures
• Title not available (Why is that?)
• Text indexing with errors
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching
• Opportunistic data structures for range queries
• Compressed data structures for strings. On searching and extracting strings from compressed textual data
• Suffix Arrays: A New Method for On-Line String Searches
• Using compressed suffix-arrays for a compact representation of temporal-graphs

This page was built for publication: Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)

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