Mon, 21 May 2007 14:50:00 GMT谁终将声震人间，必长久深自缄默；谁终将点燃闪电，必长久如云漂泊。http://blog.csdn.net/jiaomeng/http://blog.csdn.net/jiaomeng/archive/2007/05/21/1619321.aspxhttp://blog.csdn.net/jiaomeng/comments/1619321.aspx6http://blog.csdn.net/jiaomeng/comments/commentRss/1619321.aspxhttp://tb.blog.csdn.net/TrackBack.aspx?PostId=1619321下面是我做实验时实现的bloom filter，counting bloom filter和dynamic count filter的源码，只经过很简单的测试，有兴趣的可以下载玩一玩，如果发现bug请发邮件给我。<img src ="http://blog.csdn.net/jiaomeng/aggbug/1619321.aspx" width = "1" height = "1" />Mon, 21 May 2007 22:50:00 +0800焦萌http://blog.csdn.net/jiaomeng/archive/2007/05/21/1619321.aspx#Feedbackhttp://blog.csdn.net/jiaomeng/archive/2007/05/21/1619321.aspx焦萌http://blog.csdn.net/jiaomeng/archive/2007/04/18/1569595.aspxhttp://blog.csdn.net/jiaomeng/comments/1569595.aspx0http://blog.csdn.net/jiaomeng/comments/commentRss/1569595.aspxhttp://tb.blog.csdn.net/TrackBack.aspx?PostId=1569595LOAF (List Of All Friends)是一种email的扩展，它允许你在发送电子邮件时连同你的通讯录一起发出。通讯录（邮件地址的集合）用bloom filter来表示，不但大大减少了网络通信量，而且保护了你的隐私。LOAF将你收到邮件中的bloom filter收集到本地作为数据库，从而在其它邮件到来时判断其优先级。<img src ="http://blog.csdn.net/jiaomeng/aggbug/1569595.aspx" width = "1" height = "1" />Thu, 19 Apr 2007 04:00:00 +0800焦萌http://blog.csdn.net/jiaomeng/archive/2007/04/18/1569595.aspx#Feedbackhttp://blog.csdn.net/jiaomeng/archive/2007/04/18/1569595.aspx焦萌http://blog.csdn.net/jiaomeng/archive/2007/04/14/1564759.aspxhttp://blog.csdn.net/jiaomeng/comments/1564759.aspx0http://blog.csdn.net/jiaomeng/comments/commentRss/1564759.aspxhttp://tb.blog.csdn.net/TrackBack.aspx?PostId=15647591. 每篇论文都讲述了一个故事；2. 按照自顶向下的顺序写作；3. Introduction：至关重要，已经程式化；4. 掌握论文写作的基本知识；5. 将自己摆在读者的位置；6. 没有人对这个话题和你一样感兴趣；7. 谨慎地陈述结果；8. 不要夸大你的结果，也不要太保守；9. 学习写作的艺术；10. 写作需要花费一定时间。<img src ="http://blog.csdn.net/jiaomeng/aggbug/1564759.aspx" width = "1" height = "1" />Sun, 15 Apr 2007 01:27:00 +0800焦萌http://blog.csdn.net/jiaomeng/archive/2007/04/14/1564759.aspx#Feedbackhttp://blog.csdn.net/jiaomeng/archive/2007/04/14/1564759.aspx焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/28/1543751.aspxhttp://blog.csdn.net/jiaomeng/comments/1543751.aspx0http://blog.csdn.net/jiaomeng/comments/commentRss/1543751.aspxhttp://tb.blog.csdn.net/TrackBack.aspx?PostId=1543751Spectral bloom filter（SBF）在counting bloom filter（CBF）的基础上提出了元素出现频率查询的概念，将CBF的应用扩展到了multi-set的领域。但是，SBF为解决动态counter的存储问题，引入了复杂的索引结构，这让每个counter的访问变得复杂而耗时。有没有一种解决方案既支持元素出现频率查询，结构又相对比较简单呢？Dynamic count filter（DCF）尝试回答了这个问题。<img src ="http://blog.csdn.net/jiaomeng/aggbug/1543751.aspx" width = "1" height = "1" />Wed, 28 Mar 2007 19:18:00 +0800焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/28/1543751.aspx#Feedbackhttp://blog.csdn.net/jiaomeng/archive/2007/03/28/1543751.aspx焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/25/1540322.aspxhttp://blog.csdn.net/jiaomeng/comments/1540322.aspx4http://blog.csdn.net/jiaomeng/comments/commentRss/1540322.aspxhttp://tb.blog.csdn.net/TrackBack.aspx?PostId=1540322在membership query上，由于SBF和CBF都沿用bloom filter的基本结构，因此很难在membership query上提高查询效率。但在查询元素出现频率（大于1的情况）时，由于SBF采用counter中的最小值来近似表示元素的出现频率，使得各个counter的重要性有所差别，因此CBF将counter一视同仁的做法就有提高的空间。<img src ="http://blog.csdn.net/jiaomeng/aggbug/1540322.aspx" width = "1" height = "1" />Sun, 25 Mar 2007 15:24:00 +0800焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/25/1540322.aspx#Feedbackhttp://blog.csdn.net/jiaomeng/archive/2007/03/25/1540322.aspx焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/24/1539440.aspxhttp://blog.csdn.net/jiaomeng/comments/1539440.aspx0http://blog.csdn.net/jiaomeng/comments/commentRss/1539440.aspxhttp://tb.blog.csdn.net/TrackBack.aspx?PostId=1539440上一节中，我们介绍到SBF将所有counter排成一个位串，counter之间完全不留空隙，然后通过建立索引结构来访问counter。现在我们来扩展这个结构，使之能支持增加和删除操作。<img src ="http://blog.csdn.net/jiaomeng/aggbug/1539440.aspx" width = "1" height = "1" />Sat, 24 Mar 2007 16:37:00 +0800焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/24/1539440.aspx#Feedbackhttp://blog.csdn.net/jiaomeng/archive/2007/03/24/1539440.aspx焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/23/1538538.aspxhttp://blog.csdn.net/jiaomeng/comments/1538538.aspx0http://blog.csdn.net/jiaomeng/comments/commentRss/1538538.aspxhttp://tb.blog.csdn.net/TrackBack.aspx?PostId=1538538SBF并没有发明什么异乎寻常的高超技巧，和你大概能想到的一样，它构建了一套索引结构。<img src ="http://blog.csdn.net/jiaomeng/aggbug/1538538.aspx" width = "1" height = "1" />Fri, 23 Mar 2007 20:11:00 +0800焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/23/1538538.aspx#Feedbackhttp://blog.csdn.net/jiaomeng/archive/2007/03/23/1538538.aspx焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/19/1534238.aspxhttp://blog.csdn.net/jiaomeng/comments/1534238.aspx0http://blog.csdn.net/jiaomeng/comments/commentRss/1534238.aspxhttp://tb.blog.csdn.net/TrackBack.aspx?PostId=1534238Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。一旦位扩展成了counter，每一个counter就不仅能表示这一地址有无映射，还能表示映射的个数。这一扩展使得存储的数据包含了更多信息，然而遗憾的是，CBF仅仅利用这个扩展支持了删除操作，并没有将信息中蕴含的潜力完全挖掘出来。毫无疑问，Spectral Bloom Filter（SBF）的提出者就看到了这种潜力。<img src ="http://blog.csdn.net/jiaomeng/aggbug/1534238.aspx" width = "1" height = "1" />Tue, 20 Mar 2007 06:11:00 +0800焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/19/1534238.aspx#Feedbackhttp://blog.csdn.net/jiaomeng/archive/2007/03/19/1534238.aspx焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/16/1531423.aspxhttp://blog.csdn.net/jiaomeng/comments/1531423.aspx0http://blog.csdn.net/jiaomeng/comments/commentRss/1531423.aspxhttp://tb.blog.csdn.net/TrackBack.aspx?PostId=1531423从这篇文章开始，我会陆续介绍一些bloom filter的应用。Bloom filter于1970年由Burton Bloom在一篇名为Space/Time Tradeoffs in Hash Coding with Allowable Errors的论文中提出。这篇论文同时将bloom filter（论文中不叫这个，只说是一种哈希方法，Bloom还没有自负到直接将其命名为bloom filter，呵呵）应用在拼写检查中。从此以后，bloom filter就被广泛用于拼写检查之类的字典应用以及数据库中。到了90年代，bloom filter又赶上了网络和Web的浪潮，重新焕发了青春，各种变种和网络应用层出不穷。今天要介绍的summary cache就是bloom filter一个经典的分布式应用。<img src ="http://blog.csdn.net/jiaomeng/aggbug/1531423.aspx" width = "1" height = "1" />Sat, 17 Mar 2007 00:14:00 +0800焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/16/1531423.aspx#Feedbackhttp://blog.csdn.net/jiaomeng/archive/2007/03/16/1531423.aspx焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/14/1529345.aspxhttp://blog.csdn.net/jiaomeng/comments/1529345.aspx5http://blog.csdn.net/jiaomeng/comments/commentRss/1529345.aspxhttp://tb.blog.csdn.net/TrackBack.aspx?PostId=1529345Bloom 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就是一只比猫还擅长抓老鼠的狗。虽然它抓老鼠的效率比猫高了一倍，但它终究是只狗。它有猫所不具有的一些本领，但是也不具备猫的轻盈和迅捷。<img src ="http://blog.csdn.net/jiaomeng/aggbug/1529345.aspx" width = "1" height = "1" />Thu, 15 Mar 2007 00:58:00 +0800焦萌http://blog.csdn.net/jiaomeng/archive/2007/03/14/1529345.aspx#Feedbackhttp://blog.csdn.net/jiaomeng/archive/2007/03/14/1529345.aspx焦萌