Optimal batch codes: Many items or low retrieval requirement

摘要

Combinatorial batch codes were introduced by Ishai et al. [36~(th) 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 F of n not necessarily distinct sets over an m-element underlying set, such that the union of any i members of F has cardinality at least i, for every 1 ≤ P i ≤ k. The goal is to determine the minimum N(n, k,m) of ∑ F ∈ F |F| over all combinatorial batch codes F with given parameters n; k;m and t = 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 ≥ m ≥ 4. Several types of code transformations keeping optimality are described, too.