Skip to Main content Skip to Navigation
Conference papers

Error-Correcting Data Structures

Abstract : We study data structures in the presence of adversarial noise. We want to encode a given ob ject in a succinct data structure that enables us to efficiently answer specific queries about the ob ject, even if the data structure has been corrupted by a constant fraction of errors. This new model is the common generalization of (static) data structures and locally decodable error-correcting codes. The main issue is the tradeoff between the space used by the data structure and the time (number of probes) needed to answer a query about the encoded ob ject. 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 error-correcting data structures for the Membership problem (where we want to store subsets of size s from a universe of size n) is closely related to the optimal length of locally decodable codes for s-bit strings.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00359651
Contributor : Publications Loria <>
Submitted on : Monday, February 9, 2009 - 10:06:06 AM
Last modification on : Wednesday, December 20, 2017 - 5:42:07 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 8:29:51 PM

Files

ecdata-stacs_new.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00359651, version 1

Collections

Citation

Ronald de Wolf. Error-Correcting Data Structures. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.313-324. ⟨inria-00359651⟩

Share

Metrics

Record views

114

Files downloads

226