Bloom Filter Based Associative Deletion

摘要

Bloom filters are widely-used powerful tools for processing set membership queries. However, they are not entirely suitable for many new applications, such as deleting one attribute value according to another attribute value for a set of data objects/items with two correlated attributes. In this paper, we introduce a concept for such an operation, called the associative deletion. To realize this operation, we propose a new Bloom filter data structure, named IABF (Improved Associative deletion Bloom Filter), which keeps the association information on the two correlated attributes of items in the given data set. Based on IABF, we present an algorithm to perform associative deletions, which can be applied to both normal data and streaming data. To further accelerate the operation, we also illustrate a hardware coprocessor implementation for a crucial component of the algorithm. Detailed theoretical analysis and experimental results demonstrate that the presented IABF technique can accurately process associative deletions with controlled false positive and negative rates.