Olasılıksal veri yapıları arasında bloom filtresi ve cuckoo filtre, üyelik sorgusunda bellek verimliliğiyle öne çıkar; ancak bu iki yapının bloom filter cuckoo filter karşılaştırması yapıldığında aralarındaki farklar beklenenden daha derin çıkar. Bloom filtresi, m bit uzunluğunda bir bit dizisi üzerinde k bağımsız hash fonksiyonu çalıştırarak çalışır. Bir eleman eklendiğinde k farklı bit konumu 1'e ayarlanır. Üyelik sorgusunda aynı k konum kontrol edilir; hepsi 1 ise eleman muhtemelen mevcuttur. Yanlış pozitif oranı (FPR) şöyle ifade edilir: FPR ≈ (1 - e^(-kn/m))^k Burada n eklenen eleman sayısıdır. k değeri için optimum noktası k = (m/n) × ln(2) formülüyle hesaplanır; bu değerde FPR minimize edilir. m/n = 10 bit/eleman durumunda ~%1 FPR, m/n = 20 bit/eleman durumunda ~%0.01 FPR elde edilir. Bloom filtresinin temel sınırlaması silme desteğinin bulunmaması ve FPR'ın eleman sayısıyla monoton artmasıdır. Counting bloom filtresi silme sorununu çözmekle birlikte bit başına belleği 4-8 kata kadar artırır. Cuckoo filtre, cuckoo hashing üzerine inşa edilmiştir. Her kova iki pozisyondan birine yerleştirilebilir: birincil pozisyon h1(x) ve alternatif pozisyon h1(x) XOR h2(fingerprint(x)). Doluluk oranı %95'i aştığında insert başarısız olabilir. Bloom filter cuckoo filter karşılaştırmasında kritik avantaj silme desteğidir: parmak izi (fingerprint) doğrudan kovadan silinebilir. Bellek ayak izi açısından: - Bloom filtresi: FPR = %1 için ~9.6 bit/eleman - Cuckoo filtresi: FPR = %1 için ~8 bit/eleman (4-bit fingerprint, her kovada 4 girdi) - Cuckoo filtresi: FPR = %0.1 için ~12 bit/eleman Dolayısıyla düşük FPR hedeflerinde cuckoo filtresi genellikle daha verimlidir. Arama karmaşıklığı O(k) bloom'da sabit kalırken, cuckoo filtrede O(1) amortized olarak iki kova kontrolüyle gerçekleşir. Yazma işleminde cuckoo filtresi yer değiştirme (eviction) zinciri nedeniyle worst-case maliyeti artabilir. Pratik seçim kriterleri şunlardır: Silme gereksinimi varsa cuckoo filtresi, yüksek dolulukta tahmin edilebilir davranış öncelikliyse bloom filtresi tercih edilebilir. Redis'in RedisBloom modülünde her ikisi de desteklenir; Cassandra ve HBase ise write path optimizasyonu için bloom filtresi kullanır.