14 jiaomeng

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 2w+

Bloom Filter, Counting Bloom Filter和Dynamic Count Filter源码下载

下面是我做实验时实现的bloom filter,counting bloom filter和dynamic count filter的源码,只经过很简单的测试,有兴趣的可以下载玩一玩,如果发现bug请发邮件给我,谢谢。下载点击这里

2007-05-21 14:50:00

Bloom Filter应用之LOAF

 LOAF (List Of All Friends)是一种email的扩展,它允许你在发送电子邮件时连同你的通讯录一起发出。通讯录(邮件地址的集合)用bloom filter来表示,不但大大减少了网络通信量,而且保护了你的隐私。LOAF将你收到邮件中的bloom filter收集到本地作为数据库,从而在其它邮件到来时判断其优先级。LOAF可以帮你把接收的邮件分成三类:1.        

2007-04-18 20:00:00

写好论文的十大技巧

写好论文的十大技巧作者:Jim Kurose1.         每篇论文都讲述了一个故事。Ø         假设你是一个创业者,这个故事就是你的创业计划,你如何利用搭乘电梯的短暂时间给一位风险投资家讲述你的故事?换句话说,你的“电梯陈述”(elevator pitch)是什么?Ø         这个故事讲的不是你做了什么,而是你要展示什么。有没有新的想法,新的见解

2007-04-14 17:27:00

Dynamic Count Filter

Spectral bloom filter(SBF)在counting bloom filter(CBF)的基础上提出了元素出现频率查询的概念,将CBF的应用扩展到了multi-set的领域。但是,SBF为解决动态counter的存储问题,引入了复杂的索引结构,这让每个counter的访问变得复杂而耗时。有没有一种解决方案既支持元素出现频率查询,结构又相对比较简单呢?Dynamic count f

2007-03-28 11:18:00

Spectral Bloom Filter (4)

在membership query上,由于SBF和CBF都沿用bloom filter的基本结构,因此很难在membership query上提高查询效率。但在查询元素出现频率(大于1的情况)时,由于SBF采用counter中的最小值来近似表示元素的出现频率,使得各个counter的重要性有所差别,因此CBF将counter一视同仁的做法就有提高的空间。 先来看第一种优化算法Minimal

2007-03-25 07:24:00

Spectral Bloom Filter (3)

上一节中,我们介绍到SBF将所有counter排成一个位串,counter之间完全不留空隙,然后通过建立索引结构来访问counter。现在我们来扩展这个结构,使之能支持增加和删除操作。  删除操作相对来说比较好处理,因为它不会导致存储空间的增加。但是也不能坐视不管,因为大量的删除操作会导致本该释放的空间仍然被占用。SBF采取的策略是,单个删除操作只影响相关的counter,整个存储结构

2007-03-24 08:37:00

Spectral Bloom Filter (2)

上一节说到SBF对counter的存储。为实现counter的高效存储,我们先简化问题,来看最少需要多少位才能存储所有的counter。假设SBF要表示M个元素的集合(可能包含重复元素),counter数组的长度为m(对应着bloom filter的位数组),显然所有counter需要的最少位数N为 其中Ci表示counter数组中第i个counter的大小,即哈希函数映射到第i位

2007-03-23 12:11:00

Spectral Bloom Filter (1)

Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。一旦位扩展成了counter,每一个counter就不仅能表示这一地址有无映射,还能表示映射的个数。这一扩展使得存储的数据包含了更多信息,然而遗憾的是,CBF

2007-03-19 22:11:00

Bloom Filter应用之Web Cache Sharing

