What is the theory behind Cache Digests?
Cache Digests are based on Bloom Filters – they are a method for representing a set of keys with lookup capabilities; where lookup means “is the key in the filter or not?”. In building a cache digest: • A vector (1-dimensional array) of m bits is allocated, with all bits initially set to 0. • A number, k, of independent hash functions are chosen, h1, h2, …, hk, with range { 1, …, m } (i.e. a key hashed with any of these functions gives a value between 1 and m inclusive). • The set of n keys to be operated on are denoted by: A = { a1, a2, a3, …, an }.
