| 基于值域二次哈希方法的布鲁姆过滤器 |
| |
| 引用本文： | 张生华,秦拯,宋勇,张忠志.基于值域二次哈希方法的布鲁姆过滤器[J].微计算机信息,2010(6). |
| |
| 作者姓名： | 张生华 秦拯 宋勇 张忠志 |
| |
| 作者单位： | 湖南大学软件学院;湖南民族职业学院;东莞理工学院; |
| |
| 基金项目： | 国家自然科学基金项目;基金申请人:秦拯,张大方;项目名称:“基于端系统的网络在线测量理论与方法研究”(No.60273070); 广东省科技项目;基金申请人:秦拯(No.0711020400157,No.7007730); 东莞市科技项目;基金申请人:秦拯 张忠志(No.2007108101021,No.2006101101032) |
| |
| 摘 要： | 本文针对扩展式布鲁姆过滤器(EBF)内存消耗过大,提出一种基于值域哈希二次过滤的布鲁姆过滤器数据结构(VHBF)和相关算法,VHBF通过在布鲁姆过滤器中对集合中的每个特征进行k次哈希,并将此k次哈希值转化为相应特征的镜像特征。然后对此镜像进行二次过滤运算,运算后的结果保存在另一布鲁姆过滤器中。在对特征进行检索时,由于无需保存特征本身,因而空间效率比EBF更高。实验表明,VHBF的假阳性误判率的比扩展型布鲁姆过滤器(EBF)低,而VHBF内存消耗也低于EBF。
|
| 关 键 词： | 特征检测 布鲁姆过滤器 哈希 成员查找 |
Bloom Filter Based on Value Hashing Method |
| |
| ZHANG Sheng-hua QIN Zheng SONG Yong ZHANG Zhong-zhi.Bloom Filter Based on Value Hashing Method[J].Control & Automation,2010(6). |
| |
| Authors: | ZHANG Sheng-hua QIN Zheng SONG Yong ZHANG Zhong-zhi |
| |
| Affiliation: | ZHANG Sheng-hua QIN Zheng SONG Yong ZHANG Zhong-zhi(Software School,Hunan University,Changsha 410082,China)(Hunan Vocational College for Nationalities,Yueyang Hunan,414000,China)(Dongguan University of Technology,Dongguan 523808,China) |
| |
| Abstract: | This paper proposes efficient data structure called Value Hash Bloom Filter(VHBF) and the corresponding algorithms.In the programming stage of VHBF,the hash results of the first clusters of hash functions in the first Bloom Filter will be connected as a mirror image of the inserted signature.This mirror image will be hashed into another bloom filter like array.And in VHBF,it is not necessary to store all the actual signatures.Thus,with the mirror image information,we are then able to reduce the total consum... |
| |
| Keywords: | signature detection bloom filter hash member query |
| 本文献已被 CNKI 等数据库收录！ |
|
