Belajar Data Structure - Bloom Filter & Count-Min Sketch

#Pendahuluan

Setelah di episode 20 kita memahami Union-Find — struktur data untuk merge dan query set — pada episode ini kita mempelajari struktur data probabilistik: Bloom filter dan count-min sketch. Keduanya mengorbankan akurasi sempurna untuk efisiensi memori yang luar biasa — trade-off yang sangat berharga dalam skala besar.

Bloom filter memberikan O(1) insert dan lookup dengan kemungkinan false positive tetapi tidak ada false negative. Artinya, bloom filter bisa salah mengatakan "mungkin ada" tetapi tidak pernah salah mengatakan "pasti tidak ada". Ini menjadikannya ideal untuk cache, anti-spam, dan deduplication.

#Bloom Filter

#Konsep Dasar

Bloom filter adalah bit array dari m bits, digunakan bersama k hash functions. Insert dan lookup melibatkan hashing key dengan semua k hash functions dan mengecek/setting bit di posisi hasil hash.

• Insert: set bit di posisi h1(x), h2(x), ..., hk(x) ke 1
• Lookup: cek apakah semua bit di posisi h1(x), h2(x), ..., hk(x) bernilai 1
  • Jika semua 1: mungkin ada (bisa false positive)
  • Jika ada yang 0: pasti tidak ada (tidak ada false negative)

#False Positive Rate

False positive rate bergantung pada:

• m: ukuran bit array (semakin besar, semakin kecil FPR)
• k: jumlah hash functions (optimal: k = (m/n) × ln(2))
• n: jumlah elemen yang diinsert

#Implementasi dari Nol

Bloom filter sederhana

import mmh3
from bitarray import bitarray
 
class BloomFilter:
    def __init__(self, size, num_hashes):
        self.size = size
        self.num_hashes = num_hashes
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)
 
    def add(self, item):
        for i in range(self.num_hashes):
            index = mmh3.hash(item, i) % self.size
            self.bit_array[index] = 1
 
    def contains(self, item):
        for i in range(self.num_hashes):
            index = mmh3.hash(item, i) % self.size
            if self.bit_array[index] == 0:
                return False
        return True

#Mengukur False Positive Rate

Uji false positive rate

bf = BloomFilter(1000, 7)
 
for i in range(500):
    bf.add(f"item_{i}")
 
false_positives = 0
test_items = 1000
for i in range(500, 500 + test_items):
    if bf.contains(f"item_{i}"):
        false_positives += 1
 
print(f"False positive rate: {false_positives / test_items:.2%}")

#Count-Min Sketch

#Konsep

Count-min sketch adalah struktur data untuk estimasi frequency dengan bounded memory. Mirip bloom filter tetapi menggunakan counter (bukan bit) dan beberapa hash functions.

#Implementasi

Count-min sketch

import mmh3
 
class CountMinSketch:
    def __init__(self, width, depth):
        self.width = width
        self.depth = depth
        self.table = [[0] * width for _ in range(depth)]
 
    def add(self, item, count=1):
        for i in range(self.depth):
            index = mmh3.hash(str(item), i) % self.width
            self.table[i][index] += count
 
    def estimate(self, item):
        return min(
            self.table[i][mmh3.hash(str(item), i) % self.width]
            for i in range(self.depth)
        )

#Sifat

• Overestimate: selalu >= frequency sebenarnya (tidak pernah underestimate)
• Bounded error: error dibatasi oleh jumlah total elemen dibagi width

#Aplikasi

• Cache: cek apakah item ada di cache sebelum I/O mahal
• Anti-spam: cek apakah email ada di blacklist
• Deduplication: cek apakah data sudah diproses
• Network packet analysis: deteksi heavy hitters
• Database: cek apakah key ada di page sebelum disk read

#Bloom Filter vs Hash Set

#Penutup

Inti yang harus dibawa pulang:

• Bloom filter: O(1) insert/lookup, false positive tapi tidak false negative.
• False positive rate bergantung pada m (size), k (hash functions), n (elemen).
• Count-min sketch: estimasi frequency dengan bounded memory, selalu overestimate.
• Aplikasi: cache, anti-spam, deduplication, network packet analysis.
• Bloom filter tidak bisa delete; untuk delete gunakan counting bloom filter.

Di episode 22 selanjutnya kita akan membahas LRU cache dan LFU cache — dua strategi eviction yang paling umum digunakan dalam caching systems. LRU menggunakan doubly-linked list + hash map untuk O(1) get/put dengan evicts least recently used. Ini adalah kombinasi dari beberapa struktur data yang sudah kita pelajari!