Encoding 2D range maximum queries

DOI10.1016/j.tcs.2015.10.012zbMath1331.68060arXiv1109.2885OpenAlexW1488801354MaRDI QIDQ897899

Mordecai J. Golin, Srinivasa Rao Satti, Danny Krizanc, John Iacono, Rajeev Raman, Sunil M. Shende, S. Srinivasa Rao

Publication date: 8 December 2015

Published in: Theoretical Computer Science, Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

encoding modelindexing modelCartesian treeseffective entropyrange maximum queries

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items

Two dimensional range minimum queries and Fibonacci lattices, Space efficient data structures for nearest larger neighbor, Simultaneous encodings for range and next/previous larger/smaller value queries, Encoding two-dimensional range top-\(k\) queries, Range Minimum Query Indexes in Higher Dimensions, Encoding Nearest Larger Values, Space Efficient Data Structures for Nearest Larger Neighbor, Encoding nearest larger values, The effective entropy of next/previous larger/smaller value queries, A simple linear-space data structure for constant-time range minimum query, Linear-space data structures for range mode query in arrays, Unnamed Item, An Encoding for Order-Preserving Matching., Orthogonal Range Searching for Text Indexing, Succinct Representations of Ordinal Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On space efficient two dimensional range minimum data structures
• Representing trees of higher degree
• A simple optimal representation for balanced parentheses
• Compressed suffix trees with full functionality
• Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
• The Spatial Complexity of Oblivious k-Probe Hash Functions
• Two-Dimensional Range Minimum Queries
• A Uniform Approach Towards Succinct Representation of Trees
• Indexing compressed text
• On Cartesian Trees and Range Minimum Queries
• A unifying look at data structures
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching