Bloom filtresi
Bloom filtresi, bilgisayarların belirli bir öğenin bir kümede bulunup bulunmadığını görmesini sağlayan bir veri yapısıdır. Bloom filtreleri bunu yapmak için hash fonksiyonlarını kullanır. Eklenen her eleman için bir hash değeri hesaplanır. Yeni bir eleman eklendiğinde, hash değeri kümedeki diğer elemanlarınki ile karşılaştırılır. Bloom filtresi olasılıksal bir veri yapısıdır. Yanlış pozitif elde etmek mümkündür, ancak yanlış negatif elde etmek mümkün değildir. Başka bir deyişle, bir sorgu ya "muhtemelen kümede" ya da "kesinlikle kümede değil" sonucunu verir. Elemanlar kümeye eklenebilir, ancak çıkarılamaz. Eklenen her eleman için yanlış pozitif alma olasılığı artar.
Edward Bloom 1970 yılında Bloom filtresini önermiştir. Makalede Bloom, bir satırın sonundaki kelimeleri tirelemek için bir algoritma olduğunu varsaymaktadır. Örneğe göre, çoğu kelime basit tireleme modellerine sahiptir. Ancak kelimelerin yaklaşık %10'u doğru kuralı bulmak için zaman alıcı aramalar gerektirmektedir. Bu örnekte yaklaşık 500.000 kelimenin tirelenmesi söz konusuydu. "Normal" hatasız hashing tekniklerini kullanarak tireleme kalıplarını depolamanın çok fazla bellek gerektireceğini gördü. Kendi tekniğini kullanarak çoğu aramayı ortadan kaldırabileceğini keşfetti. Örneğin, ideal hatasız bir hash için gereken boyutun yalnızca %15'i kadar bir hash alanı yine de disk erişimlerinin %85'ini ortadan kaldırmaktadır.
Daha genel olarak, kümedeki öğelerin boyutundan veya sayısından bağımsız olarak %1 yanlış pozitif olasılığı için öğe başına 10 bitten daha azı gereklidir.
Sorular ve Yanıtlar
S: Bloom filtresi nedir?
C: Bloom filtresi, bilgisayarların belirli bir öğenin bir kümede bulunup bulunmadığını görmesini sağlayan bir veri yapısıdır. Bunu yapmak için eklenen her öğenin karma değerini hesaplayarak ve bunu kümedeki diğer öğelerle karşılaştırarak karma işlevlerini kullanır.
S: Bloom filtresi ne tür bir veri yapısıdır?
C: Bloom filtresi olasılıksal bir veri yapısıdır, yani yanlış pozitifler elde etme olasılığı vardır ancak yanlış negatifler elde etme olasılığı yoktur.
S: Bloom filtresini kim önerdi?
C: Edward Bloom, Bloom filtresini 1970 yılında önermiştir.
S: Edward'ın tekniğini kullanmak için verdiği örnek neydi?
C: Edward'ın örneği yaklaşık 500.000 kelimeyi tirelemekti; tekniğini kullanarak çoğu aramayı ortadan kaldırabileceğini ve disk erişimlerini %15 oranında azaltabileceğini buldu.
S: %1 yanlış pozitif olasılığı için eleman başına kaç bit gereklidir?
C: Kümedeki öğelerin boyutundan veya sayısından bağımsız olarak %1 yanlış pozitif olasılığı için öğe başına 10 bitten daha azı gereklidir.
S: Eklendikten sonra bir bloom filtresinden öğeleri çıkarmak mümkün müdür?
C: Hayır, elemanlar sadece kümeye eklenebilir ancak çıkarılamaz.
S: Daha fazla eleman eklemek yanlış pozitif sonuç alma olasılığını artırır mı yoksa azaltır mı?
C: Daha fazla öğe eklemek yanlış pozitif sonuç alma olasılığını artırır.