从这篇文章开始,我会陆续介绍一些bloom filter的应用。Bloom filter于1970年由Burton Bloom在一篇名为Space/Time Tradeoffs in Hash Coding with Allowable Errors的论文中提出。这篇论文同时将bloom filter(论文中不叫这个,只说是一种哈希方法,Bloom还没有自负到直接将其命名为bloom filter

2007-03-16 16:14:00

评价d-Left Counting Bloom Filter

 Bloom Filter是一个简洁精致的数据结构,要对它进行本质上的提高并不容易。多少年来,针对Bloom Filter的变种很多,但实质性的突破并不多,无非Counting Bloom Filter、Compressed Bloom Filter等几种。很多变种都针对某一特定的应用领域,或是针对某一个方面的问题,离开特定的领域和问题,将它单独拿出来算不上有分量的突破。 较之Bloo

2007-03-14 16:58:00

d-Left Counting Bloom Filter (5)

 最后,我们将d-left counting bloom filter与标准的counting bloom filter作一比较。假设要表示的集合有m个元素,构造d-left counting bloom filter的各个参数如下:1.         d-left哈希表包含4个子表;2.         每个子表包含m/24个bucket,使得bucket的平均负载是6个元素;

2007-03-13 12:22:00

d-Left Counting Bloom Filter (4)

根据前面的描述,d-left counting bloom filter构造过程中的缺陷有三个条件:1. x和y的fingerprint相同;2. 位置选择有重合;3. x不选择重合位置,y选择重合位置。其中fingerprint相同我们无法避免,因为碰撞总会出现,cell中的counter也是为此而设置的。元素选不选择重合位置我们也无法控制,因为这要根据当时的负载情况而定。所以我们想要弥补这个缺

2007-03-11 09:35:00

d-Left Counting Bloom Filter (3)

   通过以上的介绍,d-left counting bloom filter的主要思路已经呈现出来了,那就是利用d-left hashing的方法存储fingerprint。下面我们就总结一下d-left counting bloom filter的构造过程。 首先我们使用一个d-left哈希表,表中每个bucket可以容纳若干个(固定数量的)cell,每个cell的位数固定,包括一

2007-03-10 17:30:00

d-Left Counting Bloom Filter (2)

关于d-left hashing,上一篇文章已经介绍过了,这里不再多讲。前面提到过,使用d-left hashing是为了解决哈希表的负载平衡问题。为了了解d-left hashing如何解决这个问题,我们先来看没有d-left hashing的情况。同一个hash value高位用作地址低位用作fingerprint,这就意味着同一个地址对应着多个fingerprint。一个地址对应一个buck

2007-03-09 10:25:00

d-Left Hashing

  下面介绍简单介绍一下d-left hashing。d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同时用两个哈希函数进行计算,得出两个地址h1[key]和h2[key]。这时需要检

2007-03-08 10:38:00

d-Left Counting Bloom Filter (1)

哈希函数的输出值(hash value)通常有两种用途:一种用作地址,比如在哈希表中要存储一个元素,首先要针对这个元素生成一个随机地址;另一种用作fingerprint(或者叫digital summary),比如将密码字符串hash成一个fingerprint,验证时进行核对。今天我要介绍的这种存储信息的方式将以上两种用途结合了起来:一个hash value分作两部分,一部分用作存储地址,另

2007-03-07 12:19:00

Perfect Hashing VS. Bloom Filter

Perfect Hashing VS. Bloom Filter在Network Applications of Bloom Filters: A Survey一文中,作者提到了一种基于Perfect hashing的方法,它在维持同样错误率的情况下比Bloom Filter占用更少的空间。但是这种方法只能使用在静态集合上,一旦集合发生变化,就需要进行重新计算。 假设我们要表示的静态集

2007-03-02 16:17:00

关于hashing

The most important techniques behind Yahoo! are: hashing, hashing and hashing!——前雅虎首席科学家Udi Manber 计算机科学中的一类基本问题是如何在内存中找到一段指定的信息(a “key”),这类问题常常被称为字典问题(dictionary problem)。对这类问题可以提出很多解决方案,但考虑的

2007-02-16 22:42:00

区分几个概念:Dictionary, Direct-address Tables, Hash Tables

Dictionary是一种抽象数据类型,用来存储可以用键值(key)索引的数据项,基本的操作包括插入、查找和删除。它是一个相对比较广义的概念,并没有规定具体的实现,比如在底层用什么数据结构存储数据项。因此,只要存储的每一个数据项是一对(key, value),并可以用key索引到这一项,就可以将这样的数据类型称为Dictionary。 Direct-address Tables和Hash

2007-02-12 16:46:00

Compressed Bloom Filter

Compressed Bloom Filter焦萌 2007年2月8日 在前面的讨论中,我们都只将Bloom Filter作为一种表示集合的数据结构。但在网络应用中,Bloom Filter经常被当作节点之间交换信息时传递的消息。从这个角度考虑,我们自然希望消息在传递之前能够被压缩。 那么Bloom Filter到底能不能被压缩?在Bloom Filter概念和原理一文中,我们

2007-02-08 14:10:00

查看更多

勋章 我的勋章
    暂无奖章