A novel and precise false positive probability computation for bloom filters implemented with universal hash functions

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Bilimleri Enstitüsü, ELEKTRİK VE ELEKTRONİK MÜHENDİSLİĞİ ANABİLİM DALI, Türkiye

Tezin Onay Tarihi: 2022

Tezin Dili: İngilizce

Öğrenci: FURKAN KOLTUK

Danışman: ŞENAN ECE SCHMİDT

Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu

Özet:

Bloom Filtreleri (BF), üyelik testi uygulamalarında yaygın olarak kullanılan çoklu özetleme fonksiyonu içeren veri yapılarıdır. Bloom Filterelerindeki özet fonksiyonlarının çoğuldan tekile yapısı yanlış pozitif çıktılara ve neticede performans kayıp- larına sebep olur. Literatürdeki Bloom Filtresi yanlış pozitif olasılığı hesaplamaları tekdüze ve bağımsız özet fonksiyonları varsayar. Bildiğimiz kadarıyla, literatürdeki tüm çalışmalar herhangi bir doğrulama sağlamaksızın özet fonksiyonlarının tekdüze ve bagımsız olduğunu varsaymaktadır. Bu tez çalışması, H3 özet fonksiyonuna sahip BF'lerin tekdüzeliğine ve bağımsız- lığına odaklanmaktadır. Bu amaçla, bu çalışmada H3 BF'ler için tekdüzeliği ve bağımsızlığı kantitatif olarak tanımlayan muntazam bir çerçeve sunulmaktadır. Buna ek olarak, H3 özet fonksiyonlarının çoğuldan tekile oluşları muntazam bir tanım ile sunulmuştur. Önerilen çerçeve daha sonrasında tekdüze ya da bağımsız olma koşulu olmaksızın, H3 özet fonksiyonlarına sahip BF'lerin yanlış pozitif olasılıklarının isabetli şekilde hesaplanmasında kullanılmıştır. Bu yanlış pozitif hesabının doğrulaması için donanım üzerinde saniyede 2 × 108 üyelik kontrolü gerçekleştirebilen bir test yatağı gerçeklenmiştir. Tekdüzeliğin ve bağımsızlığın farklı seviyelerde kaybının etkilerini incelemek için yapılandırılmış testler gerçekleştirilmiştir. Yanlış pozitif hesabı farklı BF parametre aralıklarında değerlendirilmiştir.