BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260823T235941Z
UID:Seminar-networks-1135@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Giorgos Christodoulou:MAILTO:G.Christodoulou@liverpool.ac.uk
DTSTART:20210617T120000
DTEND:20210617T130000
SUMMARY:Networks and Distributed Computing Series
DESCRIPTION:Sebastian Wild: Hypersuccinct Trees\n\nThis 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).\n\nI will present our analyses of subtree distributions and give some context about their applications in data structures and compression.\n\nTree 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)$.\nWhile 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.\n\nBased on joint work with\nJ. Ian Munro, Patrick K. Nicholson, and Louisa Seelbach Benkner\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1135
LOCATION:
END:VEVENT
END:VCALENDAR