TY - GEN

T1 - Encoding 2D range maximum queries

AU - Golin, Mordecai

AU - Iacono, John

AU - Krizanc, Danny

AU - Raman, Rajeev

AU - Rao, S. Srinivasa

PY - 2011

Y1 - 2011

N2 - We consider the 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 largest element in a (user-specified) range of rows and range of columns. We focus on determining the effective entropy of 2D-RMQ, i.e., how many bits are needed to encode A so that 2D-RMQ queries can be answered 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 upper and lower bounds by Brodal et al. (ESA 2010). We also give some efficient data structures for 2D-RMQ whose space usage is close to the effective entropy.

AB - We consider the 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 largest element in a (user-specified) range of rows and range of columns. We focus on determining the effective entropy of 2D-RMQ, i.e., how many bits are needed to encode A so that 2D-RMQ queries can be answered 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 upper and lower bounds by Brodal et al. (ESA 2010). We also give some efficient data structures for 2D-RMQ whose space usage is close to the effective entropy.

UR - http://www.scopus.com/inward/record.url?scp=84055200227&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84055200227&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-25591-5_20

DO - 10.1007/978-3-642-25591-5_20

M3 - Conference contribution

AN - SCOPUS:84055200227

SN - 9783642255908

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 180

EP - 189

BT - Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings

T2 - 22nd International Symposium on Algorithms and Computation, ISAAC 2011

Y2 - 5 December 2011 through 8 December 2011

ER -