Consider a large database of n data items that need to be stored using m servers. We study how to encode information so that a large number k of read requests can be performed \textit{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~\cite{batch}.

We give families of multiset batch codes with asymptotically optimal rates of the form 1 − 1 poly ( k ) and a number of servers m scaling polynomially in the number of read requests k . 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.