Lower bound for succinct range minimum query

Mingmou Liu, Huacheng Yu

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

Abstract

Given an integer array A[1..n], the Range Minimum Query problem (RMQ) asks to preprocess A into a data structure, supporting RMQ queries: given a,bg [1,n], return the index ig[a,b] that minimizes A[i], i.e., argminig[a,b] A[i]. This problem has a classic solution using O(n) space and O(1) query time by Gabow, Bentley, Tarjan (STOC, 1984) and Harel, Tarjan (SICOMP, 1984). The best known data structure by Fischer, Heun (SICOMP, 2011) and Navarro, Sadakane (TALG, 2014) uses 2n+n/(logn/t)t+Õ(n3/4) bits and answers queries in O(t) time, assuming the word-size is w=(logn). In particular, it uses 2n+n/polylogn bits of space as long as the query time is a constant. In this paper, we prove the first lower bound for this problem, showing that 2n+n/polylogn space is necessary for constant query time. In general, we show that if the data structure has query time O(t), then it must use at least 2n+n/(logn)Õ(t2) space, in the cell-probe model with word-size w=(logn).

Original languageEnglish (US)
Title of host publicationSTOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
EditorsKonstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
PublisherAssociation for Computing Machinery
Pages1402-1415
Number of pages14
ISBN (Electronic)9781450369794
DOIs
StatePublished - Jun 8 2020
Event52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States
Duration: Jun 22 2020Jun 26 2020

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
Country/TerritoryUnited States
CityChicago
Period6/22/206/26/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Cell-probe complexity
  • Data structure
  • Lower bound
  • Range minimum query

Fingerprint

Dive into the research topics of 'Lower bound for succinct range minimum query'. Together they form a unique fingerprint.

Cite this