Full paper in PDF format:
$%E.-Y. Park and I. Blake, Construction of extended Steiner systems for information retrieval, Rev. Mat. Complut. 21 (2008), no. 1, 179–190.%$

Construction of Extended Steiner Systems
for Information Retrieval
Eun-Young PARK and Ian BLAKE
Department of Electrical and Computer Engineering
University of Toronto
Toronto, Ontario — Canada
ecpark@comm.utoronto.ca  ifblake@comm.utoronto.ca

Received: March 2, 2007
Accepted: August 30, 2007

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 (1972). 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 ["On the existence of extended triple systems" (Bennett and Mendelssohn, 1978), "Extended triple systems" (Johnson and Mendelssohn, 1972)]. 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 .

Key words: information retrieval, batch codes, combinatorial designs, Steiner systems.
2000 Mathematics Subject Classification: 05B05, 05E05, 62K10.