Construction of Extended Steiner Systems for Information Retrieval

Résumé

A multiset batch code is a variation of information retrieval where a t-multiset of items can be retrieved by reading at most one bit from each server. We study a problem at the other end of the spectrum, namely that of retrieving a t-multiset of items by accessing exactly one server. Our solution to the problem is a combinatorial notion called an extended Steiner system, which was first studied by Johnson and Mendelsohn [11]. An extended Steiner system ES(t; k; v) is a collection of k-multisets (thus, allowing repetition of elements in a block) of a v-set such that every t-multiset belongs to exactly one block. An extended triple system, with t = 2 and k = 3, has been investigated and constructed previously [3, 11]. We study extended systems over v elements with k = t + 1, denoted as ES(t, t + 1, v). We show constructions of ES(t, t + 1, v) for all t ≥ 3 and v ≥ t + 1.