Information retrieval with unambiguous output

The main problem in information storage has previously been how large amounts of data can be stored. However, the technological development over the years has been able to give rather satisfactory answers to this problem. Recently, the focus has shifted towards determining how stored information can...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2015-06, Vol.242, p.354-368
Main Authors: Junnila, Ville, Laihonen, Tero
Format: Article
Language:English
Subjects:
Algorithmic complexity
Associative memory
Covering code
Extremal graph
Forced vertex
Information retrieval
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The main problem in information storage has previously been how large amounts of data can be stored. However, the technological development over the years has been able to give rather satisfactory answers to this problem. Recently, the focus has shifted towards determining how stored information can be efficiently retrieved. This problem is addressed in an article by E. Yaakobi and J. Bruck (2012), where information retrieval in associative memories is studied. In this paper, we focus on the case where the retrieved information unit is unambiguous. In particular, we present characterizations and study various extremal properties of such associative memories. Moreover, the algorithmic complexity of certain naturally rising problems is considered.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2015.04.002