Orthogonal range searching for text indexing
From MaRDI portal
Publication:2848980
DOI10.1007/978-3-642-40273-9_18zbMATH Open1394.68099arXiv1306.0615OpenAlexW1804980550MaRDI QIDQ2848980FDOQ2848980
Authors: Moshe Lewenstein 
Publication date: 13 September 2013
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1306.0615
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
- Algorithms on Strings, Trees and Sequences
- String matching in Lempel-Ziv compressed strings
- Preserving order in a forest in less than logarithmic time and linear space
- Stronger Lempel-Ziv based compressed text indexing
- Succinct representations of binary trees for range minimum queries
- Compressed representations of sequences and full-text indexes
- Linear work suffix array construction
- Indexing compressed text
- Dictionary matching and indexing with errors and don't cares
- On Cartesian Trees and Range Minimum Queries
- Title not available (Why is that?)
- Space-Efficient Framework for Top-k String Retrieval Problems
- Top-\(K\) color queries for document retrieval
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Property matching and weighted matching
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Text Indexing and Dictionary Matching with One Error
- A universal algorithm for sequential data compression
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Indexing factors with gaps
- Forbidden patterns
- Substring Range Reporting
- Suffix Arrays: A New Method for On-Line String Searches
- A Space-Economical Suffix Tree Construction Algorithm
- Orthogonal range searching on the RAM, revisited
- Succinct data structures for flexible text retrieval systems
- Using persistent data structures for adding range restrictions to searching problems
- Efficient text fingerprinting via Parikh mapping
- On-line construction of suffix trees
- Parameterized pattern matching: Algorithms and applications
- Faster index for property matching
- Sorted range reporting
- Substring compression problems
- Managing unbounded-length keys in comparison-driven data structures with applications to online indexing
- Dynamic weighted ancestors
- Dynamic text and static pattern matching
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Fast Algorithms for Finding Nearest Common Ancestors
- Two-Dimensional Range Minimum Queries
- Rank/select operations on large alphabets
- Range Non-overlapping Indexing and Successive List Indexing
- Compressed property suffix trees
- A unifying look at data structures
- On compressing and indexing repetitive sequences
- Cross-document pattern matching
- Title not available (Why is that?)
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Sparse suffix tree construction in small space
- Data structures for range minimum queries in multidimensional arrays
- On space efficient two dimensional range minimum data structures
- Scaled and permuted string matching
- Encoding 2D range maximum queries
- Errata for ``Faster index for property matching
- Improved data structures for the orthogonal range successor problem
- Binary jumbled string matching for highly run-length compressible texts
- Indexing permutations for binary strings
- Lower bounds for orthogonal range searching: I. The reporting case
- Self-indexed grammar-based compression
- The Property Suffix Tree with Dynamic Properties
- Title not available (Why is that?)
- Position-Restricted Substring Searching
- Membership in Constant Time and Almost-Minimum Space
- Fast index for approximate string matching
- Finding Patterns in Given Intervals
- On the sorting-complexity of suffix tree construction
- Finding patterns in given intervals
- Improved algorithms for the range next value problem and applications
- Persistent predecessor search and orthogonal point location on the word RAM
- A linear size index for approximate pattern matching
- Let sleeping files lie: Pattern matching in Z-compressed files.
- Fast string matching with k differences
- Function Matching
- THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
- A faster grammar-based self-index
- Wavelet trees for all
- Title not available (Why is that?)
- A linear lower bound on index size for text retrieval
- Dynamic Text Indexing under String Updates
- Title not available (Why is that?)
- On position restricted substring searching in succinct space
- Two Dimensional Range Minimum Queries and Fibonacci Lattices
- Multi-method dispatching: a geometric approach with applications to string matching problems
- Range LCP
Cited In (12)
- Title not available (Why is that?)
- A linear-space data structure for range-LCP queries in poly-logarithmic time
- Document retrieval with one wildcard
- Less space: indexing for queries with wildcards
- Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries
- 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
- Suffix trays and suffix trists: structures for faster text indexing
- Generalized substring compression
- Time-space trade-offs for Lempel-Ziv compressed indexing
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
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)
