Encoding 2D range maximum queries

Mordecai Golin, John Iacono, Danny Krizanc, Rajeev Raman, Srinivasa Rao Satti, Sunil Shende

    Research output: Contribution to journalArticle

    Abstract

    We consider the two-dimensional range maximum query (2D-RMQ) problem: given an array containing elements from an ordered set, encode the array so that the position of the maximum element in any specified range of rows and range of columns can be found efficiently. We focus on determining the effective entropy of 2D-RMQ, i.e., how many bits are needed to encode an array so that 2D-RMQ queries can be answered without accessing the array. We give tight upper and lower bounds on the expected effective entropy for the case when A contains independent identically-distributed random values, and give new upper and lower bounds for the case when the array contains few rows. The latter results improve upon the upper and lower bounds by Brodal et al. [4]. We also give some efficient data structures for 2D-RMQ whose space usage is close to the effective entropy.

    Original languageEnglish (US)
    Pages (from-to)316-327
    Number of pages12
    JournalTheoretical Computer Science
    Volume609
    DOIs
    StatePublished - Jan 4 2016

    Keywords

    • Cartesian trees
    • Effective entropy
    • Encoding model
    • Indexing model
    • Range maximum queries

    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