Linear batch codes

DOI10.1007/978-3-319-17296-5_26MaRDI QIDQ3460471zbMATH OpenOpenAlexFDO

Authors Helger Lipmaa, Vitaly Skachek

Publication date 7 January 2016

Published in Coding Theory and Applications (Search for Journal in Brave)

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

zbMATH Keywords

batch codescomputationally-private information retrievaldistributed storageerror-correcting codesload balancing

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Linear codes (general theory) (94B05) Other types of codes (94B60)

Abstract: In an application, where a client wants to obtain many elements from a large database, it is often desirable to have some load balancing. Batch codes (introduced by Ishai et al. in STOC 2004) make it possible to do exactly that: the large database is divided between many servers, so that the client has to only make a small number of queries to every server to obtain sufficient information to reconstruct all desired elements. Other important parameters of the batch codes are total storage and the number of servers. Batch codes also have applications in cryptography (namely, in the construction of multi-query computationally-private information retrieval protocols). In this work, we initiate the study of linear batch codes. These codes, in particular, are of potential use in distributed storage systems. We show that a generator matrix of a binary linear batch code is also a generator matrix of classical binary linear error-correcting code. This immediately yields that a variety of upper bounds, which were developed for error-correcting codes, are applicable also to binary linear batch codes. We also propose new methods to construct large linear batch codes from the smaller ones.

Recommendations

• Combinatorial batch codes
• Batch codes and their applications
• Batch codes from Hamming and Reed-Muller codes
• Relaxations of Hall's condition: optimal batch codes with multiple queries
• A survey of the study of combinatorial batch code

Cites work

• Batch codes and their applications
• Combinatorial batch codes
• Combinatorial batch codes and transversal matroids
• Combinatorial batch codes: a lower bound and optimal constructions
• Combinatorial batch codes: extremal problems under Hall-type conditions
• scientific article; zbMATH DE number 1261806 (Why is no real title available?)
• Index Coding With Side Information
• Introduction to Coding Theory
• Linear batch codes
• Network Coding for Distributed Storage Systems
• New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
• Optimal combinatorial batch codes based on block designs

Cited in

(4)

• Linear batch codes
• Batch codes and their applications
• Batch codes from Hamming and Reed-Muller codes
• Optimal possibly nonlinear 3-PIR codes of small size

This page was built for publication: Linear batch codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460471)