Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913873110499328 |
|---|---|
| author | Jo, Seungbum Kim, Geunho |
| author_facet | Jo, Seungbum Kim, Geunho |
| contents | Given an array of size $n$ from a total order, we consider the problem of constructing a data structure that supports various queries (range minimum/maximum queries with their variants and next/previous larger/smaller queries) efficiently. In the encoding model (i.e., the queries can be answered without the input array), we propose a $(3.701n + o(n))$-bit data structure, which supports all these queries in $O(\log^{(\ell)}n)$ time, for any positive constant integer $\ell$ (here, $\log^{(1)} n = \log n$, and for $\ell > 1$, $\log^{(\ell)} n = \log ({\log^{(\ell-1)}} n)$). The space of our data structure matches the current best upper bound of Tsur (Inf. Process. Lett., 2019), which does not support the queries efficiently. Also, we show that at least $3.16n-Θ(\log n)$ bits are necessary for answering all the queries. Our result is obtained by generalizing Gawrychowski and Nicholson's $(3n - Θ(\log n))$-bit lower bound (ICALP, 15) for answering range minimum and maximum queries on a permutation of size $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_00158 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries Jo, Seungbum Kim, Geunho Data Structures and Algorithms Given an array of size $n$ from a total order, we consider the problem of constructing a data structure that supports various queries (range minimum/maximum queries with their variants and next/previous larger/smaller queries) efficiently. In the encoding model (i.e., the queries can be answered without the input array), we propose a $(3.701n + o(n))$-bit data structure, which supports all these queries in $O(\log^{(\ell)}n)$ time, for any positive constant integer $\ell$ (here, $\log^{(1)} n = \log n$, and for $\ell > 1$, $\log^{(\ell)} n = \log ({\log^{(\ell-1)}} n)$). The space of our data structure matches the current best upper bound of Tsur (Inf. Process. Lett., 2019), which does not support the queries efficiently. Also, we show that at least $3.16n-Θ(\log n)$ bits are necessary for answering all the queries. Our result is obtained by generalizing Gawrychowski and Nicholson's $(3n - Θ(\log n))$-bit lower bound (ICALP, 15) for answering range minimum and maximum queries on a permutation of size $n$. |
| title | Space-efficient Data Structure for Next/Previous Larger/Smaller Value Queries |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2209.00158 |