Encoding 2D range maximum queries

Mordecai Golin; John Iacono; Danny Krizanc; Rajeev Raman; S. Srinivasa Rao

doi:10.1007/978-3-642-25591-5_20

Encoding 2D range maximum queries

Mordecai Golin, John Iacono, Danny Krizanc, Rajeev Raman, S. Srinivasa Rao

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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.

Original language	English (US)
Title of host publication	Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
Pages	180-189
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-25591-5_20
State	Published - 2011
Event	22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan Duration: Dec 5 2011 → Dec 8 2011

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	7074 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	22nd International Symposium on Algorithms and Computation, ISAAC 2011
Country/Territory	Japan
City	Yokohama
Period	12/5/11 → 12/8/11

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

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

Cite this

Golin, M., Iacono, J., Krizanc, D., Raman, R., & Rao, S. S. (2011). Encoding 2D range maximum queries. In Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings (pp. 180-189). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7074 LNCS). https://doi.org/10.1007/978-3-642-25591-5_20

Encoding 2D range maximum queries. / Golin, Mordecai; Iacono, John; Krizanc, Danny et al.
Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. 2011. p. 180-189 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7074 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Golin, M, Iacono, J, Krizanc, D, Raman, R & Rao, SS 2011, Encoding 2D range maximum queries. in Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7074 LNCS, pp. 180-189, 22nd International Symposium on Algorithms and Computation, ISAAC 2011, Yokohama, Japan, 12/5/11. https://doi.org/10.1007/978-3-642-25591-5_20

@inproceedings{1184f3f7bbf843b995e75a6e3954fba8,

title = "Encoding 2D range maximum queries",

abstract = "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.",

author = "Mordecai Golin and John Iacono and Danny Krizanc and Rajeev Raman and Rao, {S. Srinivasa}",

year = "2011",

doi = "10.1007/978-3-642-25591-5_20",

language = "English (US)",

isbn = "9783642255908",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "180--189",

booktitle = "Algorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings",

note = "22nd International Symposium on Algorithms and Computation, ISAAC 2011 ; Conference date: 05-12-2011 Through 08-12-2011",

}

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 -

Encoding 2D range maximum queries

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this