Counting Bloom Filter

Membership - Counting Bloom Filter

Refs:

• Fan, L., et al. (2000) “Summary cache: a scalable wide-area web cache sharing protocol”, Journal IEEE/ACM Transactions on Networking, Vol. 8 (3), pp. 281–293.

Simple usage:

#include <membership/counting_bloom_filter.h>
#include <vector>
#include <string>

int main() {
    std::vector<std::string> urls{
        "https://google.com",
        "https://instagram.com",
        "https://youtube.com",
        "https://facebook.com",
        "https://twitter.com"};
    // Define bloom filter with 4 hash functions and 128 memory bits
    counting_bloom_filter<4, 128> url_bloom_filter;
    std::for_each(urls.begin(), urls.end(), [&url_bloom_filter](auto& item) {
        // Insert items into bloom filter
        url_bloom_filter.insert(item);
    });

    // Check that bloom filter contains an item or not
    if (url_bloom_filter.contains("https://gmail.com")) {
        std::cout << "FOUND!!!!!" << std::endl;
    } else {
        std::cout << "NOT FOUND" << std::endl;
    }
    
    if (url_bloom_filter.contains(urls[0])) {
        std::cout << "FOUND" << std::endl;
    } else {
        std::cout << "NOT FOUND!!!!!" << std::endl;
    }
    // Erase an item and check for existence
    url_bloom_filter.erase(urls[0]);
    if (url_bloom_filter.contains(urls[0])) {
        std::cout << "FOUND!!!!!" << std::endl;
    } else {
        std::cout << "NOT FOUND" << std::endl;
    }
}