Investigation on bloom filter and implementation of 3k combined parallel tiger bloom filter design

摘要

Bloom is an efficient data structure technique. Initially it was used in intelligent dictionaries and spell check applications. Its ability for dynamic membership querying and information compaction attracted huge research. Various optimization models of bloom filter for diverse applications were suggested and hence many bloom filter variants emerged. We present our investigation on bloom filter and introduce a new variant of bloom filter with 3k combined parallel design, first of its kind which uses a highly secure and collision resistant modified tiger hash with compact mapping using LFSR counter arrays. The design has been implemented and tested using a Xilinx 65 nm Virtex-5 field programmable gate array as the target technology and the results are compared by replacing the hashing unit with widely used universal H3 hash function and also relatively compared with the other possible hash functions and bloom filters. The performance matrices of the proposed design are false positive ratio, compactness and speed. The design is hardware based and suitable for networking and secure querying applications.