Less space: indexing for queries with wildcards

DOI10.1016/J.TCS.2014.09.003MaRDI QIDQ300263zbMATH OpenOpenAlexFDO

Authors Moshe Lewenstein, J. Ian Munro, Venkatesh Raman, 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)

Recommendations

• Less space: indexing for queries with wildcards
• Space-efficient string indexing for wildcard pattern matching
• Space Efficient Indexes for String Matching with Don’t Cares

Cites work

• scientific article; zbMATH DE number 7051248 (Why is no real title available?)
• A data structure for dynamic trees
• Approximate string matching using compressed suffix arrays
• Compressed indexes for approximate string matching
• Compressed indexes for text with wildcards
• Compressed text indexing with wildcards
• Dictionary matching and indexing with errors and don't cares
• Document retrieval with one wildcard
• Fully-functional succinct trees
• Geometric BWT: compressed text indexing via sparse suffixes and range searching
• Improved compressed indexes for full-text document retrieval
• Indexing factors with gaps
• Less space: indexing for queries with wildcards
• Medium-Space Algorithms for Inverse BWT
• Orthogonal range searching for text indexing
• Orthogonal range searching on the RAM, revisited
• Rank/select operations on large alphabets
• Space Efficient Indexes for String Matching with Don’t Cares
• Space-efficient string indexing for wildcard pattern matching
• Substring Range Reporting
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Succinct data structures for flexible text retrieval systems
• Suffix Arrays: A New Method for On-Line String Searches
• Text Indexing and Dictionary Matching with One Error

Cited in

(11)

• Space Efficient Indexes for String Matching with Don’t Cares
• Document retrieval with one wildcard
• Document retrieval with one wildcard
• Succincter text indexing with wildcards
• Pattern masking for dictionary matching: theory and practice
• Less space: indexing for queries with wildcards
• Reordering columns for smaller indexes
• Compressed indexes for text with wildcards
• On the average-case complexity of pattern matching with wildcards
• On character-based index schemes for complex wildcard search in peer-to-peer networks
• Space-efficient string indexing for wildcard pattern matching

This page was built for publication: Less space: indexing for queries with wildcards

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