BhBF: A Bloom Filter Using B-h Sequences for Multi-set Membership Query

doi:10.1145/3502735

	BhBF: A Bloom Filter Using B-h Sequences for Multi-set Membership Query
	Pei, Shuyu 1; Xie, Kun 1; Wang, Xin 2; Xie, Gaogang 3; Li, Kenli 1; Li, Wei 1; Li, Yanbiao 3; Wen, Jigang 4
	2022-10-01
发表期刊	ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
ISSN	1556-4681
卷号	16 期号:5 页码:26
摘要	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 Bh sequence-based Bloom filter (BhBF) for multi-set query, which supports four operations: insertion, query, deletion, and update. In BhBF, the set ID is encoded as a code in a Bh sequence. Exploiting good properties of Bh 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 BhBF, 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 BhBF. Our results from extensive experiments over two real datasets demonstrate that BhBF significantly advances state-of-the-art multi-set query algorithms.
关键词	Multi-set membership query bloom filter
DOI	10.1145/3502735
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[62025201] ; National Natural Science Foundation of China[61972144] ; NSF Electrical, Communications and Cyber Systems (ECCS)[1731238] ; NSF Electrical, Communications and Cyber Systems (ECCS)[2030063] ; NSF Communication and Information Foundations (CIF)[2007313] ; Hunan Provincial Innovation Foundation for Postgraduate Studies[CX20200437]
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Software Engineering
WOS记录号	WOS:000802146500009
出版者	ASSOC COMPUTING MACHINERY
引用统计	被引频次：2[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/19573
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Xie, Kun
作者单位	1.Hunan Univ, Coll Comp Sci & Elect Engn, Changsha 410082, Hunan, Peoples R China 2.SUNY Stony Brook, Dept Elect & Comp Engn, Stony Brook, NY 11794 USA 3.Chinese Acad Sci, Comp Network Informat Ctr, Beijing 100190, Peoples R China 4.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
推荐引用方式 GB/T 7714	Pei, Shuyu,Xie, Kun,Wang, Xin,et al. BhBF: A Bloom Filter Using B-h Sequences for Multi-set Membership Query[J]. ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA,2022,16(5):26.
APA	Pei, Shuyu.,Xie, Kun.,Wang, Xin.,Xie, Gaogang.,Li, Kenli.,...&Wen, Jigang.(2022).BhBF: A Bloom Filter Using B-h Sequences for Multi-set Membership Query.ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA,16(5),26.
MLA	Pei, Shuyu,et al."BhBF: A Bloom Filter Using B-h Sequences for Multi-set Membership Query".ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 16.5(2022):26.