Orthogonal range searching for text indexing

DOI10.1007/978-3-642-40273-9_18MaRDI QIDQ2848980zbMATH OpenOpenAlexFDO

Authors Moshe Lewenstein

Publication date 13 September 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data structures (68P05)

Abstract: Text indexing, the problem in which one desires to preprocess a (usually large) text for future (shorter) queries, has been researched ever since the suffix tree was invented in the early 70's. With textual data continuing to increase and with changes in the way it is accessed, new data structures and new algorithmic methods are continuously required. Therefore, text indexing is of utmost importance and is a very active research domain. Orthogonal range searching, classically associated with the computational geometry community, is one of the tools that has increasingly become important for various text indexing applications. Initially, in the mid 90's there were a couple of results recognizing this connection. In the last few years we have seen an increase in use of this method and are reaching a deeper understanding of the range searching uses for text indexing. In this monograph we survey some of these results.

Recommendations

• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Range Non-overlapping Indexing and Successive List Indexing
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Improved Dynamic Text Indexing

Cites work

• scientific article; zbMATH DE number 432808 (Why is no real title available?)
• scientific article; zbMATH DE number 1182924 (Why is no real title available?)
• scientific article; zbMATH DE number 2079421 (Why is no real title available?)
• scientific article; zbMATH DE number 2119724 (Why is no real title available?)
• scientific article; zbMATH DE number 1438578 (Why is no real title available?)
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• A Space-Economical Suffix Tree Construction Algorithm
• A faster grammar-based self-index
• A linear lower bound on index size for text retrieval
• A linear size index for approximate pattern matching
• A unifying look at data structures
• A universal algorithm for sequential data compression
• Algorithms on Strings, Trees and Sequences
• Binary jumbled string matching for highly run-length compressible texts
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Compressed property suffix trees
• Compressed representations of sequences and full-text indexes
• Cross-document pattern matching
• Data structures for range minimum queries in multidimensional arrays
• Dictionary matching and indexing with errors and don't cares
• Dynamic Text Indexing under String Updates
• Dynamic text and static pattern matching
• Dynamic weighted ancestors
• Efficient text fingerprinting via Parikh mapping
• Errata for ``Faster index for property matching
• Fast Algorithms for Finding Nearest Common Ancestors
• Fast index for approximate string matching
• Fast string matching with k differences
• Faster index for property matching
• Finding Patterns in Given Intervals
• Finding patterns in given intervals
• Forbidden patterns
• Function Matching
• Improved algorithms for the range next value problem and applications
• Improved data structures for the orthogonal range successor problem
• Indexing compressed text
• Indexing factors with gaps
• Indexing permutations for binary strings
• Let sleeping files lie: Pattern matching in Z-compressed files.
• Linear work suffix array construction
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Lower bounds for orthogonal range searching: I. The reporting case
• Managing unbounded-length keys in comparison-driven data structures with applications to online indexing
• Membership in Constant Time and Almost-Minimum Space
• Multi-method dispatching: a geometric approach with applications to string matching problems
• On Cartesian Trees and Range Minimum Queries
• On compressing and indexing repetitive sequences
• On position restricted substring searching in succinct space
• On space efficient two dimensional range minimum data structures
• On the sorting-complexity of suffix tree construction
• On-line construction of suffix trees
• Orthogonal range searching on the RAM, revisited
• Parameterized pattern matching: Algorithms and applications
• Persistent predecessor search and orthogonal point location on the word RAM
• Position-Restricted Substring Searching
• Preserving order in a forest in less than logarithmic time and linear space
• Property matching and weighted matching
• Range LCP
• Range Non-overlapping Indexing and Successive List Indexing
• Rank/select operations on large alphabets
• Scaled and permuted string matching
• Self-indexed grammar-based compression
• Sorted range reporting
• Space-Efficient Framework for Top-k String Retrieval Problems
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Sparse suffix tree construction in small space
• String matching in Lempel-Ziv compressed strings
• Stronger Lempel-Ziv based compressed text indexing
• Substring Range Reporting
• Substring compression problems
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Succinct data structures for flexible text retrieval systems
• Succinct representations of binary trees for range minimum queries
• Suffix Arrays: A New Method for On-Line String Searches
• THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
• Text Indexing and Dictionary Matching with One Error
• The Property Suffix Tree with Dynamic Properties
• Top-\(K\) color queries for document retrieval
• Two Dimensional Range Minimum Queries and Fibonacci Lattices
• Two-Dimensional Range Minimum Queries
• Using persistent data structures for adding range restrictions to searching problems
• Wavelet trees for all

Cited in

(11)

• Generalized substring compression
• Time-space trade-offs for Lempel-Ziv compressed indexing
• A linear-space data structure for range-LCP queries in poly-logarithmic time
• Document retrieval with one wildcard
• Fast string dictionary lookup with one error
• Two-dimensional range successor in optimal time and almost linear space
• Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
• scientific article; zbMATH DE number 7651193 (Why is no real title available?)
• Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
• Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries
• Less space: indexing for queries with wildcards

This page was built for publication: Orthogonal range searching for text indexing

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