Bloom filter, Count-Min ve HyperLogLog

Bloom filter m bit ve k hash konumu kullanır. Ekleme bitleri açar; sorguda bir bit kapalıysa eleman kesin yoktur. Hepsi açıksa belki vardır. Standart doğru ekleme/sorgu modelinde false negative yoktur; false positive olabilir. Bit silmek başka elemanları bozabilir, counting Bloom veya başka yapı gerekir. Yaklaşık false-positive olasılığı (1−e^(−kn/m))^k; bağımsız ve düzgün hash varsayımını unutma.

Optimal yaklaşık k=(m/n)ln2'dir. O(k) hash/bit işlemi yapılır; “neredeyse sıfır bellek ve koşulsuz O(1)” denemez. Dağıtık replica gecikmesi veya yanlış silme false negative üretebilir; veri yapısının matematiksel garantisi operasyonel sistemin garantisi değildir.

Count-Min Sketch frekansları birden fazla counter satırında sayar; nonnegative insert-only akışta minimum estimate fazla tahmin edebilir, az tahmin etmez. HyperLogLog distinct cardinality tahmin eder, membership sorgusu cevaplamaz. Cuckoo filter fingerprint'lerle bazı silme işlemlerini destekler. Hata payı, seed uyumu, merge koşulları ve adversarial input her sketch için ayrı değerlendirilir.

False-positive bütçesi hesapla

Yaklaşık ideal hash modelinde p=(1−e^(−kn/m))^k. k≈(m/n)ln2 seçilince m≈−n ln p/(ln2)². Bir milyon eleman ve p=0.01 için yaklaşık 9.59 milyon bit, yani yaklaşık 1.2 MB bit storage gerekir; metadata ve implementation overhead ayrıca eklenir. k yaklaşık 6.64 olduğundan 7 gibi integer seçimi değerlendirilir. Bu “RAM kullanmaz” değildir, fakat exact string set'e göre çok daha kompakt olabilir.

Her positive gerçek membership değildir. Cache veya disk lookup öncesi filter, kesin yok sonucunda pahalı işi atlatır; maybe sonucunda asıl kaynağa sorar. Security authorization kararını yalnız Bloom positive'e bağlamak yanlıştır. False positive kabul edilebilir maliyet üretmeli; yetkisiz erişim üretmemeli.

Sizing capacity aşıldıkça bitler dolar, p büyür. Monitoring'de gerçek n ve false-positive örnekleri izle. Hash'lerin correlation'ı, farklı seed ile merge veya yanlış silme teorik modeli bozabilir. Persisted filter sürümünde hash family/seed ve kapasite parametrelerini sakla.

Temel: n iki kat, m sabit olduğunda p nasıl değişir? Orta: Simülasyonla false-positive oranını confidence interval ile ölç. İleri: Counting Bloom'da counter overflow/underflow ve duplicate deletion sözleşmesini belirle; filter metadata mismatch'i fail-safe ele al.

import hashlib
bits=[False]*128
def positions(value):
    return [int.from_bytes(hashlib.sha256((str(i)+":"+value).encode()).digest()[:8],"big")%128 for i in range(3)]
def insert(value):
    for p in positions(value): bits[p]=True
def maybe(value): return all(bits[p] for p in positions(value))
insert("docker")
assert maybe("docker")