Range minimum query indexes in higher dimensions

Pooya Davoodi, John Iacono, Gad M. Landau, Moshe Lewenstein

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    Range minimum queries (RMQs) are essential in many algorithmic procedures. The problem is to prepare a data structure on an array to allow for fast subsequent queries that find the minimum within a range in the array. We study the problem of designing indexing RMQ data structures which only require sub-linear space and access to the input array while querying. The RMQ problem in one-dimensional arrays is well understood with known indexing data structures achieving optimal space and query time. The two-dimensional indexing RMQ data structures have received the attention of researchers recently. There are also several solutions for the RMQ problem in higher dimensions. Yuan and Atallah [SODA’10] designed a brilliant data structure of size O(N) which supports RMQs in a multi-dimensional array of size N in constant time for a constant number of dimensions. In this paper we consider the problem of designing indexing data structures for RMQs in higher dimensions. We design a data structure of size O(N) bits that supports RMQs in constant time for a constant number of dimensions. We also show how to obtain trade-offs between the space of indexing data structures and their query time.

    Original languageEnglish (US)
    Title of host publicationCombinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings
    EditorsUgo Vaccaro, Ely Porat, Ferdinando Cicalese
    PublisherSpringer Verlag
    Pages149-159
    Number of pages11
    ISBN (Print)9783319199283
    DOIs
    StatePublished - 2015
    Event26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015 - Ischia Island, Italy
    Duration: Jun 29 2015Jul 1 2015

    Publication series

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

    Other

    Other26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015
    CountryItaly
    CityIschia Island
    Period6/29/157/1/15

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Range minimum query indexes in higher dimensions'. Together they form a unique fingerprint.

    Cite this