Combinatorial batch codes: A lower bound and optimal constructions

Srimanta Bhattacharya; Sushmita Ruj; Bimal Roy

doi:10.3934/amc.2012.6.165

Article Contents

2012, Volume 6, Issue 2: 165-174. Doi: 10.3934/amc.2012.6.165

This issue Previous Article Codes on planar Tanner graphs Next Article On some classes of constacyclic codes over polynomial residue rings

Combinatorial batch codes: A lower bound and optimal constructions

1.
Applied Statistics Unit, Indian Statistical Institute, 203 B T Road, Kolkata 700 108
2.
School of Information Technology and Engineering, University of Ottawa, Ottawa, K1N6N5

Received: January 31, 2011

Revised: November 30, 2011

Published: April 2012

Abstract Related Papers Cited by

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:

Mathematics Subject Classification: Primary: 05D05, 68P30; Secondary: 68P20.

Citation:

Related Papers

Cited by

References

[1]	E. Agrell, A. Vardy and K. Zeger, Upper bounds for constant-weight codes, IEEE Trans. Inform. Theory, 46 (2000), 2373-2395.doi: 10.1109/18.887851.
[2]	B. Bollobas, "Combinatorics,'' Cambridge University Press, 1986.
[3]	A. E. Brouwer and T. Etzion, Some new distance-4 constant weight codes, Adv. Math. Commun., 5 (2011), 417-424.doi: 10.3934/amc.2011.5.417.
[4]	A. E. Brouwer, J. B. Shearer, N. J. A. Sloane and W. D. Smith, A new table of constant weight codes, IEEE Trans. Inform. Theory, 36 (1990), 1334-1380.doi: 10.1109/18.59932.
[5]	R. A. Brualdi, K. P. Kiernan, S. A. Meyer and M. W. Schroeder, Combinatorial batch codes and transversal matroids, Adv. Math. Commun., 4 (2010), 419-431.doi: 10.3934/amc.2010.4.419.
[6]	R. A. Brualdi, K. P. Kiernan, S. A. Meyer and M. W. Schroeder, Erratum: Combinatorial batch codes and transversal matriods, Adv. Math. Commun., 4 (2010), 597-597.doi: 10.3934/amc.2010.4.597.
[7]	C. Bujtás and Z. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes, 12 (2011), 11-23.
[8]	C. Bujtás and Z. Tuza, Optimal batch codes: many items or low retrieval requirement, Adv. Math. Commnun., 5 (2011), 529-541.doi: 10.3934/amc.2011.5.529.
[9]	R. L. Graham and N. J. A. Sloane, Lower bounds for constant weight codes, IEEE Trans. Inform. Theory, 26 (1980), 37-43.doi: 10.1109/TIT.1980.1056141.
[10]	W. C. Huffman and V. Pless, "Fundamentals of Error-Correcting Codes,'' Cambridge University Press, 2003.
[11]	Y. Ishai, E. Kushilevitz, R. Ostrovsky and A. Sahai, Batch codes and their applications, in "Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing,'' 36 (2004), 262-271.doi: 10.1145/1007352.1007396.
[12]	T. Klove, A lower bound for $A(n, 4, w)$, IEEE Trans. Inform. Theory, 27 (1981), 257-258.doi: 10.1109/TIT.1981.1056318.
[13]	M. B. Patterson, D. R. Stinson and R. Wei, Combinatorial batch codes, Adv. Math. Commun., 3 (2009), 13-27.doi: 10.3934/amc.2009.3.13.
[14]	D. H. Smith, L. A. Hughes and S. Perkins, A new table of constant weight codes of length greater than $28$, Electr. J. Combin., 13 (2006), Article A2.
[15]	C. L. M. Van Pul and T. Etzion, New lower bounds for constant weight codes, IEEE Trans. Inform. Theory, 35 (1989), 1324-1329.doi: 10.1109/18.45293.