中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
BhBF: A Bloom Filter Using B-h Sequences for Multi-set Membership Query

文献类型：期刊论文

作者Pei, Shuyu2; Xie, Kun2; Wang, Xin1; Xie, Gaogang4; Li, Kenli2; Li, Wei2; Li, Yanbiao4; Wen, Jigang3
刊名ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
出版日期2022-10-01
卷号16期号:5页码:26
关键词Multi-set membership query bloom filter
ISSN号1556-4681
DOI10.1145/3502735
英文摘要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.
资助项目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记录号WOS:000802146500009
出版者ASSOC COMPUTING MACHINERY
源URL[http://119.78.100.204/handle/2XEOYT63/19572]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Xie, Kun
作者单位1.SUNY Stony Brook, Dept Elect & Comp Engn, Stony Brook, NY 11794 USA
2.Hunan Univ, Coll Comp Sci & Elect Engn, Changsha 410082, Hunan, Peoples R China
3.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China
4.Chinese Acad Sci, Comp Network Informat Ctr, 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.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。