Computationally efficient index generation unit using a Bloom filter

Efficient implementation of index generation functions is attracting significant interest due to the dynamic development of technologies such as Big Data and Internet of Things. These functions can be realized using a circuit called index generation unit. However, the better linear transformation of an index generation function is found, the larger auxiliary memory is used. Lately, the architecture that uses probabilistic data structure was proposed. However, it requires several independent hash functions. Selecting proper hash functions is a complex issue.

In this paper new architecture of index generation unit using a Bloom Filter was proposed. It addresses the issues of the previously proposed architectures, i.e.:
• as opposed to classical index generation unti1 the memory size does not increase as a function of the number of variables after linear transformation,
• as opposed to proposed previously architecture4 does not require several independent hash functions.

Furthermore, the hardware implementation of the most important part of proposed architecture was analysed, i.e. the modulo stage. Presented results of implementation using FPGA devices prove logic utilization efficiency of proposed architecture. Memory efficiency of the proposed architecture is achieved at the cost of small probability of the false positive result during the query if ”v ∈ S?”. Thus, we believe it can be used in all applications that accept this small probability.