A1 Refereed original research article in a scientific journal

Information Retrieval With Varying Number of Input Clues




AuthorsJunnila V, Laihonen T

PublisherIEEE-inst Electrical Electronics Engineers INC

Publication year2016

JournalIEEE Transactions on Information Theory

Journal name in sourceIEEE TRANSACTIONS ON INFORMATION THEORY

Journal acronymIEEE T Inform Theory

Volume62

Issue2

First page 625

Last page638

Number of pages14

ISSN0018-9448

eISSN1557-9654

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


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(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.


Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





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