Element Recovery from Counting Bloom Filters′ Hash Space
Yang Wang · Dianzi xuebao · 2006
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.