A novel and precise false positive probability computation for bloom filters implemented with universal hash functions
Evrensel özet fonksiyonları ile gerçekleştirilmiş bloom filtrelerİ için yeni ve hassas bir yanlış pozitif olasılığı hesaplaması
- Tez No: 764766
- Danışmanlar: PROF. DR. ŞENAN ECE SCHMİDT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Elektrik ve Elektronik Mühendisliği, Computer Engineering and Computer Science and Control, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 85
Ö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.
Özet (Çeviri)
Bloom Filters (BF) are multiple-hashing data structures that are widely used in membership testing applications. The many-to-one nature of the BF hashing results in false positive outcomes which have to be further processed at a performance cost. The computation of the false positive probability of BFs is carried out under the assumption of uniform and independent hash functions. To the best of our knowledge, all previous work in the literature assume that the hash functions are uniform and independent without verifying if that is the case in reality. This thesis focuses on the hash function uniformity and independence for BFs with universal H3 functions. To this end, we propose a formal framework for defining and quantifying the uniformity and independence for H3 hash functions in BFs. Furthermore, we define a formal description of the many-to-one outcomes of H3 hash functions. We then use this framework to precisely compute the false positive probability for BFs with H3 hash functions which might not be necessarily uniform or independent. We verify our precise false positive expression with a hardware test bed that can execute 2 · 108 membership queries per second. We perform structured tests to evaluate the effect of losing uniformity and independence at different levels among the H3 hash functions. Furthermore, we evaluate the results of our expression for a range of parameters.
Benzer Tezler
- Train set complexity tunning for imbalance learning
Dengesiz öğrenme için eğitim seti karmaşıklığının ayarlanması
MEHMET ULAŞ
Yüksek Lisans
İngilizce
2024
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. MEHMET ALİ ERGÜN
- Online anomaly detection in the Neyman-Pearson hypothesis testing framework
Neyman-Pearson hipotez testi çerçevesinde çevrimiçi anomali tespiti
BAŞARBATU CAN
Doktora
İngilizce
2022
Elektrik ve Elektronik MühendisliğiSabancı ÜniversitesiElektronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ HÜSEYİN ÖZKAN
- Hızlı hastalık teşhis testlerinin bilgisayar tabanlı otomatik okunması ve hekimlerin e-rapor ile bilgilendirilmesi
Automatic reading of rapid diagnostic tests and informing the clinicians with e-report
OSMAN SEMİH KAYHAN
Yüksek Lisans
Türkçe
2016
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
DOÇ. DR. İSA YILDIRIM
YRD. DOÇ. DR. HAYDAR ÖZKAN
- Point-based matching of oblique ımages acquired from airplane and uav platforms
Uçak ve iha platformlarından elde edilen eğik görüntülerin nokta tabanlı eşleştirilmesi
SILA BAŞ
Yüksek Lisans
İngilizce
2020
Jeodezi ve FotogrametriHacettepe ÜniversitesiGeomatik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ ÖZGÜN OK
- Multivariate analysis of genomic in-silico pathogenicity predictors
Genomik in-siliko patojenite tahmin araçlarının çok değişkenli analizi
EYLÜL AYDIN
Yüksek Lisans
İngilizce
2024
BiyoistatistikAcıbadem Mehmet Ali Aydınlar ÜniversitesiGenom Çalışmaları Ana Bilim Dalı
PROF. ÖZDEN HATIRNAZ NG
DR. ÖĞR. ÜYESİ ÖZKAN ÖZDEMİR