Çok büyük miktarda veri([Big Data | Dev Veri]) üzerinde istatistiksel analiz ve veri madenciliği günümüzde büyük bir önem kazanmış durumda. Bu işlemleri gerçeklemek için oldukça maliyetli sistemlere(Hadoop, MapReduce) ihtiyaç duyuyoruz. Olasılıksal veri yapıları bu noktada öne çıkıyorlar çünkü ham veri hakkında yaklaşık/tahmini bilgiye sahip olmamızı görece çok düşük maliyetle karşılayabiliyorlar. Olasılıksal veri yapılarını kullanarak ham veri için aşağıdaki sorulara yaklaşık yanıtlar verebiliyoruz.
Olasılıksal veri yapıları hakkında daha fazla bilgiye sahip olmak için bu veri yapılarını oldukça güzel özetleyen şu yazıyı okumanızı tavsiye ederim. Ben ise bu yazıda yalnızca üyelik sorgusuna yanıt verebilen Bloom Filtresinden bahsedeceğim.
Bloom Filtresi Burton Howard Bloom tarafından 1970 yılında bulunmuş olan olasılıksal bir veri yapısı. Bu veri yapısı ile bir elemanın bir küme içinde yer alıp almadığını düşük maliyetle sorgulayabiliyoruz. Bu veri yapısına olasılıksal adı veri verilmesinin nedeni verdiği yanıtlar arasında false positive sonuçların olabilmesi. Yani filtre "Evet, eleman bu kümede bulunuyor." yanıtını verirse eleman bu kümede olabilir de olmayabilir de... Fakat bunun tam tersi, yani false negative yanıtlar bu filtre için geçerli değil. Başka bir deyişle eğer Bloom Filtresi "Hayır, eleman bu kümede bulunmuyor." derse mutlaka doğru söylüyordur. Düzgün yapılandırma ile false positive oranını %1'in altında tutabiliyoruz. Böylece Bloom Filtresi özellikle veritabanı sorgularından önce kullanıldığında gereksiz disk erişiminin önüne geçebiliyor. BigTable ve Cassandra içerisinde bu şekilde bir kullanım mevcut.
Boş bir Bloom Filtresi tüm elemanları 0 olan m bitten oluşan bir bit dizisidir. Tanımlanmış olan k farklı hash(özet) fonksiyonunun her biri verilen elemanı m dizi indisinden birine rastgele olarak yerleştirir.
Filtreye yeni bir eleman eklemek için elemanı k farklı özet fonksiyonundan geçirerek k farklı indis elde edin ve bit dizisinin bu indislerdeki değerlerini 1 olarak setleyin.
Bir elemanın üyeliğini sorgulamak için elemanı k farklı özet fonksiyonundan geçirerek k farklı indis elde edin. İndislerdeki değerlerden en az biri 0 ise bu eleman veri kümesinde bulunmamaktadır. Değerlerin tümü 1 ise elemanın üyeliği konusunda kesin bir yargıya varılamaz. Çünkü elde edilen indisler farklı elemanların eklenmesi sırasında setlenmiş olabilirler. Önceden de bahsettiğim gibi bu duruma false positive diyoruz.
Şu bağlantıda false positive oranının(p) nasıl hesaplanacağına dair matematiksel formüller ve çeşitli m(bit dizisinin boyu), n(eleman sayısı) ve k(özet fonksiyonu sayısı) değerleri için p değerinin ne olacağına dair tablolar var. Göreceğiniz üzere bu değerler düzgün şekilde seçildiğinde p değeri oldukça küçülüyor.
stream-lib isimli Github deposu olasılıksal veri yapılarının pek çoğunun Java ile gerçeklemesini içeriyor. Bloom Filter da bu gerçeklemelerden biri ve README dosyasında bu kod için Apache Cassandra projesinden faydalanıldığı belirtilmiş. Ayrıca özet fonksiyonu için MurmurHash kullanıldığını da buradan görebilirsiniz.
Follow me on Twitter