.png){kind=icon}
返回
The Variable-Increment Counting Bloom Filter
.png){kind=icon}
PRE
AI
DOI：10.1109/TNET.2013.2272604.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Counting Bloom Filters (CBFs) are widely used in networking device algorithms. They implement fast set representations to support membership queries with limited error and support element deletions unlike Bloom Filters. However, they consume significant amounts of memory. In this paper, we introduce a new general method based on variable increments to improve the efficiency of CBFs and their variants. Unlike CBFs, at each element insertion, the hashed counters are incremented by a hashed variable increment instead of a unit increment. Then, to query an element, the exact value of a counter is considered and not just its positiveness. We present two simple schemes based on this method. We demonstrate that this method can always achieve a lower false positive rate and a lower overflow probability bound than CBF in practical systems. We also show how it can be easily implemented in hardware, with limited added complexity and memory overhead. We further explain how this method can extend many variants of CBF that have been published in the literature. We then suggest possible improvements of the presented schemes and provide lower bounds on their memory consumption. Lastly, using simulations with real-life traces and hash functions, we show how it can significantly improve the false positive rate of CBFs given the same amount of memory.
Keyword:
Counting Bloom Filter
false positive rate
variable increments
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
I
IF:
3.6
论文数:
4.4K
被引数:
9.5K
机构
引用论文
.png){kind=icon}
Linear Morphea with Lipoatrophy Associated with Segmental Vitiligo in a 13-Year-Old Girl – A Continuum of Spectrum of Autoimmunity线状硬斑病伴脂萎缩与节段性白癜风相关——一种自身免疫谱系连续体
OAAI
OAAI分享收藏
分享收藏
查看更多内容