Linear batch codes and codes for private information retrieval (PIR) with a query size @math and a restricted size @math of the reconstruction sets are studied. New bounds on the parameters of such codes are derived for small values of @math or of @math by providing corresponding constructions. By building on the ideas of Cadambe and Mazumdar, a new bound in a recursive form is derived for batch codes and PIR codes.
Binary simplex codes of length @math are shown to be optimal batch codes with parameters @math , @math and @math (for any @math ) @cite_4 , yet those codes exist only for very specific parameters.
@cite_4
2951944286 2082173153 2886748290 2888898008
Consider a large database of @math data items that need to be stored using @math servers. We study how to encode information so that a large number @math of read requests can be performed in parallel while the rate remains constant (and ideally approaches one). This problem is equivalent to the design of multiset Batch Codes introduced by Ishai, Kushilevitz, Ostrovsky and Sahai [17]. We give families of multiset batch codes with asymptotically optimal rates of the form @math and a number of servers @math scaling polynomially in the number of read requests @math . An advantage of our batch code constructions over most previously known multiset batch codes is explicit and deterministic decoding algorithms and asymptotically optimal fault tolerance. Our main technical innovation is a graph-theoretic method of designing multiset batch codes using dense bipartite graphs with no small cycles. We modify prior graph constructions of dense, high-girth graphs to obtain our batch code results. We achieve close to optimal tradeoffs between the parameters for bipartite graph based batch codes. In this paper we study the problem of finding maximally sized subsets of binary strings (codes) of equal length that are immune to a given number @math of repetitions, in the sense that no two strings in the code can give rise to the same string after @math repetitions. We propose explicit number theoretic constructions of such subsets. In the case of @math repetition, the proposed construction is asymptotically optimal. For @math , the proposed construction is within a constant factor of the best known upper bound on the cardinality of a set of strings immune to @math repetitions. Inspired by these constructions, we then develop a prefixing method for correcting any prescribed number @math of repetition errors in an arbitrary binary linear block code. The proposed method constructs for each string in the given code a carefully chosen prefix such that the resulting strings are all of the same length and such that despite up to any @math repetitions in the concatenation of the prefix and the codeword, the original codeword can be recovered. In this construction, the prefix length is made to scale logarithmically with the length of strings in the original code. As a result, the guaranteed immunity to repetition errors is achieved while the added redundancy is asymptotically negligible. Binary maximum distance separable (MDS) array codes contain @math information columns and @math parity columns in which each entry is a bit that can tolerate @math arbitrary erasures. When a column in an MDS code fails, it has been proven that we must download at least half of the content from each helper column if @math columns are selected as the helper columns. If the lower bound is achieved such that the @math helper columns can be selected from any @math surviving columns, then the repair is an optimal repair. Otherwise, if the lower bound is achieved with @math specific helper columns, the repair is a weak-optimal repair. This paper proposes a class of binary MDS array codes with @math and @math that asymptotically achieve weak-optimal repair of an information column with @math helper columns. We show that there exist many encoding matrices such that the corresponding binary MDS array codes can asymptotically achieve weak-optimal repair for repairing any information column. A (tandem) duplication of length @math is an insertion of an exact copy of a substring of length @math next to its original position. This and related types of impairments are of relevance in modeling communication in the presence of synchronization errors, as well as in several information storage applications. We demonstrate that Levenshtein’s construction of binary codes correcting insertions of zeros is, with minor modifications, applicable also to channels with arbitrary alphabets and with duplication errors of arbitrary (but fixed) length @math . Furthermore, we derive bounds on the cardinality of optimal @math -ary codes correcting up to @math duplications of length @math and establish the following corollaries in the asymptotic regime of growing block length: 1) the presented family of codes is optimal for every @math , in the sense of the asymptotic scaling of code redundancy; 2) the upper bound, when specialized to @math , @math , improves upon Levenshtein’s bound for every @math ; and 3) the bounds coincide for @math , thus yielding the exact asymptotic behavior of the size of optimal single-duplication-correcting codes.