May  2012, 6(2): 165-174. doi: 10.3934/amc.2012.6.165

Combinatorial batch codes: A lower bound and optimal constructions

1. 

Applied Statistics Unit, Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India, India

2. 

School of Information Technology and Engineering, University of Ottawa, Ottawa, K1N6N5, Canada

Received  February 2011 Revised  December 2011 Published  April 2012

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].
Citation: Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy. Combinatorial batch codes: A lower bound and optimal constructions. Advances in Mathematics of Communications, 2012, 6 (2) : 165-174. doi: 10.3934/amc.2012.6.165
References:
[1]

E. Agrell, A. Vardy and K. Zeger, Upper bounds for constant-weight codes,, IEEE Trans. Inform. Theory, 46 (2000), 2373.  doi: 10.1109/18.887851.  Google Scholar

[2]

B. Bollobas, "Combinatorics,'', Cambridge University Press, (1986).   Google Scholar

[3]

A. E. Brouwer and T. Etzion, Some new distance-4 constant weight codes,, Adv. Math. Commun., 5 (2011), 417.  doi: 10.3934/amc.2011.5.417.  Google Scholar

[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.  doi: 10.1109/18.59932.  Google Scholar

[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.  doi: 10.3934/amc.2010.4.419.  Google Scholar

[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.  doi: 10.3934/amc.2010.4.597.  Google Scholar

[7]

C. Bujtás and Z. Tuza, Optimal combinatorial batch codes derived from dual systems,, Miskolc Math. Notes, 12 (2011), 11.   Google Scholar

[8]

C. Bujtás and Z. Tuza, Optimal batch codes: many items or low retrieval requirement,, Adv. Math. Commnun., 5 (2011), 529.  doi: 10.3934/amc.2011.5.529.  Google Scholar

[9]

R. L. Graham and N. J. A. Sloane, Lower bounds for constant weight codes,, IEEE Trans. Inform. Theory, 26 (1980), 37.  doi: 10.1109/TIT.1980.1056141.  Google Scholar

[10]

W. C. Huffman and V. Pless, "Fundamentals of Error-Correcting Codes,'', Cambridge University Press, (2003).   Google Scholar

[11]

Y. Ishai, E. Kushilevitz, R. Ostrovsky and A. Sahai, Batch codes and their applications,, in, 36 (2004), 262.  doi: 10.1145/1007352.1007396.  Google Scholar

[12]

T. Klove, A lower bound for $A(n, 4, w)$,, IEEE Trans. Inform. Theory, 27 (1981), 257.  doi: 10.1109/TIT.1981.1056318.  Google Scholar

[13]

M. B. Patterson, D. R. Stinson and R. Wei, Combinatorial batch codes,, Adv. Math. Commun., 3 (2009), 13.  doi: 10.3934/amc.2009.3.13.  Google Scholar

[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).   Google Scholar

[15]

C. L. M. Van Pul and T. Etzion, New lower bounds for constant weight codes,, IEEE Trans. Inform. Theory, 35 (1989), 1324.  doi: 10.1109/18.45293.  Google Scholar

show all references

References:
[1]

E. Agrell, A. Vardy and K. Zeger, Upper bounds for constant-weight codes,, IEEE Trans. Inform. Theory, 46 (2000), 2373.  doi: 10.1109/18.887851.  Google Scholar

[2]

B. Bollobas, "Combinatorics,'', Cambridge University Press, (1986).   Google Scholar

[3]

A. E. Brouwer and T. Etzion, Some new distance-4 constant weight codes,, Adv. Math. Commun., 5 (2011), 417.  doi: 10.3934/amc.2011.5.417.  Google Scholar

[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.  doi: 10.1109/18.59932.  Google Scholar

[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.  doi: 10.3934/amc.2010.4.419.  Google Scholar

[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.  doi: 10.3934/amc.2010.4.597.  Google Scholar

[7]

C. Bujtás and Z. Tuza, Optimal combinatorial batch codes derived from dual systems,, Miskolc Math. Notes, 12 (2011), 11.   Google Scholar

[8]

C. Bujtás and Z. Tuza, Optimal batch codes: many items or low retrieval requirement,, Adv. Math. Commnun., 5 (2011), 529.  doi: 10.3934/amc.2011.5.529.  Google Scholar

[9]

R. L. Graham and N. J. A. Sloane, Lower bounds for constant weight codes,, IEEE Trans. Inform. Theory, 26 (1980), 37.  doi: 10.1109/TIT.1980.1056141.  Google Scholar

[10]

W. C. Huffman and V. Pless, "Fundamentals of Error-Correcting Codes,'', Cambridge University Press, (2003).   Google Scholar

[11]

Y. Ishai, E. Kushilevitz, R. Ostrovsky and A. Sahai, Batch codes and their applications,, in, 36 (2004), 262.  doi: 10.1145/1007352.1007396.  Google Scholar

[12]

T. Klove, A lower bound for $A(n, 4, w)$,, IEEE Trans. Inform. Theory, 27 (1981), 257.  doi: 10.1109/TIT.1981.1056318.  Google Scholar

[13]

M. B. Patterson, D. R. Stinson and R. Wei, Combinatorial batch codes,, Adv. Math. Commun., 3 (2009), 13.  doi: 10.3934/amc.2009.3.13.  Google Scholar

[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).   Google Scholar

[15]

C. L. M. Van Pul and T. Etzion, New lower bounds for constant weight codes,, IEEE Trans. Inform. Theory, 35 (1989), 1324.  doi: 10.1109/18.45293.  Google Scholar

[1]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[2]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020374

[3]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (91)
  • HTML views (0)
  • Cited by (13)

Other articles
by authors

[Back to Top]