TY - GEN
T1 - Lower bound for succinct range minimum query
AU - Liu, Mingmou
AU - Yu, Huacheng
N1 - Funding Information:
∗This research was supported by National Key R&D Program of China 2018YFB1003202 and the NSFC Nos. 61722207 and 61672275. †Part of the research was done when Mingmou Liu was visiting the Harvard University.
Publisher Copyright:
© 2020 ACM.
PY - 2020/6/8
Y1 - 2020/6/8
N2 - 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).
AB - 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).
KW - Cell-probe complexity
KW - Data structure
KW - Lower bound
KW - Range minimum query
UR - http://www.scopus.com/inward/record.url?scp=85086761821&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85086761821&partnerID=8YFLogxK
U2 - 10.1145/3357713.3384260
DO - 10.1145/3357713.3384260
M3 - Conference contribution
AN - SCOPUS:85086761821
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 1402
EP - 1415
BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
A2 - Makarychev, Konstantin
A2 - Makarychev, Yury
A2 - Tulsiani, Madhur
A2 - Kamath, Gautam
A2 - Chuzhoy, Julia
PB - Association for Computing Machinery
T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
Y2 - 22 June 2020 through 26 June 2020
ER -