Bloom Filter

Hey whats up? I finished my bachelor thesis this January 🙂 Now i am studying my master in Ingolstadt.

This is a german paper about a Bloom Filter. Hope u have fun reading!

Link: Bloom Filter paper 1.8.0

Bloom Filter – eine probabilistische Datenstruktur

Dieser Artikel behandelt die Funktionsweise eines

Bloom Filters. Dabei wird insbesondere auf die ma-

thematischen Grundlagen des Bloom Filters Wert

gelegt und dieses System anhand von beiliegenden

Beispielen aufgezeigt. Mit einer speziellen Daten-

struktur kann durch dieser Methode die Performance

in vielen Anwendungen deutlich gesteigert werden.

Heutzutage sind Bloom Filter in mehreren Daten-

banken und Browsern integriert und verringert die

Wartezeit für Benutzer und Systeme. Durch die mini-

malistische Implementierung steht der Bloom Filter

in zahlreichen Programmiersprachen zur Verfügung

und kann bei einer praktischen Anwendung als Modul

in der Datenzugriffsschicht eingegliedert werden.

4 Fazit

Der Bloom Filter ist eine simple und effektive Imple-

mentierung. Durch die probabilistische Datenstruk-

tur können Anfragen effizient und zeitsparend prozessiert werden.

In fast keinem Anwendungsfall konnte der Bloom Filter einen Nachteil mit sich ziehen.

Insbesondere im Big-Data Bereich lohnt sich die Verwendung eines Bloom lters und

der daraus resultierende Performance- und Zeitgewinn. Schon jetzt ist der

Filter in vielen Datenbanken integriert und sollte bei

Bedarf auf jeden Fall benutzt werden.

Literatur

[1]

Ashwin Lall and Mitsunori Ogihara – The Bitwise Bloom Filter

[2]

Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, and George Varghese – An Improved Constructionfor Counting Bloom Filters. PhD thesis, Harvard.

[3]

Alan J. Hu and Andrew K. Martin, editors. – Formal Methods in Computer-Aided Design

[4]

Pei Cao Bloom Filters – the math

[5]

Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, and Yihui Tang – ONTHEFALSEPOSITIVERATEOFBLOOMFILTERS

[6]

Tim Kaler – Cache Ecient Bloom Filters for Shared MemoryMachines