BMF: An Indexing Structure to Support Multi-element Check

摘要

Standard Bloom Filter is an efficient structure to check element membership with low space cost and low false positive rate. However, the standard Bloom Filter assumes that all elements belong to a single set. When given multiple sets of elements, it cannot efficiently check whether or not multiple input elements belong to the same set, called multi-element check. To support the multi-element check, in this paper, we design a new data structure, namely Bloom Multi-filter (BMF). BMF maintains an array of integer numbers to support (1) the insertion of multiple sets of elements into BMF and (2) the lookup to answer multi-element check. We propose four techniques to improve the BMF and optimize the false positive rate. We conducted intensive experiments to study the tradeoff between BMF's space cost and lookup precision. Our experimental results indicate that BMF greatly outperforms the standard bloom filters with around 9.82 folds of lower false positive rate.