ERROR-CORRECTING DATA STRUCTURES ∗
ERROR-CORRECTING DATA STRUCTURES ∗
复制标题
纠错数据结构*
DOI：
10.1137/110834949
复制
发表时间：
2013
影响因子：
1.6
通讯作者：
Ronald de Wolf
中科院分区：
文献类型：
--
作者：
Victor Chen;E. Grigorescu;Ronald de Wolf
我们在存在对抗噪声的情况下研究数据结构。我们想在简洁的数据结构中编码给定的对象，以使我们能够有效地回答有关对象的特定查询，即使数据结构已被恒定的错误损坏。我们根据数据结构的长度（其表示形式中的位数）和查询效应时间来衡量数据结构的效率，该数据结构以（可能损坏的）表示形式来衡量。主要问题是这两者之间的权衡。这个新模型是（静态）数据结构和局部可解释的误差校正代码（LDC）的共同概括。我们在各种自然误差校正数据结构问题上证明了许多上限和下限。特别是，我们表明，$ t $ - 探针校正错误的数据结构的最佳长度是会员问题（我们想从大小$ n $的宇宙中存储尺寸$ s $的子集，以便会员查询可以是回答有效...
We study data structures in the presence of adversarial noise. We want to encode a given object in a succinct data structure that enables us to efficiently answer specific queries about the object, even if the data structure has been corrupted by a constant fraction of errors. We measure the efficiency of a data structure in terms of its length (the number of bits in its representation) and query-answering time, measured by the number of bit-probes to the (possibly corrupted) representation. The main issue is the trade-off between these two. This new model is the common generalization of (static) data structures and locally decodable error-correcting codes (LDCs). We prove a number of upper and lower bounds on various natural error-correcting data structure problems. In particular, we show that the optimal length of $t$-probe error-correcting data structures for the Membership problem (where we want to store subsets of size $s$ from a universe of size $n$ such that membership queries can be answered effic...