Bloom Filter哈希空间的元素还原  

Element Recovery from Counting Bloom Filters′ Hash Space

作　　者：彭艳兵 龚俭[1] 刘卫江 杨望[1] 

机构地区：[1]东南大学计算机科学与工程系江苏省计算机网络技术重点实验室,江苏南京210096

出　　处：《电子学报》2006年第5期822-827,共6页Acta Electronica Sinica

基　　金：国家973重点基础研究发展规划(No.2003CB314803);江苏省网络与信息安全重点实验室(No.BM2003201)

摘　　要：本文提出使用语义增强的Counting B loom FilterReconstruction(RSECBF)算法来快速还原源串或给出源串的聚类特征.它给每个哈希函数独立的哈希映射空间以消除哈希函数的内部冲突;扩展哈希函数使其不受均匀性限制,使得哈希函数可以带有语义;利用哈希串的重叠和数量一致性来解决同源哈希串拼接成源串的问题,为源串的还原创造了条件.本文针对Pareto分布的哈希函数,为主成分的还原提出了一个简洁的源串还原算法.对于直接选择部分比特的哈希映射而言,如果主成分分析中的RSECBF不能还原出源串,则还原出来的最长串就是源串的聚类特征.仿真及实际检验表明,B loom Filter可以扩展其哈希函数来实现语义增强,RSECBF还原的结果是可信的.本算法可以在异常行为发生的时候挖掘网络行为特征.An original element reconstructing algorithm named Reconstruction with Semantically Enhanced Counting Bloom Filter （RSECBF） is proposed to timely recover the original element in set S from Counting Bloom Filter＇s hash space. The semantically enhanced hash function is based the ideas that, the independent hash space preserved for each different hash function eliminates the internal confliction among hash functions, and the hash function could be extended from the uniform distribution to any distribution; the overlapping of hash bit strings bring the ability to recover the original string by the uniqueness of hash mapping process and the hits amount balance of overlapped hash string. The recovery algorithm is greatly simplified for the Pareto distribution when only the principal component is analyzed. For Directly Bit String Selecting, the reproduced longest string just is the distribution character of the original strings. The simulation and the validation with published data trace suggested that the recovery result of RSECBF is acceptable. It can be used to find the network behavior characteristics when abnormal behavior bursts in the real networks.

关 键 词：COUNTING BLOOM FILTER 语义增强 参数还原 异常行为检测 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]