Entropy-bounded representation of point grids
From MaRDI portal
Publication:390358
DOI10.1016/j.comgeo.2013.08.002zbMath1280.65024MaRDI QIDQ390358
Travis Gagie, Gonzalo Navarro, Arash Farzan
Publication date: 8 January 2014
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.comgeo.2013.08.002
complexity; compressed data structures; range queries; range counting; geometric grids; point selection queries; range reporting
65D18: Numerical aspects of computer graphics, image analysis, and computational geometry
65Y20: Complexity and performance of numerical algorithms
Related Items
Compact and succinct data structures for multidimensional orthogonal range searching, The range 1 query (R1Q) problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimal indexes for sparse bit vectors
- Log-logarithmic worst-case range queries are possible in space theta(N)
- Compressed data structures: Dictionaries and data-aware measures
- Optimal lower bounds for rank and select indexes
- Low Redundancy in Static Dictionaries with Constant Query Time
- Time-space trade-offs for predecessor search
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Entropy-Bounded Representation of Point Grids
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Lower bounds for orthogonal range searching: I. The reporting case
- On the Redundancy of Succinct Data Structures
- On the Size of Succinct Indices
- Filtering Search: A New Approach to Query-Answering
- Recursive Star-Tree Parallel Data Structure
- Succinct indexable dictionaries with applications to encoding k -ary trees, prefix sums and multisets
- Practical Entropy-Compressed Rank/Select Dictionary
- Space efficient dynamic orthogonal range reporting
- More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
- Orthogonal range searching on the RAM, revisited
- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting
