Encoding 2D range maximum queries

DOI10.1007/978-3-642-25591-5_20zbMATH Open1331.68060arXiv1109.2885OpenAlexW1488801354MaRDI QIDQ897899FDOQ897899

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

Publication date: 8 December 2015

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

Abstract: We consider the emph{two-dimensional range maximum query (2D-RMQ)} problem: given an array $A$ of ordered values, to pre-process it so that we can find the position of the smallest element in the sub-matrix defined by a (user-specified) range of rows and range of columns. We focus on determining the emph{effective} entropy of 2D-RMQ, i.e., how many bits are needed to encode $A$ so that 2D-RMQ queries can be answered emph{without} access to $A$. We give tight upper and lower bounds on the expected effective entropy for the case when $A$ contains independent identically-distributed random values, and new upper and lower bounds for arbitrary $A$, for the case when $A$ contains few rows. The latter results improve upon previous upper and lower bounds by Brodal et al. (ESA 2010). In some cases we also give data structures whose space usage is close to the effective entropy and answer 2D-RMQ queries rapidly.

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

Recommendations

• Encoding 2D range maximum queries
• The Encoding Complexity of Two Dimensional Range Minimum Data Structures
• Encoding two-dimensional range top-\(k\) queries
• Encoding two-dimensional range top-\(k\) queries
• On space efficient two dimensional range minimum data structures

zbMATH Keywords

encoding modelindexing modelCartesian treeseffective entropyrange maximum queries

Mathematics Subject Classification ID

Data structures (68P05) 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)

Cites Work

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

Cited In (18)

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

This page was built for publication: Encoding 2D range maximum queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q897899)