# American Institute of Mathematical Sciences

August  2011, 5(3): 529-541. doi: 10.3934/amc.2011.5.529

## Optimal batch codes: Many items or low retrieval requirement

 1 Department of Computer Science and Systems Technology, University of Pannonia, Egyetem u. 10, Veszprém, H-8200, Hungary 2 Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, Budapest, H-1111, Hungary

Received  December 2010 Revised  May 2011 Published  August 2011

Combinatorial batch codes were introduced by Ishai et al. [36th ACM STOC (2004), 262-271] and studied in detail by Paterson et al. [Adv. Math. Commun., 3 (2009), 13-27] for the purpose of distributed storage and retrieval of items of a database on a given number of servers in an economical way. A combinatorial batch code with parameters $n,k,m,t$ means that $n$ items are stored on $m$ servers such that any $k$ different items can be retrieved by reading out at most $t$ items from each server. If $t=1$, this can equivalently be represented with a family $\mathcal F$ of $n$ not necessarily distinct sets over an $m$-element underlying set, such that the union of any $i$ members of $\mathcal F$ has cardinality at least $i$, for every $1\le i\le k$. The goal is to determine the minimum $N(n,k,m)$ of $\sum$$F\in\mathcal F$$|F|$ over all combinatorial batch codes $\mathcal F$ with given parameters $n,k,m$ and $t=1$.
We prove $N(n,k,m)= (k-1)n- \lfloor \frac{(k-1){m \choose k-1}-n}{m-k+1} \rfloor$ for all ${m\choose k-2} \le n \le (k-1){m\choose k-1}$. Together with the results of Paterson et al. for $n$ larger, this completes the determination of $N(n,3,m)$. We also compute $N(n,4,m)$ in the entire range $n\ge m\ge 4$. Several types of code transformations keeping optimality are described, too.
Citation: Csilla Bujtás, Zsolt Tuza. Optimal batch codes: Many items or low retrieval requirement. Advances in Mathematics of Communications, 2011, 5 (3) : 529-541. doi: 10.3934/amc.2011.5.529
##### References:
 [1] C. Berge, "Hypergraphs,'' North-Holland, Amsterdam, 1989. [2] S. Bhattacharya, S. Ruj and B. Roy, Combinatorial batch codes: A lower bound and optimal constructions,, preprint, (). [3] 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; Corrigendum, Adv. Math. Commun., 4 (2010), 597 pp. [4] Cs. Bujtás and Zs. Tuza, Combinatorial batch codes: Extremal problems under Hall-type conditions, Electronic Notes Discrete Math., (2011), to appear. [5] Cs. Bujtás and Zs. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes (2011), to appear. [6] Y. Ishai, E. Kushiletitz, R. Ostrovsky and A. Sahai, Batch codes and their applications, in "Proceedings of the 36th Annual ACM Symposium on Theory of Computing,'' ACM Press, New York, (2004), 262-271. [7] M. B. Paterson, D. R. Stinson and R. Wei, Combinatorial batch codes, Adv. Math. Commun., 3 (2009), 13-27. doi: 10.3934/amc.2009.3.13.

show all references

