Bloom Filter als Werkzeug zur Organisation komplexer und großer Geo-Daten

• Antragsteller: Professor Dr. Martin Werner
• Fachliche Zuordnung: Datenmanagement, datenintensive Systeme, Informatik-Methoden in der Wirtschaftsinformatik ; Geodäsie, Photogrammetrie, Fernerkundung, Geoinformatik, Kartographie
• Förderung: Förderung seit 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 507196470

In diesem Projekt wollen wir uns damit beschäftigen, wie Bloom Filter angepasst und erweitert werden müssen, um auch sehr große Schlüsselmengen („Big Data“) darstellen zu können. Dabei verfolgen wir drei Ziele: Für das erste Projektziel wollen wir Hindernisse abbauen, die einen Einsatz von Bloom-Filtern für besonders große Datenmengen derzeit erschweren. Dabei sind bei der Konfiguration von Bloom-Filtern enge Grenzen gesetzt, zum Beispiel muss die Anzahl der Hash-Funktionen derzeit ganzzahlig sein, die Länge der Filter sollte eine Zweierpotenz sein und Anfragen haben in der Regel gleiche Fehlerwahrscheinlichkeit. Ferner ist eine Verwendung der Bloom-Filterdatenstrukturen über den einfachen Element-Test hinaus wenig verbreitet. In diesem Zusammenhang wollen wir basierend auf einer Vielzahl an Vorarbeiten eine systematische Untersuchung in diesem Projekt durchführen und so die möglichen Einsatz-Szenarien für den Bloom-Filter signifikant erweitern. In einem zweiten Ziel wollen wir eine Benchmarking-Umgebung implementieren, in der die theoretischen Entwicklungen im Lichte von tatsächlicher Hardware evaluiert werden können. Dabei sollen auch Experimente im Kontext von Spezialhardware (z. B. FPGAs und GPUs) Möglichkeiten für die zukünftige Entwicklung exemplarisch aufzeigen. Ein drittes Projektziel beschäftigt sich mit der Verwendung von Bloom-Filtern als Datenstruktur für komplexe Geodaten. Dabei beschäftigen wir uns insbesondere mit dünn besetzten 2D und 3D-Daten aus der Geoinformatik und mit dem Einsatz von Bloom-Filtern als Hilfsdatenstruktur in Indexstrukturen wie Bounding Volume Hierarchies (BVH’s) oder R*-Bäumen. Insgesamt trägt das Projekt damit zur Konsolidierung der Theorie von Bloom-Filtern und einer Anpassung an die komplexer werdenden Einsatzumgebungen für solche Datenstrukturen bei.

• DFG-Verfahren: Sachbeihilfen