Space/time trade-offs for associative memory
| Title | Space/time trade-offs for associative memory |
| Publication Type | Conference Papers |
| Year of Publication | 1996 |
| Authors | GROVE AJ, Jacobs DW |
| Conference Name | Pattern Recognition, 1996., Proceedings of the 13th International Conference on |
| Date Published | 1996/08// |
| Keywords | access, matching;set, memory;associative, nets;pattern, processing;content-addressable, query;memory, recall;membership, scheme;associative, space;set, storage;neural, theory;, theory;storage, time;associative |
| Abstract | 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 |
| DOI | 10.1109/ICPR.1996.547434 |