Geometric BWT: compressed text indexing via sparse suffixes and range searching

DOI10.1007/s00453-013-9792-1zbMath1314.68115OpenAlexW2049415039MaRDI QIDQ2346957

Wing-Kai Hon, Yu-Feng Chien, Rahul Shah, Jeffrey Scott Vitter, Sharma V. Thankachan

Publication date: 26 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9792-1

zbMATH Keywords

text indexingentropy compressiongeometric range searching

Mathematics Subject Classification ID

Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items (4)

Less space: indexing for queries with wildcards ⋮ Extracting the sparse longest common prefix array from the suffix binary search tree ⋮ Space-Efficient Frameworks for Top- k String Retrieval ⋮ Position-restricted substring searching over small alphabets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Compressed text indexing with wildcards
• Compressed suffix trees with full functionality
• Forbidden Patterns
• Compressed representations of sequences and full-text indexes
• Suffix Arrays: A New Method for On-Line String Searches
• The string B-tree
• Fully compressed suffix trees
• Lower bounds for orthogonal range searching: I. The reporting case
• A Lempel-Ziv Text Index on Secondary Storage
• Position-Restricted Substring Searching
• Indexing compressed text
• Compression, Indexing, and Retrieval for Massive String Data
• A Space-Economical Suffix Tree Construction Algorithm
• On the Suppression of Chaos by Means of Bounded Excitations in an Inverted Pendulum
• Dynamic Entropy-Compressed Sequences and Full-Text Indexes
• Efficient Data Structures for the Orthogonal Range Successor Problem
• Cache-oblivious planar orthogonal range searching and counting
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Algorithms and Computation
• SP-GiST: An extensible database index for supporting space partitioning trees
• Sparse suffix trees

This page was built for publication: Geometric BWT: compressed text indexing via sparse suffixes and range searching