Information Retrieval With Varying Number of Input Clues

Information retrieval in associative memories was studied in a recent paper by Yaakobi and Bruck (2012). Associations between memory entries give us the t-neighbourhood of an entry. In their model, an information unit is retrieved from the memory with the aid of input clues, which are chosen from a reference set. In this paper, we consider the situation where the information unit is found unambiguously using the associated t-neighbourhoods of the input clues. A varying number of input clues are allowed, but a limit m(u) on the maximum number of them is imposed. Of course, we would like m(u) to be as small as possible. We consider the problem over the binary Hamming space F-n and focus on the minimum of m(u), denoted by.(n; t). Using linear reference sets, we show that.(n; 2) <= 5 for any n >= 9. We also give infinite families of reference sets, which provide good bounds on.(n; t) for t = 3. In addition, efficient methods are given to obtain bounds on.(n; t) for any t from known reference sets. We also discuss the applications of this model to the Levenshtein's sequence reconstruction problem and the sensor network monitoring.