绽放过滤器的启发式分析 -- probability-theory 领域 和 hashing 领域 和 bloom-filters 领域 cs 相关 的问题

Heuristic analysis of Bloom filters


简体版||繁體版
2
vote

问题

中文

我目前正在观看绽放过滤器的讲课,教授正在进行对绽放过滤器的启发式分析。

这一切都基于以下假设:

所有$ h_ {i}(x)$ s统一随机和独立(跨不同$ i $'s和$ x $ s)

设置:

  • 长度为$ n $ bith的绽放过滤器。
  • 数据将$ s $插入盛开过滤器。

教授声称,对于每位的数组$ a $,它已设置为1的概率是(在上面的假设下,并插入数据集后):$ 1 - (1 - 1 / n)^ {k | s |} $,其中$ k $是散列函数的数量。

我试图了解为什么这是概率。

他解释说,随着$ |的每一个$对象插入(0或1),有$ k $"darts" 均匀抛出,随机抛出,彼此抛出到阵列中,所以这就是给我为什么以$ k $的直接乘以$ | s | $。然后他说给定的"飞镖" 是$ N $ BITS之一的概率是1 / N $。由于总共有$ k | s | $"飞镖" 抛出结束,因此它有意义的是,在整个设置$ s $曾被插入后,给定位被命中的概率为$(1 / n )^ {k | s |} $,它没有被命中的概率是$(1-1 / n)^ {k | s |} $。但我不明白为什么所有这些都从最终从1美元减去到最终为1美元 - (1 - 1 / n)^ {k | s |} $,所以我缺少一些东西......

有人可以向我解释这个吗?

英文原文

I am currently watching a lecture on Bloom filters, and the professor is doing a heuristic analysis of Bloom filters.

It's all based on the following assumption:

All $h_{i}(x)$'s are uniformly random and independent (across different $i$'s and $x$'s)

Setup:

  • Bloom filter of length $n$ bits.
  • Data set $S$ is inserted into the Bloom filters.

The professors claims that for each bit of array $A$, the probability that it has been set to 1 is (under above assumption, and after data set has been inserted): $1 - (1 - 1/n)^{k|S|}$, where $k$ is the number of hash functions.

I am trying to understand why that's the probability.

He explains that as each of the $|S|$ objects gets inserted (0 or 1), there are $k$ "darts" thrown uniformly at random and independent from each other thrown into the array, so that gives me the intuition of why $k$ is being multiplied by $|S|$. He then says the probability that a given "dart" is one of the $n$ bits is $1/n$. Since there are a total of $k|S|$ "darts" thrown at the end, it makes sense that after the whole set $S$ has been inserted, the probability that a given bit has been hit is $(1/n)^{k|S|}$, and the probability that it hasn't been hit is $(1-1/n)^{k|S|}$. But I don't understand why all that is being subtracted from $1$ at the end to end up being $1 - (1 - 1/n)^{k|S|}$, so clearly I'm missing something...

Can somebody explain this to me?

        

回答列表

2
 
vote
vote
最佳答案
 

如果它被命中,则一位设置为1。它有$ k | s | $遭受击中的机会,每次都以1 / n $的概率打击。使用UNIT绑定,比特命中的概率最多为$ k | s | / n $。

我们可以通过计算来改进这一界限,而不是计算概率,即它是 not 命中。有点不被击中,每次都必须错过。由于它有$ k | s | $机会被击中,每次都错过了1-1 / n $的概率,总数有概率$(1-1 / n)^ {k | |} $。因此,有点是不是概率$ 1-(1-1 / n)^ {k | s |} $。

 

A bit is set to 1 if it has been hit. It has $k|S|$ chances of being hit, and each time it is hit with probability $1/n$. Using a union bound, the probability that a bit is hit is at most $k|S|/n$.

We can improve on this bound by calculating instead the probability that a bit is 0, that is, that it is not hit. For a bit not to be hit, it has to be missed each time. Since it has $k|S|$ opportunities to be hit, and each time it is missed with probability $1-1/n$, in total a bit is missed with probability $(1-1/n)^{k|S|}$. Thus a bit is not missed with probability $1-(1-1/n)^{k|S|}$.

 
 
         
         

相关问题

5  在绽放过滤器中,为什么哈希数*增加*滤波器中的位数?  ( In a bloom filter why does the optimal number of hashes increase with the num ) 
多个资源,如 wikipedia ,如果您有$ m $ -bit bloom过滤器,带有$ n $元素插入,那么最佳数字$ k $ $ k $ f $ k $ / p> $ k = frac {m} {n} ln 2 $ 这是非常违反直觉的。如果$ M $是过滤器中的位数,那么随着M $增加$ M $,为什么...

1  如何估算插入绽放过滤器的元素数量  ( How to estimate the number of elements inserted to a bloom filter ) 
a bloom filter 是一个概率数据结构,允许使用误报的组编码集。< / p> 由位数 $ m $ 中的参数化,在数组 $ a $ (初始化为零)和哈希函数的数量 $ k $ ,Item $ x $ 对应于设置 $ a [h_i(x)] = 1 $ for $ i = 1, ldots,k $ 。...

2  绽放过滤器的启发式分析  ( Heuristic analysis of bloom filters ) 
我目前正在观看绽放过滤器的讲课,教授正在进行对绽放过滤器的启发式分析。 这一切都基于以下假设: 所有$ h_ {i}(x)$ s统一随机和独立(跨不同$ i $'s和$ x $ s) 设置: 长度为$ n $ bith的绽放过滤器。 数据将$ s $插入盛开过滤器。 教授声称,对于每位的数组$ a $,它已设...

1  为什么绽放过滤器需要$ frac {m} {n} ln {2} $散列函数?  ( Why bloom filter needs fracmn ln2 hash functions ) 
我从 wikipedia 那是最佳散列函数是: $ k = frac {m} {n} ln {2} $。 然而,对于我来说,为什么这不明显,即使阅读维基百科文章之后(例如误报的一个)。有兴趣用简单的词语解释的人吗? :) ...

3  绽放过滤器为20800万URL  ( Bloom filter for 208 million urls ) 
我需要创建一个208万URL的绽放过滤器。什么是偏航尺寸和哈希数量的良好选择?我尝试了大小的1 GB和4个哈希函数的位矢量,但它导致读取时的误报了太多。 我有一个包含数十亿个URL的Web内容的巨大Web语料库。我需要处理满足某些标准的URL的Web内容:URL应该在过去7天内在Web搜索结果中出现,至少5次。这由2...

7  双重散列和绽放过滤器的变化  ( Double hashing and variations for bloom filters ) 
我正在阅读绽放过滤器上的几篇论文 - 概率验证中的绽放过滤器(Dillinger和Manolios)建议分别为双重和三重散列分配 $$ begin {align *} f [i]&amp; = a(δ)+ ib(δ) pmod {m} \ f [i]&amp; = a(δ)+ ib(δ)+(c(δ)(i)(i...

2  找到有效地占主导地位的或副线性的线性不平等  ( Find dominated or subsumed linear inequalities efficiently ) 
问题陈述 给定一组 $ n $ 形式的线性不等式 $ a_1x_1 + a_2x_2 + ... + a_mx_m GEQ RHS $ ,其中 $ a_i $ 和 $ RHS $ 是整数。不等式 $ a $ 占主导地位或 esuales 不等式 $ b $ 如果其所有系数较少或等于,而 $ RHS_A GEQ ...

2  绽放过滤器变型  ( Bloom filter variant ) 
我一直在玩一个简单的概率数据结构,它非常类似于绽放过滤器。如果盛开过滤器将使用$ k $独立的散列函数选择$ k $ of $ m $ bits设置,则该结构使用$ m $哈希函数,并使用概率$ p $设置每个位。 这种结构不会产生低于绽放过滤器的假阳性率,但似乎非常快速地计算,特别是如果$ m $是机器字大小的一些...

3  了解Murmur3  ( Understanding murmur3 ) 
Bloom过滤器数据结构需要一组散列函数。 Murmur3家族非常适合,因为它包含 99887665544330 参数,可以轻松创建各种不同的功能(加上它具有良好的价值分配和充足的速度)。 选择 seed 是否有任何特定的方法选择Bloom Filter应用程序的 998807665544332 值?通过随机选...

1  双重散列碰撞  ( Double hashing collision ) 
相同的性能:构建一个更好的绽放过滤器 (kirsch和mitzenmacher)提到我们可以使用 $ g_i(x)=(h_1(x)+ ih_2(x)) pmod {p} $,其中$ h_1(x)$和$ h_2(x)$是两个 宇宙中的独立,均匀的随机哈希函数,范围 $ {0, dots,p-1} $,我们...

1  Bloom滤波器交叉点和盛开过滤器联合之间的比率等于其原始集合的比率?  ( Is the ratio between a bloom filter intersection and a bloom filter union equal ) 
给定两组,S 1 和s 2 ,它们相应的绽放滤波器,bf 1 和bf 2 ,有没有办法证明这一点| BF 1 χbf 2 | bf 1 ∪bf 2 | = | S 1 ∩s 2 | / s 1 ∪s 2 | (我们可以假设使用相同的哈希函数生成盛开过滤器)?如果没有,是否有一种方法可以近似...

7  盛开滤波器的第一个公众参考是什么?  ( What was the first public reference to bloom filters where the number of hash fu ) 
在传统的绽放过滤器中,每个项目都是一些固定数量的位置。其中一个变体是散列物品在同一盛开过滤器内的不同数量的位置。 这个想法是在 zhong等人。,优化数据流行度意识绽放过滤器,podc '08 和 Bruck等,加权绽放过滤器,IEEE信息理论'06 。但是,我知道在没有公布的行业中的一个独立和大致的当代"发现" 。...

0  快速和空间有效的方法,以找到两个套是否相交  ( Quick and space efficient way to find whether two sets intersect ) 
我希望你能帮助我 - 给出了大量包含整数的集合, 我想要任何两套,快速(即code> O(1) )询问它们是否相交。 请注意,我不需要确切的十字路口,而是只是一个是/否答案。 另外,我对一些假的阳性很好。 此外,该组的表示应该是空间效率(即少于设定大小)。 理想情况下,我也喜欢(不经常)更新集。 我的要求让我想到...

4  为什么绽放过滤器工作?  ( Why do bloom filters work ) 
让我们说我正在使用绽放过滤器创建一个函数来检查文档中是否存在于文档中。如果我选择哈希函数以填写一系列桶,请为我的文档中的所有单词填写。然后如果为给定数量的单词,那么整个位桶都不是全部1s?如果是这样,那么检查任何单词都会返回真实吗?我在这里遗漏了什么? ...

9  删除盛开过滤器  ( Deleting in bloom filters ) 
我知道标准绽放过滤器只有插入元素和检查元素是否属于过滤器的操作,而且还有盛开过滤器的一些修改,例如:删除操作 - 例如:计算盛开过滤器。我也听到了另一种方法,它使用第二个过滤器。如果我想删除一个元素,我必须将其"插入" 它进入第二个过滤器。我找不到这一建议的结构如何运行,任何关于它的文章,甚至是发起人的名称。也许有人...

11  替代浏览过滤器以获得极端参数  ( Alternative to bloom filter for extreme parameters ) 
盛开过滤器是一个节省空间的概率数据结构,可以在集合上执行成员资格测试(请参阅 wikipedia 的一个定义页面;我使用下面的相同符号)。 我对一个特殊应用感兴趣,每个元素$ m / n $的比特数量非常低,通常为m&l lt; n $(这导致非常紧凑的集合,但当然当然支付的价格是很多误报)。 一个我遇到的问题是,最...

3  比盛开过滤器的理论假阳性率更好  ( Achieving better than the theoretical false positive rate for bloom filters ) 
我在C ++中实现了标准盛开过滤器,并在不同的大小上测试了它,其比率为$ {c = n / m} $的不同值$ {n} $ where筛选器的大小,而$ { m} $是插入的元素数。 对于绽放过滤器,我创建了$ {k} $散列函数,并在返回的每个哈希索引中设置过滤器中的值。这是我从我的测试中获得的结果的图表: ...

4  有效地执行“批处理”近似会员查询的方法  ( Ways to perform batch approximate member queries efficiently ) 
在这个问题中,我第一次给出 n 我必须以空间有效的方式存储的值数。然后我给了 m 我必须检查它们是否被添加到数据结构中的值(例如,在操作之后,我知道哪个值是成员,哪个价值是成员,哪个值)。 我可以使用绽放过滤器并简单地迭代 99887665544332 ,但由于 m 相当大,我想看看是否有更有效的方式。数据的一个可能...

1  Count-Min草图和商滤波器之间的性能差异(空间和时间复杂性)是什么?  ( What are the performance differnces space and time complexity between count mi ) 
Count-min草图和商滤波器的空间和时间复杂度(查找,插入)? 我找不到这些复杂性。 我想制作一个节目,以最快的方式找到一个集合中对象的频率,因此时间复杂性对我来说非常重要。 我读取了关于这些对象的研究文章,关于"don’t thrash:如何缓存闪存上的哈希值" ,它据说它的查找和插入操作比绽放过滤器更...

1  你怎么称呼“非概率绽放过滤器”?  ( What do you call a non probabilistic bloom filter ) 
我的一个同事用一个很好的技术来解决问题,我觉得它必须已经有一个名字。我只是不知道如何弄清楚它是什么。 是一种用于缓存输入域的子集的简单答案,然后返回到昂贵的计算。在这方面,它让我想起了绽放过滤器的语义或Karnaugh地图的优化概念。 简单说明w / pseudocode: // Determine whethe...

1  为什么我们使用多个比特而不是单个位,以存储在绽放过滤器中的对象  ( Why do we use several bits instead of a single bit for storage of objects in blo ) 
绽放过滤器是哈希表的变体,除了在误报率低的概率低的成本上有更多的空间。 它是如何工作的:假设有10000位,3个哈希函数和对象foo将插入盛开过滤器。 插入:Foo将被第一哈希函数散列,3405位索引设置为1,通过第二个哈希函数散列,并且1001位索引设置为1,所以通过第三个散列函数散列。并且5555位索引设置为1....

0  在磁盘上使用大规模数据算法是否有效?  ( Is it efficient to use large scale data algorithms on disk ) 
是否有效地使用磁盘上的算法等算法,而不是存储器,而不是内存,对于非常大的数据集,甚至这些结构不能保存在内存中? ...

4  整数设置与同性恋散列等类似的草图上的脱节查询  ( Integer set disjointness query on sketches with something like homomorphic hashi ) 
假设我有两组整数 $ a $ 和 $ b $ ,我有一个草图函数 $ mathsf {scraxt} _n: mathcal {p}( mathbb {z}) to 2 ^ n $ 返回bitstring的数据结构大小 $ n $ 。可以使用函数 $ mathsf {disjoint} _n:2 ^ n tim...

27  有防绽放过滤器吗?  ( Is there an anti bloom filter ) 
a bloom filter 使得可以有效地跟踪是否已经遇到了各种值在处理过程中。当有许多数据项时,盛开的过滤器可能会导致在哈希表上保存的重要内存。盛开过滤器的主要特征,它与哈希表共享,如果一个项目不是新的,它总是说"不是新的" ,但是一个非零概率将被标记为"不是新的"即使是新的。 是否有一个"反绽放过滤器" ...

7  绽放过滤器和完美的哈希  ( Bloom filter and perfect hashing ) 
a bloom filter 使用哈希函数以给定的设置$ s $测试成员身份,通过检查项目是否存在于指定位置。 为了减轻散列碰撞的影响,使用多种功能,如果使用通用哈希,则产生概率界限。 我们可以使用每元素10位以具有"合理" 错误率。 如果我们可以直接构建一个完美的哈希函数设置$ s + idty $ ,最后...




© 2021 it.wenda123.org All Rights Reserved. 问答之家 版权所有