NDLI: Error-Correcting Data Structures

Please wait, while we are loading the content...

Error-Correcting Data Structures

Content Provider	Hyper Articles en Ligne (HAL)
Author	de Wolf, Ronald
Copyright Year	2009
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 eﬃciently answer speciﬁc 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 tradeoﬀ 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.
Related Links	https://inria.hal.science/inria-00359651/file/ecdata-stacs_new.pdf
Conference Proceedings	26th International Symposium on Theoretical Aspects of Computer Science STACS 2009
Language	English
Publisher	HAL CCSD IBFI Schloss Dagstuhl
Publisher Date	2009-01-01
Access Restriction	Open
Subject Keyword	data structures error-correcting codes locally decodable codes membership
Content Type	Text
Resource Type	Conference Proceedings
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in