High-throughput bloom filter design: systematic parameter selection and FPGA implementation

Date

2024-7

Author

Yitim, Efe Berkay

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

60
views

0
downloads

Cite This

Membership testing, a fundamental concept in computer science, involves checking whether an element belongs to a set. It plays a crucial role in algorithms, data structures, and various applications. Bloom Filters (BFs) are probabilistic data structures used for efficient membership testing. They rely on hash functions to map elements to positions in a fixed-size bit array. When testing for membership, BFs quickly determine if an element is likely in the set or definitely not. However, false positives can occur due to the many-to-one nature of hash functions. In this thesis, we propose a detailed model for designing BFs tailored to specific application parameters. We consider factors such as the number of strings in the set, string length, and acceptable false positive probability. Our approach aims to minimize memory usage while meeting application requirements. Unlike previous work, we account for the discrete block RAM structure of Field-Programmable Gate Arrays (FPGAs), which are commonly used for BF implementations. To this end, the first main contribution of the thesis is an analytical computation for the minimum memory required to support an application with a given false positive probability and string set size. The second main contribution is an algorithmic design space exploration method based on enumerating hash function and memory combinations for a given FPGA platform. The third contribution is a heavily pipelined implementation of Partitioned Bloom Filters (PBFs) with XOR-based hash functions. We demonstrate the benefits of our design approach and pipelined architecture through detailed FPGA implementation studies. Our work contributes to efficient BF design, especially for FPGA-based systems, enabling faster membership testing across various domains.

Subject Keywords

Bloom filter, FPGA, High-throughput, Hardware design

URI

https://hdl.handle.net/11511/110393

Collections

Graduate School of Natural and Applied Sciences, Thesis