Time-decaying Bloom Filters for data streams with skewed distributions
Time-decaying Bloom Filters for data streams with skewed distributions
复制标题
DOI：
10.1109/ride.2005.15
复制
发表时间：
2005-04
期刊：
影响因子：
--
通讯作者：
K. Cheng;Limin Xiang;M. Iwaihara;Haiyan Xu;M. Mohania
中科院分区：
文献类型：
--
作者：
K. Cheng;Limin Xiang;M. Iwaihara;Haiyan Xu;M. Mohania
Bloom Filters are space-efficient data structures for membership queries over sets. To enable queries for multiplicities of multi-sets, the bitmap in a Bloom Filter is replaced by an array of counters whose values increment on each occurrence. In a data stream model, however, data items arrive at varying rates and recent occurrences are often regarded as more significant than past ones. In most data stream applications, it is critical to handle this "time-sensitivity". Furthermore, data streams with skewed distributions are common in many emerging applications, e.g., traffic engineering and billing, intrusion detection, trading surveillance and outlier detection. For such applications, it is inefficient to allocate counters of uniform size to all buckets. In this paper, we present Time-decaying Bloom Filters (TBF), a Bloom Filter that maintains the frequency count for each item in a data stream, and the value of each counter decays with time. For data streams with highly skewed distributions, we proposed further optimization by allowing dynamically allocating free counters to the "large" items. We performed preliminary experiments to verify the optimization.
