Minimum Number of Input Clues in Robust Information Retrieval



: Junnila V, Laihonen T

Publisher: IOS PRESS

: 2016

: Fundamenta Informaticae

: FUNDAMENTA INFORMATICAE

: FUND INFORM

: 145

: 3

: 243

: 256

: 14

: 0169-2968

DOI: https://doi.org/10.3233/FI-2016-1359


Information retrieval in associative memories was considered recently by Yaakobi and Bruck. In their model, a stored information unit is retrieved using input clues. In this paper, we study the problem where at most s (s >= 0) of the received input clues can be false and we still want to determine the sought information unit uniquely. We use a coding theoretical approach to estimate the maximum number of stored information units with respect to a given s. Moreover, optimal results for the problem are given, for example, in the infinite king grid. We also discuss the problem in the class of line graphs where a characterization and a connection to k-factors is given.

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