Compressed Bloom Filter

Summary A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Compressed Bloom filters improve performance when the Bloom filter is passed as a message; its transmission size is a limiting factor. Bloom filters have been suggested as a means for sharing Web cache information. In this setting, proxies do not share the exact contents of their caches, but instead periodically broadcast Bloom filters representing their cache. By using compressed Bloom filters, proxies can reduce the number of bits broadcast, the false positive rate, and/or the amount of computation per lookup. The cost is the processing time for compression and decompression, which can use simple arithmetic coding, and more memory use at the proxies, which utilize the larger uncompressed form of the Bloom filter.

Applications Web cache sharing systems For Further Information Please Contact the Director of Business Development Alan Gordon Email: [email protected] Telephone: (617) 384-5000

Inventor(s): Mitzenmacher, Michael D.

Type of Offer: Licensing



« More Engineering - Electrical Patents
« More Software Patents

---