    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:
  C. Berge, "Hypergraphs,'', North-Holland, (1989). Google Scholar  S. Bhattacharya, S. Ruj and B. Roy, Combinatorial batch codes: A lower bound and optimal constructions,, preprint, ().   Google Scholar  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. Google Scholar  Cs. Bujtás and Zs. Tuza, Combinatorial batch codes: Extremal problems under Hall-type conditions,, Electronic Notes Discrete Math., (2011).   Google Scholar  Cs. Bujtás and Zs. Tuza, Optimal combinatorial batch codes derived from dual systems,, Miskolc Math. Notes (2011), (2011).   Google Scholar  Y. Ishai, E. Kushiletitz, R. Ostrovsky and A. Sahai, Batch codes and their applications,, in, (2004), 262. Google Scholar  M. B. Paterson, D. R. Stinson and R. Wei, Combinatorial batch codes,, Adv. Math. Commun., 3 (2009), 13.  doi: 10.3934/amc.2009.3.13.  Google Scholar

show all references

##### References:
  C. Berge, "Hypergraphs,'', North-Holland, (1989). Google Scholar  S. Bhattacharya, S. Ruj and B. Roy, Combinatorial batch codes: A lower bound and optimal constructions,, preprint, ().   Google Scholar  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. Google Scholar  Cs. Bujtás and Zs. Tuza, Combinatorial batch codes: Extremal problems under Hall-type conditions,, Electronic Notes Discrete Math., (2011).   Google Scholar  Cs. Bujtás and Zs. Tuza, Optimal combinatorial batch codes derived from dual systems,, Miskolc Math. Notes (2011), (2011).   Google Scholar  Y. Ishai, E. Kushiletitz, R. Ostrovsky and A. Sahai, Batch codes and their applications,, in, (2004), 262. Google Scholar  M. B. Paterson, D. R. Stinson and R. Wei, Combinatorial batch codes,, Adv. Math. Commun., 3 (2009), 13.  doi: 10.3934/amc.2009.3.13.  Google Scholar
  Zongyuan Li, Weinan Wang. Norm inflation for the Boussinesq system. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020353  Neng Zhu, Zhengrong Liu, Fang Wang, Kun Zhao. Asymptotic dynamics of a system of conservation laws from chemotaxis. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 813-847. doi: 10.3934/dcds.2020301  Craig Cowan, Abdolrahman Razani. Singular solutions of a Lane-Emden system. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 621-656. doi: 10.3934/dcds.2020291  Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321  Manil T. Mohan. First order necessary conditions of optimality for the two dimensional tidal dynamics system. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020045  Sumit Arora, Manil T. Mohan, Jaydev Dabas. Approximate controllability of a Sobolev type impulsive functional evolution system in Banach spaces. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020049  Helmut Abels, Andreas Marquardt. On a linearized Mullins-Sekerka/Stokes system for two-phase flows. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020467  Adel M. Al-Mahdi, Mohammad M. Al-Gharabli, Salim A. Messaoudi. New general decay result for a system of viscoelastic wave equations with past history. Communications on Pure & Applied Analysis, 2021, 20 (1) : 389-404. doi: 10.3934/cpaa.2020273  Yuxin Zhang. The spatially heterogeneous diffusive rabies model and its shadow system. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020357  Hai Huang, Xianlong Fu. Optimal control problems for a neutral integro-differential system with infinite delay. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020107  Hao Wang. Uniform stability estimate for the Vlasov-Poisson-Boltzmann system. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 657-680. doi: 10.3934/dcds.2020292  Yichen Zhang, Meiqiang Feng. A coupled $p$-Laplacian elliptic system: Existence, uniqueness and asymptotic behavior. Electronic Research Archive, 2020, 28 (4) : 1419-1438. doi: 10.3934/era.2020075  Youshan Tao, Michael Winkler. Critical mass for infinite-time blow-up in a haptotaxis system with nonlinear zero-order interaction. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 439-454. doi: 10.3934/dcds.2020216  Jianquan Li, Xin Xie, Dian Zhang, Jia Li, Xiaolin Lin. Qualitative analysis of a simple tumor-immune system with time delay of tumor action. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020341  Denis Bonheure, Silvia Cingolani, Simone Secchi. Concentration phenomena for the Schrödinger-Poisson system in $\mathbb{R}^2$. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020447  Xavier Carvajal, Liliana Esquivel, Raphael Santos. On local well-posedness and ill-posedness results for a coupled system of mkdv type equations. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020382  Fathalla A. Rihan, Hebatallah J. Alsakaji. Stochastic delay differential equations of three-species prey-predator system with cooperation among prey species. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020468  Karoline Disser. Global existence and uniqueness for a volume-surface reaction-nonlinear-diffusion system. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 321-330. doi: 10.3934/dcdss.2020326  Mathew Gluck. Classification of solutions to a system of $n^{\rm th}$ order equations on $\mathbb R^n$. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5413-5436. doi: 10.3934/cpaa.2020246  Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167

2019 Impact Factor: 0.734