基于布隆过滤器的精确匹配算法设计与实现

作     者：王鹏超 杜慧敏 曹广界 杜琴琴 丁家隆 WANG Peng-chao;DU Hui-min;CAO Guang-jie;DU Qin-qin;DING Jia-long

作者机构：西安邮电大学电子工程学院西安710061 

基　　金：国家自然科学基金(90607008 60976020) 陕西省政府基金(2011k06-47)资助 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2015年第42卷第S1期

页      码：429-434页

摘      要：针对布隆过滤器技术存在将不属于该集合的某元素误判为属于该数据集合(假阳性)和元素删除困难的问题,提出了CAM(内容可寻址存储器)来进行二级匹配。与直接将字符串存储在CAM的单级匹配模式不同,提出将布隆过滤器的k个哈希值存入CAM,从而判断某元素是否真正属于这个集合,从而达到精确匹配,且易于删除元素。对算法在Snort2.9规则库下的分析结果表明,相较于单级CAM查找,所设计的两级匹配模式在假阳率为0.01时,系统的资源占用减少5倍以上;本算法功耗降低10倍以上,能够减轻系统的负载,提高系统性能,适用于高速网络中字符串的检测。

主 题 词：布隆过滤器 内容寻址存储器 字符串匹配 哈希函数 网络安全 

学科分类：0839[0839] 08[工学] 

馆 藏 号：203167192...