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.
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.