The Basics of Sparse Distributed Storage
- Want to store n length vectors or words, but not use N=2^n space
- So choose N' hard locations, which will serve as the address space
- Thes locations are chosen so they are distributed evenly throughout
- These locations are the only locations in the storage space
- When storing a vector, store it at all the addresses it is 'close' to
- Close: defined by hamming distance, max distance away = r
- Each address of N' has a single storage space
- A word is stored at multiple addresses at a single time, for each:
- Store a vector at an address by literally adding it to the contents of the location
- If a location had storage 1001001, adding 1111111 to that location would result in the storage being 2112112.
The number of words stored at that address is also kept
A word is retrieved from a given address as follows:
- For all addresses within r of the given address take the bitwise sum of the storage contents
- Also, take the sum of the number of words stored
- For each bit, if the sum is > (1/2)[total stored words] the retrieved word will have a 1
- If the sum is < (1/2)[total stored words] the retrieved word will have a 0 at that bit
- This process is repeated a small number of times, approx 5
Thus, retrieving a word from an address accesses a number of addresses at once