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

transversal designsaffine planesbatch codes

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

• scientific article; zbMATH DE number 1016456 (Why is no real title available?)
• scientific article; zbMATH DE number 3407723 (Why is no real title available?)
• Batch codes and their applications
• Combinatorial batch codes
• Combinatorial batch codes and transversal matroids
• Combinatorial batch codes: a lower bound and optimal constructions
• 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

(24)

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

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)