A Scalable Bloom Filter Implementation in Java
Description
This project is an implementation of a scalable Bloom filter in Java. In the published paper we give a brief introduction into the general concept of Bloom filters and describe our developed implementation. We show through benchmarks against publicly available variants that our implementation fulfills the anticipated requirements for production level deployment.
The program for creating benchmarks, the evaluated data which the paper references and the scalable Bloom filter implementation itself can be downloaded from this page. The paper was published and presented at the university of applied sciences Bremen on the 29. January 2020. The slides are available for download.
The downloadable software of this project is licensed under the Apache License version 2.
Abstract
Bloom filters are a widely used data structure as they allow for very efficient implementations regarding space usage and runtime requirements. Over the past decades there have been numerous proposals for adjusting the core idea of Bloom filters in order to allow removal and counting of elements as well as other features. However, many available concepts and implementations do not allow scaling by dynamically changing set sizes. In this paper we propose our implementation of a scalable Bloom filter in the programming language Java based on the theoretical work published by Almeida et al. in 2007. Furthermore, we conduct measurements on how well our filter performs compared to other publicly available (static) implementations. We can show through benchmarks that our implementation yields competitive results with regard to runtime and false positive rates while facilitating dynamic scaling for cases with considerable set growth.