Error-correcting data structures
From MaRDI portal
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. 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 object. 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.
Recommendations
- Error-correcting data structures
- Error correction for massive datasets
- Error-correcting codes for byte-organized memory systems
- scientific article; zbMATH DE number 3172224
- Error-correcting codes
- scientific article; zbMATH DE number 919489
- Perfect error-correcting databases
- Error correction in the bounded storage model
Cited in
(7)- Efficient and error-correcting data structures for membership and polynomial evaluation
- Error-correcting keys in relational databases
- Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
- Resilient dynamic programming
- Error-correcting data structures
- Error correction in the bounded storage model
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
This page was built for publication: Error-correcting data structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2839172)