Hypersuccinct Trees

17^th June 2021, 12:00
Sebastian Wild

Abstract

This talk covers some recent successes of taking a beyond-worst-case perspective in space-efficient data structures. More specifically, we show how tree covering, a method invented for succinct tree data structures, yields a simple universal source code for many random sources of binary or ordinal (a.k.a. plane) trees. Unlike other such codes, tree covering can be augmented to a data structure that supports a wide range of queries on the stored tree (without decompressing it first).

I will present our analyses of subtree distributions and give some context about their applications in data structures and compression.

Tree covering decomposes a (binary or ordinal a.k.a. plane) tree into $O(n/B)$ micro trees (connected subtrees) of $O(B)$ nodes each, with restricted connections between micro trees; our code uses $B=\Theta(\log n)$.
While distributions of “fringe subtrees” (subtrees containing all descendants of one node) are often well understood, the challenge in the analysis here is to bound the entropy of all micro-tree shapes, including the non-fringe ones.

Based on joint work with
J. Ian Munro, Patrick K. Nicholson, and Louisa Seelbach Benkner

Additional Materials

• https://arxiv.org/abs/2104.13457