全部博文（330）
分类：
2011-06-20 23:22:25
Bloom Filter是一个简洁精致的数据结构，要对它进行本质上的提高并不容易。多少年来，针对Bloom Filter的变种很多，但实质性的突破并不多，无非Counting Bloom Filter、Compressed Bloom Filter等几种。很多变种都针对某一特定的应用领域，或是针对某一个方面的问题，离开特定的领域和问题，将它单独拿出来算不上有分量的突破。
较之Bloom Filter的其它变种，d-left counting bloom filter有其特殊性。之所以将这种结构称作counting bloom filter，是因为它的外在功能和counting bloom filter一样，但就它的内部结构而言，称它为bloom filter有些牵强。如果将counting bloom filter比作一只猫，那d-left counting bloom filter就是一只比猫还擅长抓老鼠的狗。虽然它抓老鼠的效率比猫高了一倍，但它终究是只狗。它有猫所不具有的一些本领，但是也不具备猫的轻盈和迅捷。
就d-left狗抓老鼠的本领来说，它已经跻身了bloom猫家族的贵族行列。在bloom filter的所有变种中，它大概有资格被称为前面提到的实质性的突破。Bloom filter的一个先天不足就是不支持删除集合元素，这些年出了这么多变种，实用的支持删除操作的变种也不过就是counting bloom filter。Counting bloom filter好是好，但毕竟占用的空间是标准bloom filter的4倍。现在d-left counting bloom filter的出现将counting bloom filter的空间占用减少到原来的一半甚至更少，这毫无疑问是巨大的突破。
当然它也不是没有缺点。前面提到d-left狗不具备猫的轻盈和迅捷，这是由它狗的本质所决定的。Counting bloom猫虽然比它的祖宗bloom猫肥了4倍，但它终究是只猫，有一些猫的共性。在很多应用领域，比如，counting bloom filter并不单独使用，在表示本地动态变化的集合时采用counting bloom filter，而在与其它节点交换信息时将counting bloom filter转为标准的bloom filter在网络上传送。Counting bloom猫虽然能力强，但是太肥，跑不动，跑路的事儿还是交给它的祖宗bloom猫去干吧。在这类应用中，d-left狗就傻眼了，它想跟身轻如燕的bloom猫一起配合抓老鼠，但bloom猫不干啊，猫狗之间完全没法沟通，除了打架还能干什么像样的工作？
除此之外，d-left counting bloom filter还有其它的问题。虽然论文作者说它是一个很简单、甚至比counting bloom filter更简单的结构，但我死活没有看出这点来。作者本来想直接用d-left hashing的方法将集合的fingerprints一存就了事，没想到出了一个漏洞，删除时有可能会碰到两个完全相同的fingerprint。还好作者没有放弃，赶紧想出了一个亡羊补牢的法子，又引入了d个置换把漏洞抹平。可是漏洞虽然抹平了，但整个hashing操作已经被整了容，不是原汁原味的d-left hashing了。作者没办法，只好说，虽然不是原汁原味了，但也没关系，将就着用吧，用起来感觉不到差别的。回想bloom filter的简洁带来的美感，我实在体会不出d-left counting bloom filter的简单到底在那里。
虽然d-left狗不是什么名门正派，但毕竟走出了一条混血的新路。如果追随者很多，说不定慢慢也就成了名门正派。现在看起来，d-left狗属于羽翼未丰的小崽儿，需要完善的地方还有很多，这也意味着可以提升的空间还很大。另外，论文中很多需要证明的地方作者都没有给出，但承诺会在后面杂志上发表时给出完整的理论支持。让我们拭目以待吧。
