Substring Range Reporting

DOI10.1007/978-3-642-21458-5_26MaRDI QIDQ3011863zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Philip Bille, Inge Li Gørtz

Publication date 29 June 2011

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.3683

Mathematics Subject Classification ID

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

Abstract: We revisit various string indexing problems with range reporting features, namely, position-restricted substring searching, indexing substrings with gaps, and indexing substrings with intervals. We obtain the following main results. {itemize} We give efficient reductions for each of the above problems to a new problem, which we call emph{substring range reporting}. Hence, we unify the previous work by showing that we may restrict our attention to a single problem rather than studying each of the above problems individually. We show how to solve substring range reporting with optimal query time and little space. Combined with our reductions this leads to significantly improved time-space trade-offs for the above problems. In particular, for each problem we obtain the first solutions with optimal time query and $O(nlo{g}^{O(1)}n)$ space, where $n$ is the length of the indexed string. We show that our techniques for substring range reporting generalize to emph{substring range counting} and emph{substring range emptiness} variants. We also obtain non-trivial time-space trade-offs for these problems. {itemize} Our bounds for substring range reporting are based on a novel combination of suffix trees and range reporting data structures. The reductions are simple and general and may apply to other combinations of string indexing with range reporting.

Recommendations

• Substring range reporting
• String range matching
• Reporting consecutive substring occurrences under bounded gap constraints
• Reporting consecutive substring occurrences under bounded gap constraints
• Position-Restricted Substring Searching
• Sorted range reporting
• Shared-constraint range reporting
• Substring compression problems
• String matching bounds via coding

Cites work

• Algorithms on Strings, Trees and Sequences
• Errata for ``Faster index for property matching
• Faster index for property matching
• Filtering Search: A New Approach to Query-Answering
• Finding patterns in given intervals
• scientific article; zbMATH DE number 6146456 (Why is no real title available?)
• Improved data structures for the orthogonal range successor problem
• Indexing factors with gaps
• On dynamic range reporting in one dimension
• On the sorting-complexity of suffix tree construction
• Optimal prefix and suffix queries on texts
• Optimal static range reporting in one dimension
• Position-Restricted Substring Searching
• Property matching and weighted matching
• Range non-overlapping indexing
• Rank and select revisited and extended
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Time-space trade-offs for predecessor search

Cited in

(13)

• Position-restricted substring searching over small alphabets
• Improved and extended locating functionality on compressed suffix arrays
• On position restricted substring searching in succinct space
• Generalized substring compression
• Simple and efficient LZW-compressed multiple pattern matching
• Orthogonal range searching for text indexing
• Document retrieval with one wildcard
• Reporting consecutive substring occurrences under bounded gap constraints
• Reporting consecutive substring occurrences under bounded gap constraints
• Less space: indexing for queries with wildcards
• Position-Restricted Substring Searching
• String range matching
• Substring range reporting

This page was built for publication: Substring Range Reporting

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