Space/time trade-offs for associative memory

TitleSpace/time trade-offs for associative memory
Publication TypeConference Papers
Year of Publication1996
AuthorsGROVE AJ, Jacobs DW
Conference NamePattern Recognition, 1996., Proceedings of the 13th International Conference on
Date Published1996/08//
Keywordsaccess, matching;set, memory;associative, nets;pattern, processing;content-addressable, query;memory, recall;membership, scheme;associative, space;set, storage;neural, theory;, theory;storage, time;associative

In any storage scheme, there is some trade-off between the space used (size of memory) and access time. However, the nature of this trade-off seems to depend on more than just what is being stored-it also depends the types of queries we consider. We justify this claim by considering a particular memory model and contrast recognition (membership queries) with associative recall. We show that the latter task can require exponentially larger memories even when identical information is stored