Bloom Filter - Probabilistic Data Structure - Nesne Var Diyorsa Yanılma İhtimali (False Positive) Bulunur

Giriş
Bloom Filter'ı şimdiye kadar hiçbir programda kullanmadım. Ama ilginç bir konu olduğunu düşündüğüm için not almak istedim.

Bloom Filter Nedir?
Çok fazla sayıda nesneyi - örneğin 10 milyon tane - bir set/dictionary/map içinde bellekte tutmak istersek ve amacımız sadece nesnenin  veri yapısı içinde olmadığını bilmek ise bloom filter kullanılır. Açıklaması şöyle

When you ask a Bloom filter if it remembers a specific item, it will answer either “probably yes” or “definitely no.” If it says “probably yes” there’s a slight chance that it could be wrong. But if it says “definitely no” it’s totally confident about the answer.

Nasıl Çalışır
Bir tane büyük bit array yaratılır. Eklenmek istenen nesne N farklı hash'ten geçirilir. Her hash sonucunda array içindeki bir bit atanır. Nesne var mı kontrolü yapılmak istenirse tekrar N tane hash çalıştırılır. 

- Eğer bitlerden bir tanesi bile 0 ise nesne yoktur. 

- Tüm bitlerin 1 olması nesnenin var olduğu anlamına gelmez. False positive bir sonuç gelmiş olabilir.

Bazı Kullanım Örnekleri

1. Google Chrome

 Açıklaması şöyle

Whenever you try to access a URL, Google Chrome first checks with a local Bloom filter in your browser. This filter is filled with a list of hashed malicious URLs. If the Bloom filter returns “probably yes,” Chrome reaches out to Google’s servers for further verification. If the Bloom filter says “definitely no,” Chrome doesn’t bother with the server check, saving you time and preserving server resources.

2. Apache Cassandra and HBase

 Açıklaması şöyle

Instead of doing a slow disk read every time they need to check if specific data exists, these databases use a Bloom filter for a quick first check. The Bloom filter has a smaller memory footprint, which makes this operation much faster. If the Bloom filter returns “probably yes,” the system may perform a disk read to confirm. But if the filter says “definitely no,” the system avoids the disk read, saving a lot of time.

Yanlış Kullanım Örneği

Sosyal ağlarda A ve C kişileri eğer ortak B arkadaşları varsa, arkadaş olabiliyorlar. A ve C'nin ortak arkadaşları var mı diye kontrol etmek için bloom filter kullanılamaz. Çünkü bloom filter var derse bile yanılma ihtimali bulunur,  yani false positive  dönebilir.

Gerçekleştirim Örnekleri

Örnek

Şöyle yaparız

import java.util.BitSet;
import java.nio.ByteBuffer;
import java.nio.ByteOrder;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

public class BloomFilter {
  private BitSet bitSet;
  private int bitSetSize;
  private int numOfHashFunctions;

  public BloomFilter(int size, int numOfHashFunctions) {
    this.bitSetSize = size;
    this.numOfHashFunctions = numOfHashFunctions;
    this.bitSet = new BitSet(bitSetSize);
  }

  // Add element to Bloom Filter
  public void add(String url) throws NoSuchAlgorithmException {
    for (int i = 0; i < numOfHashFunctions; i++) {
      int hashCode = getHash(url, i);
      bitSet.set(Math.abs(hashCode % bitSetSize));
    }
  }

  // Check if element is present in Bloom Filter
  public boolean mightContain(String url) throws NoSuchAlgorithmException {
    for (int i = 0; i < numOfHashFunctions; i++) {
      int hashCode = getHash(url, i);
      if (!bitSet.get(Math.abs(hashCode % bitSetSize))) {
        return false;
      }
    }
    return true;
  }

  // Computes the i-th hash function for the given URL
  private int getHash(String url, int i) throws NoSuchAlgorithmException {
     MessageDigest md5 = MessageDigest.getInstance("MD5");
     md5.update(ByteBuffer.allocate(4).order(ByteOrder.LITTLE_ENDIAN).putInt(i).array());
     md5.update(url.getBytes());
     byte[] digest = md5.digest();
     int hash = ByteBuffer.wrap(digest).getInt();
     return hash;
  }
}

Kullanmak için şöyle yaparız

public static void main(String[] args) throws NoSuchAlgorithmException {
  BloomFilter bloomFilter = new BloomFilter(1000000, 3);

  // Add some URLs to the Bloom filter
  bloomFilter.add("http://example1.com");
  bloomFilter.add("http://example2.com");

  // Check if URLs are present in the Bloom filter
  System.out.println(bloomFilter.mightContain("http://example1.com")); // Outputs: true
  System.out.println(bloomFilter.mightContain("http://example3.com")); // Outputs: false
}

Guava

BloomFilter Sınıfı yazısına taşıdım