代码之家 › 专栏 › 技术社区 › flyingfox

当我们处理非常大的数据时,什么时候使用Bloom过滤器,什么时候使用位图?

bloom-filter bitmap algorithm

0

flyingfox · 技术社区 · 6 年前

我在学习 Bloom filter BitMap (也称为 Bit Array )遇到一个问题,有人能告诉我什么时候使用Bloom过滤器,什么时候使用位图吗?

在我的理解中,我认为当我们需要找到最大的数或者想要对大量的数据进行排序时,位图更适合(纯数字)。

不过,我想在谷歌上找到一些有用的建议,或者说我不想在谷歌上找到更多有用的信息。提前谢谢!

0 回复 | 直到 6 年前

1

3

Thomas Mueller 6 年前

何时使用 Bloom filter :如果您有一个集合(唯一项的列表)和哈希函数,则可以创建Bloom筛选器。它允许查询类型为“entry x liked in the set?”。如果条目在集合中,则查询将返回true。对于不在集合中的条目,它可能返回true,概率很低,通常为1%或更低(取决于Bloom过滤器的大小)。您可以使Bloom过滤器尽可能小,但是对于大约1%的假阳性率,您需要每个条目大约10位。有其他算法/数据结构使用较少的空间,参见。 https://github.com/FastFilter

何时使用 bit array https://roaringbitmap.org/ . 您不会像Bloom过滤器那样有误报,但是大小的使用很大程度上取决于您的数据(取决于您拥有的数字),这比使用Bloom过滤器更为重要。