How to Store a Random Walk-猫眼课题宝

DOI：

10.1137/1.9781611975994.26

发表时间：

2019-07

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Emanuele Viola;Omri Weinstein;Huacheng Yu

在存储应用程序的激励中，我们研究以下数据结构问题：编码器希望存储共同分布的文件集合$ \ overline {x} {x}：=（x_1，x_2，\ ldots，x_n），x_n）\ sim \ mu $， \ emph {correcated}（$ h_ \ mu（\ overline {x}）\ ll \ sum_i h_ \ mu（x_i）$），使用尽可能少的（预期）内存，使每个单独的文件$ x_i $可以在很少（理想的常数）内存访问的情况下快速恢复。对于独立的随机文件，\ pat（focs'08）的戏剧性结果，随后由Dodis，\ pat和Thorup（stoc'10）结果表明，可以仅使用a即可存储$ \ overline {x} $ \ emph {constant}除信息理论最小空间以外的额外位数，同时在恒定时间内解码每个$ x_i $。但是，在文件相关的（现实）情况下，已知的结果要弱得多，需要至少$ \ omega（n/poly \ lg n）$额外的位置，即使对于“简单的”联合分布$，也需要额外的位置。 \ mu $。我们专注于压缩\ emph {Markov链}的自然案例，即，在任何（可能有指示的）图$ g $上存储长度-N $随机步行。用$ \ kappa（g，n）$表示$ g $的长度 - $ n $ walks的数量，我们表明有一个简洁的数据结构，使用$ \ lg_2 \ kappa（g，n） +，存储随机步行o（\ lg n）$ lats的空间，使步行沿线的任何顶点都可以在单词-RAM上以$ o（1）$时间进行解码。对于匹配\ emph {point-wise}步行的最佳空间的更艰巨任务，即经验熵$ \ sum_ {i = 1}^{n-1} {n-1} \ lg（deg（v_i））$，我们以$ o（1）$ $ o（\ lg n）$解码时间的价格呈现数据结构，并证明对此的任何改进都会改善关于长期词典问题的解决方案。我们的所有数据结构都支持\ emph {Online}问题的版本，并具有恒定的更新和查询时间。

Motivated by storage applications, we study the following data structure problem: An encoder wishes to store a collection of jointly-distributed files $\overline{X}:=(X_1,X_2,\ldots, X_n) \sim \mu$ which are \emph{correlated} ($H_\mu(\overline{X}) \ll \sum_i H_\mu(X_i)$), using as little (expected) memory as possible, such that each individual file $X_i$ can be recovered quickly with few (ideally constant) memory accesses. In the case of independent random files, a dramatic result by \Pat (FOCS'08) and subsequently by Dodis, \Pat and Thorup (STOC'10) shows that it is possible to store $\overline{X}$ using just a \emph{constant} number of extra bits beyond the information-theoretic minimum space, while at the same time decoding each $X_i$ in constant time. However, in the (realistic) case where the files are correlated, much weaker results are known, requiring at least $\Omega(n/poly\lg n)$ extra bits for constant decoding time, even for "simple" joint distributions $\mu$. We focus on the natural case of compressing\emph{Markov chains}, i.e., storing a length-$n$ random walk on any (possibly directed) graph $G$. Denoting by $\kappa(G,n)$ the number of length-$n$ walks on $G$, we show that there is a succinct data structure storing a random walk using $\lg_2 \kappa(G,n) + O(\lg n)$ bits of space, such that any vertex along the walk can be decoded in $O(1)$ time on a word-RAM. For the harder task of matching the \emph{point-wise} optimal space of the walk, i.e., the empirical entropy $\sum_{i=1}^{n-1} \lg (deg(v_i))$, we present a data structure with $O(1)$ extra bits at the price of $O(\lg n)$ decoding time, and show that any improvement on this would lead to an improved solution on the long-standing Dictionary problem. All of our data structures support the \emph{online} version of the problem with constant update and query time.

How to Store a Random Walk

文献摘要

相似文献