A Bloom filter is a method for representing a set of n elements (also called keys) to support membership queries. It was invented by Burton Bloom in 1970 [6] and was proposed for use in the web context by Marais and Bharat [37] as a mechani sm for identifying which pages have associated comments stored within a CommonKnowledge server. The idea (illustrated in Figure 3) is to allocate a vector v of