Algorithms For Dummies

  Managing Big Data 

     241

an  element  from  the  filter  after  adding  it  (the  filter  has  an  indelible  memory). 

When adding an element to a bit vector, the bit vector has some bits set to 1, as 

shown in Figure 12-4. In this case, the Bloom filter adds X to the bit vector.

You can add as many elements as is necessary to the bit vector. For example, 

 Figure  12-5  shows  what  happens  when  adding  another  element,  Y,  to  the  bit 

 vector. Note that bit 7 is the same for both X and Y. Consequently, bit 7 represents 

a collision between X and Y. These collisions are the source of the potential false 

positives;  because  of  them,  the  algorithm  could  say  that  an  element  is  already 

added to the bit vector when it isn’t. Using a larger bit vector makes collisions 

less likely and improves the performance of the Bloom filter, but does so at the 

cost of both space and time.