How to Store a Random Walk
Wednesday, September 25, 2019, 11:00am
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.
Speaker: Huacheng Yu
Huacheng Yu is an associate research scholar in the department of computer science at Princeton University. Prior to Princeton, he was a postdoc in the Theory of Computation group at Harvard University, after receiving his PhD from Stanford University in 2017.
Location : CoRE A 301
Rutgers/DIMACS Theory of Computing Seminar
Event Type: Seminar