M*******a
发帖数: 1633 | |
e***a
发帖数: 1661 | 2 bloom filter is the biggest buy-point of mapreduce. |
s*****r
发帖数: 43070 | 3 detect duplication的
【在 M*******a 的大作中提到】
: 好像又是个什么新的数据结构我老没学过
|
a****r
发帖数: 87 | 4 A Bloom filter is a data structure designed to tell you, rapidly and memory-
efficiently, whether an element is present in a set. It is used in Cassandra
for fast data read.
http://billmill.org/bloomfilter-tutorial/ |
z*****u
发帖数: 3010 | 5 好像是比较省空间的 一种hash function
但是不能够保定100%准确 |
s******c
发帖数: 1920 | 6 Bloom filter 相当于对set做一个摘要. 支持你快速判定是否一个任意元素出现在这个
set中.
但是会有one-side error: 一个不在set中的元素可能被判定成在set中; 但是一个在
set中的元素绝对不会被判错.
Bloom filter的好处是要求的空间很小: 1%错误率的Bloom filter 只需要8个bit 来存
一个元素, 不管原元素多长.
不算是新数据结构, 70年代的时候就被提出了, 但是当时大家觉得没用. 90年代才被
reinvent. 现在好一点的美国学校都会在本科教这个了.
【在 M*******a 的大作中提到】
: 好像又是个什么新的数据结构我老没学过
|
M*******a
发帖数: 1633 | |
w**z
发帖数: 8232 | 8 Cassandra uses it.
【在 M*******a 的大作中提到】
: 好像又是个什么新的数据结构我老没学过
|
s**x
发帖数: 7506 | |
j**********g
发帖数: 204 | 10 最近面过google，问的就是这个，不会。已经挂了 |
e********3
发帖数: 18578 | 11 我也被问到过。
【在 M*******a 的大作中提到】
: 好像又是个什么新的数据结构我老没学过
|
s**x
发帖数: 7506 | 12 还有consistent hashing 看来是必会的了。 |
