Orthogonal Range Searching for Text Indexing
From MaRDI portal
Publication:2848980
DOI10.1007/978-3-642-40273-9_18zbMath1394.68099arXiv1306.0615OpenAlexW1804980550MaRDI QIDQ2848980
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
Related Items (11)
Document retrieval with one wildcard ⋮ Less space: indexing for queries with wildcards ⋮ Fast String Dictionary Lookup with One Error ⋮ Two-dimensional range successor in optimal time and almost linear space ⋮ Time-space trade-offs for Lempel-Ziv compressed indexing ⋮ Unnamed Item ⋮ Fully Dynamic No-Back-Edge-Traversal Forest via 2D-Range Queries ⋮ Generalized substring compression ⋮ Spaces, Trees, and Colors ⋮ A linear-space data structure for range-LCP queries in poly-logarithmic time ⋮ Suffix trays and suffix trists: structures for faster text indexing
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Compressed property suffix trees
- On compressing and indexing repetitive sequences
- Cross-document pattern matching
- Indexing permutations for binary strings
- Improved algorithms for the range next value problem and applications
- Fast index for approximate string matching
- Improved data structures for the orthogonal range successor problem
- A linear size index for approximate pattern matching
- On space efficient two dimensional range minimum data structures
- Scaled and permuted string matching
- Encoding 2D range maximum queries
- Succinct data structures for flexible text retrieval systems
- Property matching and weighted matching
- Let sleeping files lie: Pattern matching in Z-compressed files.
- Errata for ``Faster index for property matching
- Fast string matching with k differences
- Preserving order in a forest in less than logarithmic time and linear space
- String matching in Lempel-Ziv compressed strings
- Efficient text fingerprinting via Parikh mapping
- Log-logarithmic worst-case range queries are possible in space theta(N)
- On-line construction of suffix trees
- Parameterized pattern matching: Algorithms and applications
- On position restricted substring searching in succinct space
- Faster index for property matching
- Indexing factors with gaps
- Stronger Lempel-Ziv based compressed text indexing
- Binary jumbled string matching for highly run-length compressible texts
- Multi-method dispatching
- A Faster Grammar-Based Self-index
- Forbidden Patterns
- Wavelet Trees for All
- Sorted Range Reporting
- Two Dimensional Range Minimum Queries and Fibonacci Lattices
- Succinct Representations of Binary Trees for Range Minimum Queries
- Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to Online Indexing
- Dynamic text and static pattern matching
- Compressed representations of sequences and full-text indexes
- Finding Patterns In Given Intervals
- Substring Range Reporting
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Dynamic Text Indexing under String Updates
- Suffix Arrays: A New Method for On-Line String Searches
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
- Self-Indexed Grammar-Based Compression
- Fast Algorithms for Finding Nearest Common Ancestors
- Linear work suffix array construction
- Lower bounds for orthogonal range searching: I. The reporting case
- Two-Dimensional Range Minimum Queries
- Finding Patterns in Given Intervals
- Position-Restricted Substring Searching
- Indexing compressed text
- The Property Suffix Tree with Dynamic Properties
- Dictionary matching and indexing with errors and don't cares
- Rank/select operations on large alphabets
- Range Non-overlapping Indexing and Successive List Indexing
- On Cartesian Trees and Range Minimum Queries
- A unifying look at data structures
- A Space-Economical Suffix Tree Construction Algorithm
- A universal algorithm for sequential data compression
- Algorithms on Strings, Trees and Sequences
- Membership in Constant Time and Almost-Minimum Space
- Using persistent data structures for adding range restrictions to searching problems
- A linear lower bound on index size for text retrieval
- Text Indexing and Dictionary Matching with One Error
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Space-Efficient Framework for Top-k String Retrieval Problems
- Sparse Suffix Tree Construction in Small Space
- Orthogonal range searching on the RAM, revisited
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Function Matching
- On the sorting-complexity of suffix tree construction
- Range LCP
This page was built for publication: Orthogonal Range Searching for Text Indexing