Entropy Trees: Range-Minimum Queries In Optimal Average-Case Space

13^th November 2019, 14:00
Sebastian Wild
University of Liverpool

Abstract

I will present some basics of succinct (=space-efficient) data structures and a recent result in the area of distribution-succinct data structures, i.e., data structures that have (asymptotically) optimal expected space usage (as opposed to only optimal worst case) for a certain data-structuring task.

More specifically, I will talk about (and define) the range-minimum query (RMQ) problem, 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.