u********s
发帖数: 1047 | |
f*******t
发帖数: 7549 | 2 给你一堆文件，每个文件都是排序好的数字，问这些文件是否包含某一个数字。给每个
文件建一个bloom filter可以快速排除不包含这个数字的文件。
【在 u********s 的大作中提到】
: 最好能给一个简单的小例子。十分感谢
|
s********k
发帖数: 6180 | 3 不是大牛，不过可以用在比如无效或者问题URL检测上，
【在 u********s 的大作中提到】
: 最好能给一个简单的小例子。十分感谢
|
j*******l
发帖数: 1066 | 4 我个人的理解 bloom filter本质就是不解决conflict的hash set 把所有见过的成员全
部hash 然后你问它A见过没 B见过没
因为是hash 所以有conflict的可能 A和B hash成一个value 哪怕只见过A， bloom
filter也会回答你见过B 所以会有false positive
bloom filter适合大量询问是否存在的请求 不care 少量false positive 好处是占用
的space空间小
实际用途之一是我决定部分用户可以用到测试版本 每个用户请求我都问bloom filter
是否是测试用户 如果是就展示测试功能 当然少量非测试用户也被误报 但无碍大局
如果因为可能样本大 bloom filter自身空间小造成false conflict高的情况 可以通过
多次HASH来缓解
【在 u********s 的大作中提到】
: 最好能给一个简单的小例子。十分感谢
|
j*******l
发帖数: 1066 | 5 一个问题 如果数字没有排序 能否使用bloom filter?
【在 f*******t 的大作中提到】
: 给你一堆文件，每个文件都是排序好的数字，问这些文件是否包含某一个数字。给每个
: 文件建一个bloom filter可以快速排除不包含这个数字的文件。
|
f*******t
发帖数: 7549 | 6 可以
【在 j*******l 的大作中提到】
: 一个问题 如果数字没有排序 能否使用bloom filter?
|
u********s
发帖数: 1047 | 7 可以说说url检测这个例子吗。因为还是会有false positive
【在 s********k 的大作中提到】
: 不是大牛，不过可以用在比如无效或者问题URL检测上，
|
u********s
发帖数: 1047 | 8 我也是类似理解的现在，因为会遇到相同的hash value，所以会有false positive
filter
【在 j*******l 的大作中提到】
: 我个人的理解 bloom filter本质就是不解决conflict的hash set 把所有见过的成员全
: 部hash 然后你问它A见过没 B见过没
: 因为是hash 所以有conflict的可能 A和B hash成一个value 哪怕只见过A， bloom
: filter也会回答你见过B 所以会有false positive
: bloom filter适合大量询问是否存在的请求 不care 少量false positive 好处是占用
: 的space空间小
: 实际用途之一是我决定部分用户可以用到测试版本 每个用户请求我都问bloom filter
: 是否是测试用户 如果是就展示测试功能 当然少量非测试用户也被误报 但无碍大局
: 如果因为可能样本大 bloom filter自身空间小造成false conflict高的情况 可以通过
: 多次HASH来缓解
|
f*******t
发帖数: 7549 | 9 由于bloom filter有false positive的特性，在实践中为了提高准确性，会保持一个固
定的bits per entry值。也就是说，随着entry数量的增加，生成的bloom filter也会
变大。所以这是一种典型的空间换时间的做法。
比如用bloom filter来优化key-value数据结构的查询，如果key数量不多而value很大
，空间效率会很高。相反，如果用bloom filter来优化一个set（只有key没有value）
，空间效率就非常低。
【在 u********s 的大作中提到】
: 我也是类似理解的现在，因为会遇到相同的hash value，所以会有false positive
:
: filter
|
