CS Events Monthly View

Abstract: 

Motivated by storage applications, we study the following data structure problem: An encoder wishes to store a collection of correlated variables X:=(X_1,X_2,...,X_n), using as little space as possible, such that each individual X_i can be recovered quickly with few (ideally constant) memory accesses.

In this talk, we focus on the natural case of compressing "Markov chains," i.e., storing a length-n walk on any (possibly directed) constant-size graph G. Denoting by k(G,n) the number of length-n walks on G, we show that there is a succinct data structure storing a walk using lg_2 k(G,n) + O(lg n) bits of space, such that each vertex along the walk can be decoded in constant time on a word-RAM. If the graph is strongly connected (e.g., undirected), the space can be improved to only lg_2 k(G,n) + 5 bits.

Joint work with Emanuele Viola and Omri Weinstein.