4 种计数型Bloom Filter 的性能分析与比较

对3 种已有的计数型Bloom filter——Na?ve Counting Bloom Filter(NCBF),Space-Code Bloom Filter (SCBF)和d-left Counting Bloom Filter(dlCBF)——的查询错误概率进行了分析,得出了NCBF 的计数器防溢出条件 以及SCBF 和dlCBF 的参数最优设置准则.提出了一种衡量计数型Bloom filter 性能的指标:负载适应性.针对dlCBF 负载适应性差的问题,对dlCBF 进行了改进,提出了一种计数型Bloom filter:Binary Shrinking d-left Counting Bloom Filter(BSdlCBF).通过仿真实验,以计数误差、空间复杂度以及负载适应性为性能指标,对上述4 种CBF 进行了比较. 实验结果表明,BSdlCBF 具有最低的空间复杂度、最小的计数误差以及最佳的负载适应性. BSdlCBF 赢得上述性能 优势的代价在于其计算复杂度比其他3 种计数型Bloom filter 略高.     

相对误差受限的数据流流量测量算法

数据流流量测量的精度采用错误概率和相对误差进行衡量.现有的流量测量算法主要关注如何降低错误概率,而对如何减小相对误差则缺乏研究.考虑到减小相对误差对于流量计费等应用的重要意义,提出了一种相对误差受限的数据流流量测量算法MT-dlCBF(Multi-Tier d-left Counting Bloom Filter).MT-dlCBF由多层dlCBF (d-left Counting Bloom Filter)构成,且随着层数的提高,dlCBF中数据流指纹长度和流量计数器宽度也逐步增加,这样,可减轻长流对于短流的干扰,从而达到减小相对误差的目的.理论分析和仿真实验的结果表明,与dlCBF相比,MT-dl-CBF的错误概率略有增大,但相对误差显著减小.此外,在典型的参数条件下,MT-dlCBF的空间效率略优于dlCBF.     

分片计数布隆过滤器及其在Hbase二级索引的应用

针对Hadoop Database(Hbase)仅支持主索引结构,即通过主键和主键的range来检索数据的问题,提出利用Counting Bloom Filter的新变体建立二级索引来支持非主键数据的检索.分析了已有的Counting Bloom Filter(CBF)技术,针对CBF溢出概率高的问题,提出一种新的Split Counting Bloom Filter(SCBF)技术,SCBF将标准CBF分成多个相互独立的区域,由这多个区域共同存储元素的fingerprint.实验结果表明,与标准CBF相比,SCBF降低了溢出概率,充分提高了过滤器的性能,可以很好地用来建立Hbase二级索引.     

d-Left CBF技术在P2P中的研究

分析了Bloom Filter技术在时下流行的P2P分布式系统中的应用,着重介绍基于Bloom Filter的d-Left Counting Bloom Filtr(CBF)技术,d-left CBF利用d-lef thashing的方法存储fingerprint,将hash value分为两部分,分别用于存储随机地址和fingerprint,从而提高工作效率,并支持节点动态删除操作,应用于节点异常活跃的P2P系统中.     

一种面向数据流模型的流计数算法

在研究数据流过程中,基于现有的概要数据结构Bloom Filter,给出改进的K Bloom Filter结构,从理论上对假阳性误判进行分析,得出两者具有相同的在误判率f0下表示集合规模的上限n0,因此,K Bloom Filter的误判率在可控范围内。提出基于K Bloom Filter的流计数算法,与基于Bloom Filter的流计数算法相比,在相同的空间复杂度O(m)和插入操作时间复杂度O(k)情况下,该算法降低了统计结果的误差。     

K分组合型Bloom Filter方法的设计

Bloom Filter是一种采用位向量表示数据集合并利用Hash函数支持有效数据查找的方法.它能够很好地判定某个元素是否属于给定的集合.拆分型Bloom Filter是Bloom Filter的一种改进,它能较好地缓解分布式环境下集合元素动态增长导致的查找误称率增大问题.作为一种新的K分组合型Bloom Filter,通过与Bloom Filter和拆分型Bloom Filter比较分析的结果表明,该方法能够在误称率、向量空间和平均判定时间3个指标中得到较好的平衡.     

基于Bloom Filter的网页去重算法

现在的互联网中存在网页重复的问题,这些问题将会使数据挖掘,搜索的复杂度加大。现有技术一些不足之处,针对互联网中的重复网页采用基于Bloom Filter的网页去重算法。使用了现有的网页去杂算法,对网页进行预处理,同时利用Bloom Filter结构大大降低了网页去重算法的时间复杂度和空间复杂度。从网页中提炼出表示网页特征的一些长句,从而把网页去重过程转换为一个搜索长句的过程,使用Bloom Filter减小了算法的时间复杂度。     

计数型Bloom Filter及其在机器人导航中的应用

机器人导航面临的一个基本问题是路径规划.本文提出采用单步方向的方式来实现全局地理路径信息的存储和查询,这使得在资源受限、计算能力弱的无线传感器节点上实现大数据量信息的分布式存储成为可能.本文进而采用计数型Bloom Fiher来对路径信息进行压缩存储,同时可以实现路径信息的动态修改.本文随后针对计数型Bloom Filter进行了分析,并通过实验指出了已有的关于Bloom Fiher的研究中存在的一些错误.     

基于Bloom filter的RFID中间件数据过滤算法研究

