Bloom Filters: the Practice

• Choosing hash functions

  • bits from MD5 signatures of URLs

• Maintaining the summary

  • the proxy maintains an array of counters
  • for each bit, the counter records how many times the bit is set to 1

• Updating the summary

  • either the whole bit array or the positions of changed bits (delta encoding)

Previous slide

Next slide

Back to first slide

View graphic version