我正在寻找一种集合数据结构,它针对一个项目是集合的一部分的概率非常低而进行了优化。
使用案例是Gnip/Twitter遵从性防火墙,我们每秒获得大约1000个事件(这是从所有Twitter中删除的事件)。我们有一个表,假设有1000万条存储的tweet(每年以这个数量增长),如果一个项目出现在消防水管中,我必须删除它。我猜每100,000秒就会有一次匹配(从空气中提取一个数字)。
我曾想过布隆过滤器,可能是几个链式的,但考虑到命中率非常低,我总是需要遍历整个链条,事情最终会变得线性。
有没有一个很好的次线性数据结构?
发布于 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),但仍然不会注意到由于误报而产生的大问题。
发布于 2016-10-21 05:46:56
Bloom过滤器应该很好,假设它可以放在内存中。如果它不能完全装入内存,请考虑使用this paper中描述的解决方案。
或者,如果您真的想压缩一点额外的性能,可以使用Cuckoo Filter,但是很难找到开源实现;这里有一个用Go编写的实现。
https://stackoverflow.com/questions/40160233
复制相似问题