Information Retrieval With Varying Number of Input Clues




Junnila V, Laihonen T

PublisherIEEE-inst Electrical Electronics Engineers INC

2016

IEEE Transactions on Information Theory

IEEE TRANSACTIONS ON INFORMATION THEORY

IEEE T Inform Theory

62

2

625

638

14

0018-9448

1557-9654

DOIhttps://doi.org/10.1109/TIT.2015.2508800



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.


Last updated on 2024-26-11 at 15:09