Article Contents
Article Contents

# Optimal batch codes: Many items or low retrieval requirement

• 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.
Mathematics Subject Classification: Primary: 05A05, 05C65, 05D05, 68P20, 68R05.

 Citation:

•  [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, arXiv:1102.4951v1 [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.