Less space: indexing for queries with wildcards

DOI10.1016/j.tcs.2014.09.003zbMath1338.68053OpenAlexW1964432965MaRDI QIDQ300263

J. Ian Munro, Venkatesh Raman, Moshe Lewenstein, Sharma V. Thankachan

Publication date: 27 June 2016

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.09.003

zbMATH Keywords

data structuresrange searchingsuffix treeswildcardsstring indexing

Mathematics Subject Classification ID

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

Related Items

On the average-case complexity of pattern matching with wildcards

Cites Work

• Unnamed Item
• Unnamed Item
• Compressed indexes for text with wildcards
• Approximate string matching using compressed suffix arrays
• Succinct data structures for flexible text retrieval systems
• A data structure for dynamic trees
• String indexing for patterns with wildcards
• Geometric BWT: compressed text indexing via sparse suffixes and range searching
• Improved compressed indexes for full-text document retrieval
• Indexing factors with gaps
• Compressed text indexing with wildcards
• Orthogonal Range Searching for Text Indexing
• Less Space: Indexing for Queries with Wildcards
• Document Retrieval with One Wildcard
• Space-Efficient String Indexing for Wildcard Pattern Matching.
• Substring Range Reporting
• Suffix Arrays: A New Method for On-Line String Searches
• Dictionary matching and indexing with errors and don't cares
• Rank/select operations on large alphabets
• Medium-Space Algorithms for Inverse BWT
• Text Indexing and Dictionary Matching with One Error
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Space Efficient Indexes for String Matching with Don’t Cares
• Orthogonal range searching on the RAM, revisited
• Compressed indexes for approximate string matching