\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Optimal batch codes: Many items or low retrieval requirement

Abstract / Introduction Related Papers Cited by
  • 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:

    \begin{equation} \\ \end{equation}
  • [1]

    C. Berge, "Hypergraphs,'' North-Holland, Amsterdam, 1989.

    [2]

    S. Bhattacharya, S. Ruj and B. RoyCombinatorial 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.

  • 加载中
SHARE

Article Metrics

HTML views() PDF downloads(103) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return