Information Retrieval With Varying Number of Input Clues

Abstract

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 <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">u</sub> on the maximum number of them is imposed. Of course, we would like m <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">u</sub> to be as small as possible. We consider the problem over the binary Hamming space F <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> and focus on the minimum of m <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">u</sub> , 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.