c – 计算布隆过滤器的近似总体

前端之家收集整理的这篇文章主要介绍了c – 计算布隆过滤器的近似总体前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
给定大小为N位和K个散列函数的布隆过滤器,其中设置了滤波器的M位(其中M <= N). 是否可以近似插入布隆过滤器的元素数量? 简单的例子 我一直在考虑以下示例,假设一个100位的BF和5个散列函数,其中设置了10位… 最佳情况:假设散列函数非常完美并且为某些X个值唯一映射一个位,那么已经设置了10位,我们可以说在BF中只插入了2个元素 最糟糕的情况:假设哈希函数是坏的并且一致地映射到相同的位(但彼此之间是唯一的),那么我们可以说已经将10个元素插入到BF中 范围似乎是[2,10],其中这个范围内的大概可能是由滤波器的假阳性概率决定的 – 我在这一点上陷入困​​境.

解决方法

这个问题让我有点担心,因为有大约 better algorithms用于计算具有少量存储的不同元素的数量.

然而,如果我们必须使用Bloom过滤器,我们假设散列函数随机的oracles(所有值独立选择,或“非常完美”,不要与完美散列混淆).现在我们有一个球和箱子的问题:考虑到N个箱子中有M个球,我们扔了多少个球?设B为抛出的球数;项目数是B / K,因为每个项目我们扔K球.

球和箱过程的标准近似是将每个箱建模为独立的泊松过程; bin被占用之前的时间是指数分布的.假设1是抛出所有球所花费的时间,该指数分布的速率的最大似然估计λ满足Pr(指数[λ] <1)= M / N,所以1-exp(-λ) = M / N且λ= -log(1-M / N).参数λ类似于球的数量,因此项目数的估计是B≈-N log(1-M / N)/ K. 编辑:有N个箱子,所以我们需要乘以N.

原文链接:https://www.f2er.com/c/111710.html

猜你在找的C&C++相关文章