Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing

DOI10.1007/978-3-642-03367-4_9zbMath1253.68103OpenAlexW1495731517MaRDI QIDQ3183444

Pat Morin, Prosenjit Bose, Meng He, Anil Maheshwari

Publication date: 20 October 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-642-03367-4_9

Mathematics Subject Classification ID

Searching and sorting (68P10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (28)

Succinct indices for path minimum, with applications ⋮ Two dimensional range minimum queries and Fibonacci lattices ⋮ Succinct encodings for families of interval graphs ⋮ On finding the Adams consensus tree ⋮ Compact binary relation representations with rich functionality ⋮ Space efficient data structures for dynamic orthogonal range counting ⋮ Entropy-bounded representation of point grids ⋮ Compressed indexes for text with wildcards ⋮ Space-efficient data-analysis queries on grids ⋮ Longest Common Prefix with Mismatches ⋮ Improved data structures for the orthogonal range successor problem ⋮ Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number ⋮ Succinct permutation graphs ⋮ New algorithms on wavelet trees and applications to information retrieval ⋮ Unnamed Item ⋮ Wavelet trees for all ⋮ Fast relative Lempel-Ziv self-index for similar sequences ⋮ Path queries on functions ⋮ Succincter Text Indexing with Wildcards ⋮ Substring Range Reporting ⋮ \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity ⋮ Substring range reporting ⋮ Spaces, Trees, and Colors ⋮ Compact and succinct data structures for multidimensional orthogonal range searching ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Succinct and Implicit Data Structures for Computational Geometry ⋮ Orthogonal Range Searching for Text Indexing ⋮ Array Range Queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Orthogonal range searching in linear and almost-linear space
• Planar stage graphs: Characterizations and applications
• Adaptive searching in succinctly encoded binary relations and tree-structured documents
• Rank and select revisited and extended
• Succinct ordinal trees with level-ancestor queries
• Compressed representations of sequences and full-text indexes
• Efficient data structures for range searching on a grid
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets

This page was built for publication: Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing