偏态数据流中的Bloom Filters自适应机制研究

Research of the Bloom Filters Adaptive Mechanism in Skewed Traffic

针对Count Bloom Filters(CBF)在对偏态分布的网络数据流进行频度检测时,其使用的固定位数的计数器容易溢出的不足,提出了一种自适应性Bloom Filters(Adaptive Bloom Filters ABF),ABF使用可扩展的逻辑计数器替代CBF中大小固定的物理计数器进行计数,逻辑计数器由数目动态变化的若干个物理计数器组成,初始状态逻辑计数器等同于物理计数器,但逻辑计数器在频度数值上溢时会自适应扩展,覆盖其外部的物理计数器,增加数值容量,保证数值的测量准确性.实验表明ABF能够更好地适应检测频度的变化,并且不显著增加误判率,在对数据偏态分布的频度测量场合比其它Count Bloom Filters更具有优势.

To overcome the shortcoming the counters of Count Bloom Filters are easy to be overflow when CBF counts the multiplicity of items in many emerging applications data streams with skewed distributions, this paper proposes an Adaptive Count Bloom Filter （ABF） ,which uses a scaleable logical counter instead of the fixed size physical counter and the logical counter consists of some physical counters. In the initial stage the logical counter is similar to the physical counter, but while the counter becomes overflow the logical counter will override the external counter to increase its capability to assure the right value. The experimental results show that ABF adapts to the change of multiplicity of items well and the probability of error of ABF does not get a remarkable worse, so ABF outperforms most other Count Bloom Filters on counting multiplicity of items in skewed distributions traffic.