Munro, J Ian and Wild, Sebastian 
ORCID: 0000-0002-6061-9177
(2019)
Entropy Trees and Range-Minimum Queries In Optimal Average-Case Space.
[Report]
|
Text
1903.02533v1.pdf - Submitted version Download (683kB) | Preview |
Abstract
The range-minimum query (RMQ) problem is a fundamental data structuring task with numerous applications. Despite the fact that succinct solutions with worst-case optimal $2n+o(n)$ bits of space and constant query time are known, it has been unknown whether such a data structure can be made adaptive to the reduced entropy of random inputs (Davoodi et al. 2014). We construct a succinct data structure with the optimal $1.736n+o(n)$ bits of space on average for random RMQ instances, settling this open problem. Our solution relies on a compressed data structure for binary trees that is of independent interest. It can store a (static) binary search tree generated by random insertions in asymptotically optimal expected space and supports many queries in constant time. Using an instance-optimal encoding of subtrees, we furthermore obtain a "hyper-succinct" data structure for binary trees that improves upon the ultra-succinct representation of Jansson, Sadakane and Sung (2012).
| Item Type: | Report |
|---|---|
| Uncontrolled Keywords: | cs.DS, cs.DS |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 15 Aug 2019 14:39 |
| Last Modified: | 19 Jan 2023 00:29 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3051855 |
Share
Share
