Optimal combinatorial batch codes based on block designs

DOI10.1007/S10623-014-0007-9MaRDI QIDQ5963364zbMATH OpenOpenAlexFDO

Authors Natalia Silberstein, Anna Gál

Publication date 19 February 2016

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

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

zbMATH Keywords

affine planesbatch codestransversal designs

Mathematics Subject Classification ID

Other types of codes (94B60) Applications of design theory to circuits and networks (94C30)

Abstract: Batch codes, introduced by Ishai, Kushilevitz, Ostrovsky and Sahai, represent the distributed storage of an $n$-element data set on $m$ servers in such a way that any batch of $k$ data items can be retrieved by reading at most one (or more generally, $t$) items from each server, while keeping the total storage over $m$ servers equal to $N$. This paper considers a class of batch codes (for $t=1$), called combinatorial batch codes (CBC), where each server stores a subset of a database. A CBC is called optimal if the total storage $N$ is minimal for given $n,m$, and $k$. A $c$-uniform CBC is a combinatorial batch code where each item is stored in exactly $c$ servers. A $c$-uniform CBC is called optimal if its parameter $n$ has maximum value for given $m$ and $k$. Optimal $c$-uniform CBCs have been known only for $cin2,k-1,k-2$. In this paper we present new constructions of optimal CBCs in both the uniform and general settings, for values of the parameters where tight bounds have not been established previously. In the uniform setting, we provide constructions of two new families of optimal uniform codes with $csimsqrtk$. Our constructions are based on affine planes and transversal designs.

Recommendations

• Combinatorial batch codes: a lower bound and optimal constructions
• Combinatorial batch codes
• Optimal batch codes: many items or low retrieval requirement
• Combinatorial batch codes based on RTD(q-2, q)
• Multiset combinatorial batch codes

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
• scientific article; zbMATH DE number 1016456 (Why is no real title available?)
• scientific article; zbMATH DE number 3407723 (Why is no real title available?)
• Key distribution schemes using combinatorial designs to identify all traitors
• On an extremal hypergraph problem related to combinatorial batch codes
• Optimal batch codes: many items or low retrieval requirement
• Optimal combinatorial batch codes derived from dual systems
• Relaxations of Hall's condition: optimal batch codes with multiple queries
• Turán numbers and batch codes
• Upper bounds for constant-weight codes

Cited in

(25)

• Optimization models for complex recovery block schemes
• The results on optimal values of some combinatorial batch codes
• Constructions and bounds for batch codes with small parameters
• Multiset combinatorial batch codes
• Batch codes from affine Cartesian codes and quotient spaces
• Access balancing in storage systems by labeling partial Steiner systems
• Combinatorial batch codes
• Some optimal combinatorial batch codes with k=5
• Erasure combinatorial batch codes based on nonadaptive group testing
• Derandomized construction of combinatorial batch codes
• Combinatorial batch codes based on RTD(q-2, q)
• A survey of the study of combinatorial batch code
• A class of combinatorial batch code based on the p construction
• MaxMinSum Steiner systems for access balancing in distributed storage
• Linear batch codes
• Combinatorial batch codes: a lower bound and optimal constructions
• A special kind of combinatorial batch codes
• Batch codes from Hamming and Reed-Muller codes
• Combinatorial batch codes and transversal matroids
• On the maximum double independence number of Steiner triple systems
• Design of extended dense coding protocol strategy based on combinatorial optimization
• Optimal batch codes: many items or low retrieval requirement
• Resolutions for an infinite family of Bose triple systems
• Bounds on data limits for all-to-all comparison from combinatorial designs
• On generalized combinatorial batch codes

This page was built for publication: Optimal combinatorial batch codes based on block designs

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