Construction of extended Steiner systems for information retrieval
- Autores: Eun-Young Park, Ian Blake
- Localización: Revista matemática complutense, ISSN-e 1988-2807, ISSN 1139-1138, Vol. 21, Nº 1, 2008, págs. 179-190
- Idioma: inglés
- DOI: 10.5209/rev_rema.2008.v21.n1.16452
- Enlaces
-
Resumen
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 .
