我试图确定Google Guava's Bloom Filter是否适用于我的项目,但是在我的测试中,我得到了极高的误报率(很可能是由于高度的哈希冲突?)。
我正在使用2个数据文件进行实验。第一个包含2200万个唯一数字(整数),我将它们放入了Bloom过滤器中。第二个包含另一组完全不同的数字,也是唯一的,我用它们来测试Bloom Filter的误报率。
这是其中一些数字的示例:
1010061
904436
859990
854448
839175
754186
904491
233955
904491
876342
919575
603051
1012863
989713
323424
我的代码如下:
private static void experiment() {
// Load 22m unique IDs from file
ArrayList<String> skus = loadSkus("sku_1.txt");
int numInsertions = skus.size();
// Google Guava Bloom Filter
Funnel<String> strFunnel = (Funnel<String>) (from, into) -> into.putString(from, Charset.forName("US-ASCII"));
BloomFilter<String> bf = BloomFilter.create(strFunnel, numInsertions, 0.001);
for (String sku : skus) {
bf.put(sku);
}
int falsePositiveCount = 0;
double falsePositiveRate;
// Load another set of unique IDs that are NOT in the first set
ArrayList<String> skus2 = loadSkus("sku_2.txt");
for (String sku : skus2) {
if (bf.mightContain(sku)) {
falsePositiveCount++;
}
}
falsePositiveRate = (double)falsePositiveCount / (double)skus2.size();
System.out.println("Expected FPP: " + Double.toString(bf.expectedFpp()));
System.out.println("Measured FP rate: " + Double.toString(falsePositiveRate));
}
结果:
Expected FPP: 7.276343403395039E-27
Measured FP rate: 0.9979594547309587
测得的误报率似乎高得令人难以置信!这不是该数据结构应如何表现的。我会以某种方式滥用图书馆吗?我真的很想使用Bloom Filter实现适当的性能。
最佳答案
我无法复制您的结果。我唯一能想到的是它与您的数据文件有关?
我使用了与您发布的代码相同的代码,除了我这样生成了skus:
final List<String> skus = ContiguousSet.create(Range.closedOpen(0, 22000000), DiscreteDomain.integers()).stream().map(String::valueOf).collect(Collectors.toList());
和
final List<String> skus2 = ContiguousSet.create(Range.closedOpen(-22000000, 0), DiscreteDomain.integers()).stream().map(String::valueOf).collect(Collectors.toList());
结果:
Expected FPP: 0.0010001451412535098
Measured FP rate: 9.963636363636364E-4
关于java - 为什么 Guava Bloom过滤器的性能如此差?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/40387916/