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.
This setup has first appeared in @cite_14 . It was shown therein that the minimum distance @math of a batch code satisfies @math . It is worth mentioning that batch codes are closely related to locally repairable codes, which have been extensively studied in the context of the distributed data storage. The main difference between them is that in batch codes we are interested in the reconstruction of information symbols in @math , while in locally repairable codes we are interested in the recovery of coded symbols in @math .
@cite_14
2097444899
In an application, where a client wants to obtain many symbols from a large database, it is often desirable to balance the load. Batch codes (introduced by in STOC 2004) do exactly that: the large database is divided between many servers, so that the client has to only make a small number of queries to every server to obtain sufficient information to reconstruct all desired symbols.