FBF: Bloom Filter for Fuzzy Membership Queries on Strings

摘要

Bloom filters are space efficient, probabilistic data structures for membership queries with low false positives and zero false negatives. They are widely used in the field of big data, networking, bio-informatics, cloud computing and IoT. However, a standard bloom filter does not support fuzzy membership queries. To overcome this limitation, we propose a novel algorithm using locality sensitive hashing on strings which extends the capability of a bloom filter to support fuzzy queries and calculate a score indicating its degree of similarity with the dataset. Experiments are performed to analyze false positive and false negative rates along with space requirements, time taken to serve a query and time taken to build the data structure. The proposed algorithm is benchmarked on two real world datasets where it outperforms all the baselines while maintaining all the advantages of a standard bloom filter.