Resumen de Construction of extended Steiner systems for information retrieval
Eun-Young Park, Ian Blake
A multiset batch code is a variation of information retrieval where a -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 -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 (1972). An extended Steiner system is a collection of -multisets (thus, allowing repetition of elements in a block) of a -set such that every -multiset belongs to exactly one block. An extended triple system, with and , has been investigated and constructed previously [Bennett and Mendelssohn (1978), Johnson and Mendelssohn (1972)]. We study extended systems over elements with , denoted as . We show constructions of for all and .
