deduplicating - 排重

基于Bloom Filter 的排重

Bruno Martins 用java 实现了bloom filter，并且还移植了Maciej Ceglowski 在Using Bloom Filters一文中给出的用于计算最优bit size 和 hash function number 的模型，但由于java.lang.Math.pow 方法存在bug，用移植后的方法往往会得到完全错误的结果。

于是想到用Maciej Ceglowski 提供的方法[1]预算出几种可能会用到的结果，以便于在程序中进行选择，但结果却又大失所望 :(

keys	error rate	lowest bits size	best hash functions
20000000	0.0001	383459095.926706	13
20000000	1e-05	479331722.287969	17
20000000	1e-06	575105573.54478	20
100000000	1e-05	2396658611.43985	17
100000000	1e-06	2875527867.7239	20
100000000	1e-07	3354894536.66848	23

过于密集的hash functions 导致了大量的冲突，使得实际的error rate 与预期的相差很远！

无奈之下，最后还是选择了最原始的方法选择来可以接受的结果。最后得到下面的结果：

keys	error rate	bits size	hash functions
<20000000		100000000	3

注：
[1]，请直接访问 Using Bloom Filters 以获得方法的最新版本。

基于Bekerley DB的排重

基于bekerley db 的排重结果：6340260 rows duplicated [total:13195827, deleted: 0, malformed:0]

基于bloom filter 的排重结果：6482366 rows duplicated [total:13195827, deleted: 0, malformed:0]

对13m的数据进行排重处理，实际重复的数据为6.34m，而bloom filter 过滤的结果是6.48m。