Xan*_*lip 6 c++ algorithm probability computation bloom-filter
给定大小为N位和K个散列函数的布隆过滤器,其中设置了滤波器的M位(其中M <= N).
是否可以近似插入布隆过滤器的元素数量？
简单的例子
我一直在考虑以下示例,假设一个100位的BF和5个散列函数,其中设置了10位...
最佳情况:假设散列函数非常完美并且为某些X个值唯一映射一个位,那么已经设置了10位,我们可以说在BF中只插入了2个元素
最糟糕的情况:假设哈希函数是坏的并且一致地映射到相同的位(但彼此之间是唯一的),那么我们可以说已经将10个元素插入到BF中
范围似乎是[2,10],其中这个范围内的大概可能是由滤波器的假阳性概率决定的 - 我在这一点上陷入困境.
小智 12
这个问题让我有点担心,因为有更好的算法来近似计算具有少量存储的不同元素的数量.
然而,如果我们必须使用Bloom过滤器,我们假设散列函数是随机的oracles(所有值独立选择,或"非常完美",不要与完美散列混淆).现在我们有一个球,箱问题:考虑到M的N垃圾箱已经在他们的球,多少个球没我们抛出？让B投掷的球数; 物品的数量是B/K,因为每个项目我们扔K球.
球和箱过程的标准近似是将每个箱建模为独立的泊松过程; bin被占用之前的时间是指数分布的.假设1投掷所有球的时间?,这个指数分布的速率的最大似然估计满足Pr(Exponential[?] < 1) = M/N,所以1 - exp(-?) = M/N和? = -log(1 - M/N).该参数?类似于球的数量,因此物品数量的估计是B ? -N log(1 - M/N)/K.
编辑:有N箱子,所以我们需要乘以N.