- Bachelorarbeit -

Beschreibung:

Mit Hash-Filtern kann schnell bestimmt werden, ob ein Element in einer Menge von Schlüsseln möglicherweise oder mit Sicherheit nicht vorhanden ist.

In dieser Bachelor-/Masterthesis wollen wir verschiedene Ansätze für Hash-Filter mit unterschiedlichem Platzbedarf untersuchen, welche durch GPUs beschleunigt werden. Eine Auswahl an Hashing-Ansätzen sind: Bloom-Filter [1], Cuckoo [1], Morton filters [2] und Vacuum filters [3].

[1] B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher. Cuckoo filter: Practically better than Bloom. In Proc. of the ACM CoNEXT, 2014.

[2] Alex D. Breslow, Nuwan S. Jayasena, Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity, VLDB, 2018.

[3] Minmei Wang, Mingxun Zhou, Chen Qian, Shouqian Shi, Vacuum Filters: More Space-Efficient and Faster Replacement for Bloom and Cuckoo Filters, VLDB, 2019

Anforderungen/Kenntnisse:
OpenCL, GPU-Programmierung, Hashtabellen ...

Bearbeitung:
Malte Sauer

Ergebnis:
Die Ausarbeitung kann im Institut für Informationssysteme angefordert werden.

Betreuung:

Prof. Dr. rer.nat. habil. Sven Groppe
Institut für Informationssysteme
Ratzeburger Allee 160 ( Gebäude 64 - 2. OG)
23562 Lübeck
Telefon: 0451 / 3101 5706