Bloom Filter
Bir öğenin kümede kesinlikle olmadığını hızlı söyleyebilen, var olduğunu söylediğinde false positive üretebilen olasılıksal veri yapısı.
Veri Yapısı Bağlamı
Bit dizisi ve birden fazla hash fonksiyonu kullanır. LSM tree, cache ve network sistemlerinde gereksiz disk veya uzak sorguları azaltabilir.
Karmaşıklık ve Bellek Sınırı
Klasik Bloom filter false negative üretmez ancak silme doğrudan desteklenmez; counting Bloom filter gibi varyantlar farklı trade-off taşır.
İlişkili Veri Yapıları
- Hash Function
- LSM Tree
- False Positive
- Probabilistic Data Structure