In:
ACM Transactions on Knowledge Discovery from Data, Association for Computing Machinery (ACM), Vol. 16, No. 5 ( 2022-10-31), p. 1-26
Abstract:
Multi-set membership query is a fundamental issue for network functions such as packet processing and state machines monitoring. Given the rigid query speed and memory requirements, it would be promising if a multi-set query algorithm can be designed based on Bloom filter (BF), a space-efficient probabilistic data structure. However, existing efforts on multi-set query based on BF suffer from at least one of the following drawbacks: low query speed, low query accuracy, limitation in only supporting insertion and query operations, or limitation in the set size. To address the issues, we design a novel B h sequence-based Bloom filter (B h BF) for multi-set query, which supports four operations: insertion, query, deletion, and update. In B h BF, the set ID is encoded as a code in a B h sequence. Exploiting good properties of B h sequences, we can correctly decode the BF cells to obtain the set IDs even when the number of hash collisions is high, which brings high query accuracy. In B h BF, we propose two strategies to further speed up the query speed and increase the query accuracy. On the theoretical side, we analyze the false positive and classification failure rate of our B h BF. Our results from extensive experiments over two real datasets demonstrate that B h BF significantly advances state-of-the-art multi-set query algorithms.
Type of Medium:
Online Resource
ISSN:
1556-4681
,
1556-472X
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2022
detail.hit.zdb_id:
2257358-6
Permalink