The Bloom Filter as a Tool for Organizing Complex Big Geospatial Data

• Applicant: Professor Dr. Martin Werner
• Subject Area: Data Management, Data-Intensive Systems, Computer Science Methods in Business Informatics ; Geodesy, Photogrammetry, Remote Sensing, Geoinformatics, Cartography
• Term: since 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 507196470

In this project, we want to address how Bloom filters need to be adapted and extended to represent very large key sets ("Big Data"). In doing so, we pursue three goals: For the first project goal, we want to remove obstacles that currently make it difficult to use Bloom filters for particularly large data sets. There are tight constraints on the configuration of Bloom filters, for example, the number of hash functions must currently be an integer, the length of the filters should be a power of two, and queries usually have equal error probability. Furthermore, there is little use of Bloom filter data structures beyond simple element testing. In this context, based on a large body of prior work, we aim to conduct a systematic investigation in this project, significantly expanding the possible usage scenarios for the Bloom filter. In a second goal, we want to implement a benchmarking environment in which theoretical developments can be evaluated in light of actual hardware and exemplify possibilities for future development in the context of specialized hardware (e.g., FPGAs and GPUs). A third project goal deals with the use of Bloom filters as a data structure for complex geospatial data. In particular, we are concerned with sparse 2D and 3D data from geoinformatics and with the use of Bloom filters as an auxiliary data structure in index structures such as bounding volume hierarchies (BVH's) or R*-trees. Overall, the project thus contributes to the consolidation of the theory of Bloom filters and an adaptation to the increasingly complex deployment environments for such data structures.

• DFG Programme: Research Grants