Construction of Extended Steiner Systems for Information Retrieval

Abstract

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.