Combinatorial batch codes: A lower bound and optimal constructions

Pages: 165 - 174, Volume 6, Issue 2, May 2012

doi:10.3934/amc.2012.6.165       Abstract        References        Full Text (345.4K)       Related Articles

Srimanta Bhattacharya - Applied Statistics Unit, Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India (email)
Sushmita Ruj - School of Information Technology and Engineering, University of Ottawa, Ottawa, K1N6N5, Canada (email)
Bimal Roy - Applied Statistics Unit, Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India (email)

Abstract: Batch codes, introduced by Ishai et al. in [11], are methods for solving the following data storage problem: $n$ data items are to be stored in $m$ servers in such a way that any $k$ of the $n$ items can be retrieved by reading at most $t$ items from each server, and that the total number of items stored in $m$ servers is $N$. A combinatorial batch code (CBC) is a batch code where each data item is stored without change, i.e., each stored data item is a copy of one of the $n$ data items.
    One of the basic yet challenging problems is to find optimal CBCs, i.e., CBCs for which total storage ($N$) is minimal for given values of $n$, $m$, $k$, and $t$. In [13], Paterson et al. exclusively studied CBCs and gave constructions of some optimal CBCs.
    In this article, we give a lower bound on the total storage ($N$) for CBCs. We give explicit construction of optimal CBCs for a range of values of $n$. For a different range of values of $n$, we give explicit construction of optimal and almost optimal CBCs. Our results partly settle an open problem of [13].

Keywords:  Combinatorial batch codes, Hall's theorem, binary constant weight codes.
Mathematics Subject Classification:  Primary: 05D05, 68P30; Secondary: 68P20.

Received: February 2011;      Revised: December 2011;      Published: April 2012.

 References