Error-correcting data structures

DOI10.1137/110834949MaRDI QIDQ2839172zbMATH OpenOpenAlexFDO

Authors Victor Chen, Elena Grigorescu, Ronald de Wolf

Publication date 4 July 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0802.1471

zbMATH Keywords

data structuresfault-toleranceerror-correcting codesmembership problemlocally decodable codespolynomial evaluation

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Bounds on codes (94B65)

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
• Theory of Cryptography

Cited in

(7)

• Efficient and error-correcting data structures for membership and polynomial evaluation
• Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes
• A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
• scientific article; zbMATH DE number 1507280 (Why is no real title available?)
• Theory of Cryptography
• Error-correcting data structures
• Resilient dynamic programming

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)