bloom ne demek?

Bloom Algoritması (Bloom Filter)

Bloom filtresi, bir elemanın bir kümeye ait olup olmadığını test etmek için kullanılan olasılıksal bir veri yapısıdır. Temel amacı, bir elemanın kümede kesinlikle olmadığını söyleyebilmek ve kümede olabileceğini olasılıkla belirtmektir. Yani, yanlış pozitiflere (false positive) izin verirken, yanlış negatifleri (false negative) engeller. Bu özelliği sayesinde, büyük veri kümelerinde hızlı ve bellek tasarruflu aramalar için idealdir.

Nasıl Çalışır?

Bloom filtresi, aşağıdaki adımlarla çalışır:

1. Bit Dizisi (Bit Array): Belirli bir boyutta (m) bit içeren bir dizi ile başlar. Başlangıçta tüm bitler 0 olarak ayarlanmıştır.
2. Hash Fonksiyonları: K tane farklı hash fonksiyonu kullanılır (k < m). Bu fonksiyonlar, bir elemanı alıp, 0 ile m-1 arasında bir indeks değeri üretir.
3. Ekleme (Insertion): Bir elemanı kümeye eklemek için, eleman her bir hash fonksiyonundan geçirilir ve elde edilen indekslerdeki bitler 1 olarak ayarlanır.
4. Arama (Lookup): Bir elemanın kümede olup olmadığını kontrol etmek için, eleman yine her bir hash fonksiyonundan geçirilir. Eğer elde edilen tüm indekslerdeki bitler 1 ise, elemanın olası olarak kümede olduğu kabul edilir. Ancak, eğer herhangi bir indeksdeki bit 0 ise, elemanın kesinlikle kümede olmadığı söylenir.

Avantajları:

• Bellek Verimliliği: Kümedeki eleman sayısına göre nispeten az bellek kullanır.
• Hızlı Arama: Hash fonksiyonları sayesinde arama işlemleri çok hızlıdır.
• Basit Uygulama: Uygulaması kolaydır.

Dezavantajları:

• Yanlış Pozitifler (False Positives): Bir eleman kümede olmasa bile, tüm hash fonksiyonları ilgili bitleri 1 olarak işaretlemişse, algoritma elemanın kümede olduğunu söyleyebilir. Yanlış pozitif olasılığı, kullanılan bit sayısı (m) ve hash fonksiyonu sayısıyla (k) doğrudan ilişkilidir.
• Silme İşlemi Zorluğu: Standart Bloom filtrelerinde eleman silme işlemi doğrudan yapılamaz. Çünkü bir bitin 1 olması, birden fazla elemanın o bite karşılık gelmesi anlamına gelebilir. Silme işlemi için alternatif yöntemler (örneğin, sayıcı tabanlı Bloom filtreleri) kullanılabilir.

Kullanım Alanları:

• Veritabanı Sistemleri: Mevcut olmayan verileri hızlı bir şekilde filtrelemek için. (https://www.nedemek.page/kavramlar/veritabanı%20sistemleri)
• Web Önbellekleme: Daha önce erişilmemiş URL'leri filtreleyerek önbelleğe alma maliyetini düşürmek için. (https://www.nedemek.page/kavramlar/web%20önbellekleme)
• Ağ Yönlendirme: Zararlı IP adreslerini filtrelemek için. (https://www.nedemek.page/kavramlar/ağ%20yönlendirme)
• Spam Filtreleme: İstenmeyen e-postaları filtrelemek için. (https://www.nedemek.page/kavramlar/spam%20filtreleme)
• Kripto Para Birimleri: Sahtekarlığı tespit etmek için (Örn: Double Spending).

Özetle, Bloom filtresi, özellikle bellek kısıtlamalarının olduğu ve kesin doğruluğun çok kritik olmadığı durumlarda kullanışlı bir araçtır.