有效地减少RFID系统中冗余阅读器或天线采集到的大量重复数据,可以降低系统能耗和提高处理效率。经研究,提出采用改进的布隆过滤器(Bloom filter)对RFID采集数据进行去重过滤,并运用到中间件系统中。改进的Bloom filter主要将两个标准的Bloom filter组成二维并行Bloom filter,对RFID采集数据所包含的两个属性值tag ID和reader ID进行并行过滤。经实验可见,标准Bloom filter与哈希过滤(hash filter)相比具有明显的优势,对其改进后,采用二维并行Bloom filter在误判率、吞吐率和存储空间上具有更高的系统性能。     

基于DCBF的流抽样测量算法

为了提高系统的处理效率,减少系统的测量误差,提出了一种基于动态计数型布鲁姆过滤器（Dynamic Counting Bloom Filter,DCBF）的流抽样测量算法。该算法使用基于报文级别的抽样,并通过DCBF进行流查找和统计,且在CBF计数器溢出时动态增加新的CBF。经理论分析和实验表明,该算法不仅提高了系统的运行效率,减少了存储空间的消耗,同时具有准确性和可扩展性,能很好地适用于高速链路的流量测量中。     

典型Bloom过滤器的研究及其数据流应用

Bloom过滤器是一种空间高效但有一定假阳性的数据表示方法。该文分析比较计数型Bloom过滤器、光谱Bloom过滤器和动态计数过滤器的异同点及适用场合,介绍Bloom过滤器在重复项检测及频繁项挖掘中的应用,总结Bloom过滤器给数据流带来的挑战,包括元素突发问题及数据流相异元素数目变化问题。     

基于计数型Bloom过滤器的网络数据流统计

现有的流统计信息主要侧重于流抽样而忽视全流统计。为此,提出一种使用优化设计的计数型Bloom过滤器流统计方法。针对计数型Bloom过滤器数据增长带来的计数器溢出和假阳性错误率增高的问题,分别设计动态统计和多个计数器协同统计的方案。概要化的存储结构可方便查询,而且其计数型Bloom过滤器简单的数据结构也易于硬件实现。实验结果表明,与传统哈希方法相比,计数型Bloom过滤器流统计方法的时间复杂度更低,可用于网络应用中的快速全流统计。     

基于LRU和扩展CBF的网络大流检测

高速网络流量检测中的大流检测已成为当前一种重要的、高效准确的可扩展流量测量机制,针对CBF（Count Bloom Filter）容易溢出的问题,将扩展的CBF应用于流量测量,防止过滤器溢出,并且结合LRU链表存储机制,共同应用于网络大流检测之中。经理论分析,所研究的流量测量算法LRU_MCBF（Least Recently Used_Multiple Count Bloom Filter）占用空间小,时间复杂度低;通过仿真实验验证了LRU_MCBF在大流测量中漏报率和错报率较低,能实现高速网络环境下大流对象的准确提取。     

基于CBF的分布式元组空间叉积算法

针对分布式报文分类算法内存消耗大、可扩展性差的问题,提出分布式元组空间叉积算法。该算法采用独立域搜索引擎与树状多级聚合网络的分类结构,在聚合节点使用计数型布鲁姆过滤器(CBF)加速搜索,利用剪枝技术降低CBF内存消耗。仿真结果表明,对于 5×104条规模的9域规则库,聚合网络总内存消耗被控制在60 Kb内,该算法的查找速度达到100 Mp/s,且具有良好的可扩展性。     

基于CBF的分布式元组空间叉积算法

针对分布式报文分类算法内存消耗大、可扩展性差的问题,提出分布式元组空间叉积算法。该算法采用独立域搜索引擎与树状多级聚合网络的分类结构,在聚合节点使用计数型布鲁姆过滤器(CBF)加速搜索,利用剪枝技术降低CBF内存消耗。仿真结果表明,对于 5×104条规模的9域规则库,聚合网络总内存消耗被控制在60 Kb内,该算法的查找速度达到100 Mp/s,且具有良好的可扩展性。     

参与式感知中隐私保护的差异化数据分享协议

参与式感知中用户不仅对数据匹配度有要求,对数据差异化也同样有要求,为了既能满足用户对数据匹配度和差异化数据的需求,也能保护用户的偏好隐私,提出了一种隐私保护的差异化数据分享协议。该协议首先将交互双方的数据表示为两个整数集合,并且利用计数布隆过滤器(CBF)计算两个集合的集合交,以集合交的结果作为数据类型匹配度;其次利用CBF能删除元素的功能,计算两个集合的差异化数据值;最后将数据类型匹配度和差异化数据值与预先设定的阈值比较,判断是否符合交互条件,同时,对CBF的构造方法进行了改进,用以保护用户的偏好隐私。理论分析和实验结果表明,与基于布隆过滤器(BF)的非加密匹配协议相比,该协议克服了匹配结果偏大的缺陷,同时计算开销减少了50%以上。该协议在保护用户偏好隐私和满足用户对差异化数据需求的同时,具有较高的匹配精度和效率。     

偏态数据流中的Bloom Filters自适应机制研究

针对Count Bloom Filters(CBF)在对偏态分布的网络数据流进行频度检测时,其使用的固定位数的计数器容易溢出的不足,提出了一种自适应性Bloom Filters(Adaptive Bloom Filters ABF),ABF使用可扩展的逻辑计数器替代CBF中大小固定的物理计数器进行计数,逻辑计数器由数目动态变化的若干个物理计数器组成,初始状态逻辑计数器等同于物理计数器,但逻辑计数器在频度数值上溢时会自适应扩展,覆盖其外部的物理计数器,增加数值容量,保证数值的测量准确性.实验表明ABF能够更好地适应检测频度的变化,并且不显著增加误判率,在对数据偏态分布的频度测量场合比其它Count Bloom Filters更具有优势.