 Author
 Year
 2013
 Title
 Errorcorrecting data structures
 Journal
 SIAM Journal on Computing
 Volume  Issue number
 42  1
 Pages (fromto)
 84111
 Document type
 Article
 Faculty
 Interfacultary Research Institutes
 Institute
 Institute for Logic, Language and Computation (ILLC)
 Abstract

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 queryanswering time, measured by the number of bitprobes to the (possibly corrupted) representation. The main issue is the tradeoff between these two. This new model is the common generalization of (static) data structures and locally decodable errorcorrecting codes (LDCs). We prove a number of upper and lower bounds on various natural errorcorrecting data structure problems. In particular, we show that the optimal length of $t$probe errorcorrecting 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 efficiently) is approximately the optimal length of $t$probe LDCs that encode strings of length $s$. It has been conjectured that LDCs with small $t$ must be superpolynomially long. This bad probesversuslength tradeoff carries over to errorcorrecting data structures for Membership and many other data structure problems. We then circumvent this problem by defining socalled relaxed errorcorrecting data structures, inspired by the notion of “relaxed locally decodable codes” developed in the PCP literature. Here the decoder is required to answer most queries correctly with high probability, and for the remaining queries the decoder with high probability either answers correctly or declares “don't know.” Furthermore, if there is no noise on the data structure, it answers all queries correctly with high probability. We obtain positive results for the following two data structure problems: (1) Membership. We construct a relaxed errorcorrecting data structure for this problem with length nearly linear in $s\log n$ that answers membership queries with $O(1)$ bitprobes. This nearly matches the asymptotically optimal parameters for the noiseless case: length $O(s\log n)$ and one bitprobe, due to Buhrman et al. (2) Univariate Polynomial Evaluation (namely, we want to store a univariate polynomial $g$ of degree $\deg(g)\leq s$ over the integers modulo $n$ such that evaluation queries can be answered efficiently; i.e., we can evaluate the output of $g$ on a given integer modulo $n$). We construct a relaxed errorcorrecting data structure for this problem with length nearly linear in $s\log n$ that answers evaluation queries with ${\mbox{polylog}}(s)\cdot\log^{1+o(1)}(n)$ bitprobes. This nearly matches the parameters of the best known noiseless construction due to Kedlaya and Umans.
 URL
 go to publisher's site
 Language
 English
 Permalink
 http://hdl.handle.net/11245/1.402486
Disclaimer/Complaints regulations
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.