##### References:
 [1] C. Berge, "Hypergraphs,'' North-Holland, Amsterdam, 1989. [2] S. Bhattacharya, S. Ruj and B. Roy, Combinatorial batch codes: A lower bound and optimal constructions,, preprint, (). [3] 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; Corrigendum, Adv. Math. Commun., 4 (2010), 597 pp. [4] Cs. Bujtás and Zs. Tuza, Combinatorial batch codes: Extremal problems under Hall-type conditions, Electronic Notes Discrete Math., (2011), to appear. [5] Cs. Bujtás and Zs. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes (2011), to appear. [6] Y. Ishai, E. Kushiletitz, R. Ostrovsky and A. Sahai, Batch codes and their applications, in "Proceedings of the 36th Annual ACM Symposium on Theory of Computing,'' ACM Press, New York, (2004), 262-271. [7] M. B. Paterson, D. R. Stinson and R. Wei, Combinatorial batch codes, Adv. Math. Commun., 3 (2009), 13-27. doi: 10.3934/amc.2009.3.13.
 [1] Xu Zhang, Xiang Li. Modeling and identification of dynamical system with Genetic Regulation in batch fermentation of glycerol. Numerical Algebra, Control and Optimization, 2015, 5 (4) : 393-403. doi: 10.3934/naco.2015.5.393 [2] Tao Jiang, Liwei Liu. Analysis of a batch service multi-server polling system with dynamic service control. Journal of Industrial and Management Optimization, 2018, 14 (2) : 743-757. doi: 10.3934/jimo.2017073 [3] Chongyang Liu, Zhaohua Gong, Enmin Feng, Hongchao Yin. Modelling and optimal control for nonlinear multistage dynamical system of microbial fed-batch culture. Journal of Industrial and Management Optimization, 2009, 5 (4) : 835-850. doi: 10.3934/jimo.2009.5.835 [4] Omer Faruk Yilmaz, Mehmet Bulent Durmusoglu. A performance comparison and evaluation of metaheuristics for a batch scheduling problem in a multi-hybrid cell manufacturing system with skilled workforce assignment. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1219-1249. doi: 10.3934/jimo.2018007 [5] Bangyu Shen, Xiaojing Wang, Chongyang Liu. Nonlinear state-dependent impulsive system in fed-batch culture and its optimal control. Numerical Algebra, Control and Optimization, 2015, 5 (4) : 369-380. doi: 10.3934/naco.2015.5.369 [6] Wenjuan Zhao, Shunfu Jin, Wuyi Yue. A stochastic model and social optimization of a blockchain system based on a general limited batch service queue. Journal of Industrial and Management Optimization, 2021, 17 (4) : 1845-1861. doi: 10.3934/jimo.2020049 [7] Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261 [8] Zsolt Saffer, Wuyi Yue. A dual tandem queueing system with GI service time at the first queue. Journal of Industrial and Management Optimization, 2014, 10 (1) : 167-192. doi: 10.3934/jimo.2014.10.167 [9] M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281 [10] Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027 [11] Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032 [12] Vladimir Pozdyayev. 2D system analysis via dual problems and polynomial matrix inequalities. Numerical Algebra, Control and Optimization, 2016, 6 (4) : 491-504. doi: 10.3934/naco.2016022 [13] Yu Tian, John R. Graef, Lingju Kong, Min Wang. Existence of solutions to a multi-point boundary value problem for a second order differential system via the dual least action principle. Conference Publications, 2013, 2013 (special) : 759-769. doi: 10.3934/proc.2013.2013.759 [14] María Chara, Ricardo A. Podestá, Ricardo Toledano. The conorm code of an AG-code. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021018 [15] Martino Borello, Francesca Dalla Volta, Gabriele Nebe. The automorphism group of a self-dual $[72,36,16]$ code does not contain $\mathcal S_3$, $\mathcal A_4$ or $D_8$. Advances in Mathematics of Communications, 2013, 7 (4) : 503-510. doi: 10.3934/amc.2013.7.503 [16] Zhongming Chen, Liqun Qi. Circulant tensors with applications to spectral hypergraph theory and stochastic process. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1227-1247. doi: 10.3934/jimo.2016.12.1227 [17] Jean-Marc Hérard, Olivier Hurisse. Some attempts to couple distinct fluid models. Networks and Heterogeneous Media, 2010, 5 (3) : 649-660. doi: 10.3934/nhm.2010.5.649 [18] Johan Chrisnata, Han Mao Kiah, Sankeerth Rao Karingula, Alexander Vardy, Eitan Yaakobi Yao, Hanwen Yao. On the number of distinct k-decks: Enumeration and bounds. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021032 [19] Thomas Feulner. The automorphism groups of linear codes and canonical representatives of their semilinear isometry classes. Advances in Mathematics of Communications, 2009, 3 (4) : 363-383. doi: 10.3934/amc.2009.3.363 [20] Anton Zorich. Explicit Jenkins-Strebel representatives of all strata of Abelian and quadratic differentials. Journal of Modern Dynamics, 2008, 2 (1) : 139-185. doi: 10.3934/jmd.2008.2.139

2020 Impact Factor: 0.935