Optimal succinct rank data structure via approximate nonnegative tensor decomposition
Optimal succinct rank data structure via approximate nonnegative tensor decomposition
复制标题
DOI：
10.1145/3313276.3316352
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Huacheng Yu
中科院分区：
文献类型：
--
作者：
Huacheng Yu
给定一个n位数组A，简洁的秩数据结构问题要求使用空间n+r位来构造一个数据结构，其中r≪n，支持形式为rank(u)=Σi=0u−1 A[i]的秩查询。在本文中，我们设计了一种新的简洁排名数据结构，其中 r=n/(logn)Ω(t)+n1−c ，对于某个常数 c>0 的查询时间为 O(t)，改进了之前由 Pǎtraşcu 提出的最著名的数据结构，该结构具有 r=n/(logn/t)Ω(t)+Õ(n3/4) 位冗余。对于 r>n1−c，我们的时空权衡与 Pǎtraşcu 和 Viola 的细胞探针下界相匹配，它断言 r 必须至少为 n/(logn)O(t)。此外，当在单元探针模型中实现数据结构时，可以避免n1−c位查找表，从而实现r=⌈n/(logn)Ω(t)⌉。它匹配整个参数范围的下限。在进行新的数据结构设计的过程中，我们在简洁的数据结构和近似非负张量分解之间建立了有趣的联系。我们的连接表明，对于特定问题，要构造一个节省空间的数据结构，只需通过（几个）非负 1 阶张量之和来近似特定张量就足够了。对于排序问题，我们显式地构造这样的近似，从而产生数据结构的显式构造。
Given an n-bit array A, the succinct rank data structure problem asks to construct a data structure using space n+r bits for r≪ n, supporting rank queries of form rank(u)=∑i=0u−1 A[i]. In this paper, we design a new succinct rank data structure with r=n/(logn)Ω(t)+n1−c and query time O(t) for some constant c>0, improving the previous best-known by Pǎtraşcu, which has r=n/(logn/t)Ω(t)+Õ(n3/4) bits of redundancy. For r>n1−c, our space-time tradeoff matches the cell-probe lower bound by Pǎtraşcu and Viola, which asserts that r must be at least n/(logn)O(t). Moreover, one can avoid an n1−c-bit lookup table when the data structure is implemented in the cell-probe model, achieving r=⌈ n/(logn)Ω(t)⌉. It matches the lower bound for the full range of parameters. En route to our new data structure design, we establish an interesting connection between succinct data structures and approximate nonnegative tensor decomposition. Our connection shows that for specific problems, to construct a space-efficient data structure, it suffices to approximate a particular tensor by a sum of (few) nonnegative rank-1 tensors. For the rank problem, we explicitly construct such an approximation, which yields an explicit construction of the data structure.