Encoding 2D range maximum queries

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

    Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
    Title of host publicationAlgorithms and Computation - 22nd International Symposium, ISAAC 2011, Proceedings
    Pages180-189
    Number of pages10
    DOIs
    StatePublished - 2011
    Event22nd International Symposium on Algorithms and Computation, ISAAC 2011 - Yokohama, Japan
    Duration: Dec 5 2011Dec 8 2011

    Publication series

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

    Other

    Other22nd International Symposium on Algorithms and Computation, ISAAC 2011
    CountryJapan
    CityYokohama
    Period12/5/1112/8/11

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Encoding 2D range maximum queries'. Together they form a unique fingerprint.

  • 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