首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >非常低概率的概率集

问非常低概率的概率集
EN

Stack Overflow用户
提问于 2016-10-21 00:55:25
回答 2查看 55关注 0票数 1

我正在寻找一种集合数据结构,它针对一个项目是集合的一部分的概率非常低而进行了优化。

使用案例是Gnip/Twitter遵从性防火墙,我们每秒获得大约1000个事件(这是从所有Twitter中删除的事件)。我们有一个表,假设有1000万条存储的tweet(每年以这个数量增长),如果一个项目出现在消防水管中,我必须删除它。我猜每100,000秒就会有一次匹配(从空气中提取一个数字)。

我曾想过布隆过滤器,可能是几个链式的,但考虑到命中率非常低,我总是需要遍历整个链条,事情最终会变得线性。

有没有一个很好的次线性数据结构?

EN

回答 2

Stack Overflow用户

发布于 2016-10-21 04:33:14

我看不出有什么问题。在我看来,如果检查Bloom filter告诉您已经存储了tweet,那么您就可以在数据存储中查找该tweet。如果它在那里,你就把它删除。如果它不在那里,你不会删除它。

您有1000万条存储的tweet,并且您预计它将以每年约1000万条的速度增长。因此,构建一个容量为10亿,误报概率为0.1%的Bloom filter。根据Bloomfilter calculator的说法,这将耗费1.67G的空间。

请理解,“假阳性”数字假设筛选器包含10亿个密钥。当您的过滤器填充非常稀疏时,误报的概率要低得多。

如果你每秒收到一千条tweet,而Bloom filter的误报率为0.1%,那么在最坏的情况下,你平均每秒会得到一条误报。因此,每秒一次,您的代码必须访问数据库,以确定tweet是否在那里。

但要实现这一点还需要很多年。由于现有记录只有1000万条,并且以每年1000万条的速度增长,过滤器甚至需要10年才能填满10%。您可能会将筛选器大小降低到5亿(860MB),但仍然不会注意到由于误报而产生的大问题。

票数 0
EN

Stack Overflow用户

发布于 2016-10-21 05:46:56

Bloom过滤器应该很好,假设它可以放在内存中。如果它不能完全装入内存,请考虑使用this paper中描述的解决方案。

或者,如果您真的想压缩一点额外的性能,可以使用Cuckoo Filter,但是很难找到开源实现;这里有一个用Go编写的实现。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/40160233

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档