Optimal combinatorial batch codes based on block designs

DOI10.1007/S10623-014-0007-9zbMATH Open1401.94255arXiv1312.5505OpenAlexW3112923198MaRDI QIDQ5963364FDOQ5963364

Anna Gál, Natalia Silberstein

Publication date: 19 February 2016

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

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.

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

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

zbMATH Keywords

transversal designsaffine planesbatch codes

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial batch codes: a lower bound and optimal constructions
• Combinatorial batch codes and transversal matroids
• Optimal batch codes: many items or low retrieval requirement
• Upper bounds for constant-weight codes
• Combinatorial batch codes
• Title not available (Why is that?)
• Batch codes and their applications
• Relaxations of Hall’s Condition: Optimal batch codes with multiple queries
• On an extremal hypergraph problem related to combinatorial batch codes
• Key distribution schemes using combinatorial designs to identify all traitors
• Turán numbers and batch codes

Cited In (14)

• Batch Codes from Hamming and Reed-M\"uller Codes
• Batch codes from affine Cartesian codes and quotient spaces
• Linear Batch Codes
• 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
• Optimization models for complex recovery block schemes
• Resolutions for an infinite family of Bose triple systems
• Multiset combinatorial batch codes
• Access balancing in storage systems by labeling partial Steiner systems
• MaxMinSum Steiner Systems for Access Balancing in Distributed Storage
• 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)