Bitget App
Akıllı işlemler
Kripto Satın AlPiyasalarİşlem YapVadeli İşlemlerCopyBotsKazan

Bloom Filtresi

Gelişmiş
share

Bloom filtresi, bir elemanın bir kümenin parçası olup olmadığını verimli bir şekilde test etmek için tasarlanmış olasılıksal bir veri yapısıdır. Burton Howard Bloom tarafından 1970 yılında icat edilmiş ve minimum bellek tüketimi ile büyük veri kümelerini yönetme yeteneği nedeniyle bilgisayar biliminde temel bir araç haline gelmiştir. Hash tabloları veya ikili arama ağaçları gibi geleneksel veri yapılarının aksine bloom filtresi, bir eleman kümede olmadığında kesin bir cevap sağlayabilir, ancak bir eleman olduğunda yalnızca olasılıklı bir cevap sağlayabilir. Bu, yanlış pozitifler mümkün olsa da yanlış negatiflerin mümkün olmadığı anlamına gelir.

Bloom filtresinin temel konsepti, hepsi başlangıçta 0 olarak ayarlanmış bir dizi bit ve bir dizi karma fonksiyon etrafında döner. Bir öğe çiçeklenme filtresine eklendiğinde, bit dizisinde birden fazla konum oluşturmak için hash işlevlerin her birinden geçirilir. Bu pozisyonlardaki bitler daha sonra 1'e ayarlanır. Bir elemanın kümede olup olmadığını kontrol etmek için, aynı fonksiyonlar kullanılarak tekrar hash’lenir ve ilgili bitler kontrol edilir. Bu pozisyonlardaki tüm bitler 1 ise, elemanın kümede olabileceği düşünülür; bitlerden herhangi biri 0 ise, eleman kesinlikle kümede değildir.

Bloom filtrelerinin önemli avantajlarından biri de alan verimliliğidir. Özellikle eleman sayısı arttıkça, aynı görev için diğer veri yapılarına kıyasla önemli ölçüde daha az bellek gerektirirler. Örneğin, kümedeki eleman sayısından bağımsız olarak %1 yanlış pozitif olasılığı elde etmek için eleman başına 10 bitten daha azına ihtiyaç vardır. Bu, bloom filtrelerini özellikle ağ yönlendiricileri, veritabanı sistemleri ve dağıtılmış sistemler gibi bellek kullanımının kritik bir sorun olduğu uygulamalarda kullanışlı hale getirir.

Bununla birlikte, bloom filtreleri belirli sınırlamalarla birlikte gelir. Birden fazla eleman tarafından ayarlanan bitlerin temizlenmesi yanlış negatiflere yol açacağından, kümeden eleman çıkarılamaması birincil dezavantajdır. Bu sorunu çözmek için, her bir bitin kaç kez ayarlandığının sayımını tutarak öğelerin kaldırılmasına olanak tanıyan sayılı bloom filtreleri gibi varyantlar geliştirilmiştir. Ek olarak, yanlış pozitif oranı daha fazla eleman eklendikçe artar, bu da bit dizisinin boyutunun ve hash fonksiyonlarının sayısının beklenen eleman sayısına ve kabul edilebilir yanlış pozitif oranına göre dikkatlice seçilmesi gerektiği anlamına gelir.

Pratik uygulamalarda, bloom filtreleri çeşitli alanlarda yaygın bir kullanım alanı bulmuştur. Örneğin Bitcoin'de, kullanıcıların adreslerini açıklamadan işlemleri sorgulamalarına izin vererek Basitleştirilmiş Ödeme Doğrulama (SPV) istemcilerinde gizliliği artırmak için kullanılırlar. Akamai gibi içerik dağıtım ağları, önbellek depolamasını verimli bir şekilde yönetmek için bloom filtreleri kullanır ve gereksiz veri alımlarından kaçınarak sunucular üzerindeki iş yükünü azaltır. Olasılıksal yapılarına ve sınırlamalarına rağmen, bloom filtreleri verimli ve ölçeklenebilir sistemlerin tasarımında paha biçilmez bir araç olmaya devam etmektedir.

Uygulamayı İndir
Uygulamayı İndir