Information retrieval and the average number of input clues



: Laihonen T

Publisher: AMER INST MATHEMATICAL SCIENCES-AIMS

: 2017

: Advances in Mathematics of Communications

: ADVANCES IN MATHEMATICS OF COMMUNICATIONS

: ADV MATH COMMUN

: 11

: 1

: 203

: 223

: 21

: 1930-5346

: 1930-5338

DOI: https://doi.org/10.3934/amc.2017013


Information retrieval in an associative memory was introduced in a recent paper by Yaakobi and Bruck. The associative memory is represented by a graph where the vertices correspond to the stored information units and the edges to associations between them. The goal is to find a stored information unit in the memory using input clues. In this paper, we study the minimum average number of input clues needed to find the sought information unit in the infinite king grid. We provide a geometric approach to determine the minimum number of input clues. Using this approach we are able to find optimal results and bounds on the number of input clues. The model by Yaakobi and Bruck has also applications to sensor networks monitoring and Levenshtein's sequence reconstruction problem.



Last updated on 2024-26-11 at 23:13