Bloom Filter及其应用综述

Bloom Filter对数据集合采用一个位串表示并能有效支持集合元素的哈希查找操作。本文对Bloom Filter及其改进型进行了综述性分析研究．探讨了它的实用性。较为详细地阐述了它在P2P网络文件存储系统OceanStore和文本检索系统中的应用情况。最后指出了进一步的研究方向。     

基于Bloom Filter和概率分发队列的P2P网络快速查找算法

无结构化P2P网络资源定位过程中的响应时间、查准率及覆盖率难以同时被优化。提出一种面向有向无环随机网络的基于Bloom Filter和概率分发队列的快速查找算法BFPDQ(Bloom Filter and Probabilistic Distribution Queue),它用Bloom Filter表达和传递节点命中资源信息及查找请求信息,计算新查询消息与历史查询消息Bloom Filter语义向量相似度,并应用底层网络路径性能信息指导上层转发决策。概率分发队列(Probabilistic Distribution Queue,PDQ)把传统walkers表示成为查找消息分发队列,查找请求者协调各分发队列的查找方向和深度,并融合各队列查找过程中得到的定位消息。仿真实验表明,BFPDQ算法在保持较少冗余信息的同时有效缩短了响应时间。     

基于Bloom Filter的去重方法研究

在个性化新闻推荐系统中,文章去重是一个重要的模块,避免了同一篇文章被重复推荐的现象。在海量用户场景下,采用传统的基于队列的去重方法将会消耗大量的内存。Bloom Filter是一种空间效率很高的随机数据结构,适用于允许有一定误判率的场景。本文基于Bloom Filter,设计双Bloom Filter位数组结构和Bloom Filter位数组链结构。实验证明,基于Bloom Filter位数组链的去重方法,不仅大大降低了程序对服务器内存要求,而且具有较好的灵活性和扩展性。     

针对动态集的矩阵型Bloom filter表示与查找

提出一种针对动态集合的矩阵型Bloom filter表示与查找法（matrix Bloom filter,MBF）,它使用一个s×m位矩阵对数据集合进行哈希表示与查找,较同类算法SBF和DBF,能继承Bloom filter算法常数查找开销的基本精髓。     

基于伪名的VANET恶意节点检测研究

针对车载自组网(VANET)节点通信时间短、实时性要求高的特点,设计一种压缩型Bloom Filter机制,并将其应用于基于伪名的VANET恶意节点检测中。该Bloom Filter机制能减少伪名恶意节点集合的数据存储量,以及节点数据更新时的信息交换量,同时获得更高的恶意节点检测率和更低的假阳性率。分析结果表明,该方法可降低VANET节点间实际传输的数据量和通信开销,提高通信实时性。     

事务存储中的一种自适应冲突检测算法

事务存储被认为是极具前景的多核处理器并行编程的手段,但存在开销过大的问题。采用Bloom Filter对事务间访问共享变量进行冲突检测,能够有效地降低开销,但其存在误判会导致不必要的事务作废,因此要尽可能减少。简要介绍了Bloom Filter和事务存储,提出了一种事务存储的自适应冲突检测算法ACDA,根据事务读写集合大小自适应地调整Bloom Filter的位串大小,在较低开销的情况下,保持误判率不增加。分析了软件事务存储中实现ACDA的特点,初步实现ACDA,与主流软件事务存储实现RSTM相比,在事务存储测试程序STAMP中,开销可接受的前提下,减少因误判而作废的事务最高达93%。给出了对ACDA哈希函数进一步优化的思路。     

ODBF:基于操作型衰落Bloom Filter的P2P网络弱状态路由算法

在P2P网络中,基于衰落Bloom Filter的弱状态路由算法试图将每条查询消息沿着成员资格信息量最强的方向传递,并最终以较低的传输代价和传输时延确保较高的查准率.研究发现衰落Bloom Filter在传递过程中存在严重的多径叠加和噪音问题,这直接导致查询消息以很高的概率沿着错误的方向传播,甚至会退化为泛洪路由算法.为解决这一挑战性难题,文中提出了基于操作型衰落Bloom Filter的弱状态路由算法ODBF(Operative Deca-ying Bloom Filter).ODBF通过分别保存对象的衰落Bloom Filter及源节点等信息,使得ODBF能够有效解决基于衰落Bloom Filter的路由信息在P2P网络中的多径叠加和信息回流问题,有效抑制噪音的影响,进而使得基于弱状态的路由能够以很高的概率沿着正确方向进行.     

BFPC:一种新型的基于Bloom Filter的报文分类算法

Bloom Filter是一种支持高速数据查询的数据结构,已被广泛应用到各个领域,包括路由查找、串匹配[1]等。本文将重点研究Bloom Filter在报文分类领域中的应用,提出一种新型的报文分类算法——BFPC,阐述BFPC算法的基本思想,并通过实例对该算法进行了描述。最后,对BFPC算法与其他报文分类算法进行了性能比较。     

一种新型精确深度包检测引擎研究与设计

传统的深度包检测算法通常存在频率带宽瓶颈、不能精确匹配、不切实际的存储要求等其中之一或数个缺点.本文基于哈希与Bloom Filter提出一种新型精确匹配结构:Bloom Filter分类器,首先基于哈希对特征串分组,再用多组Bloom Filter对输入串分类,在每长度定位到唯一可能的匹配串并对比验证.对Snort、ClamAV集合进行了存储实验评估,以约1.22(字节/字符)的低存储代价实现对万条字符串集的精确匹配.该结构具有精确匹配、多字节匹配扩展简单、不存在带宽瓶颈等优点.     

一种轻量级的SYN Flooding攻击检测方法

提出了一种轻量级的源端DDoS攻击检测的有效方法.本方法基于Bloom Filter技术对数据包信息进行提取,然后使用变化点计算方法进行异常检测,不仅能够检测出SYN Flooding攻击的存在,而且能够避免因为正常拥塞引起的误报.重放DARPA数据实验表明,算法的检测结果与类似方法相比更精确,使用的计算资源很少.     

多模式匹配算法及硬件实现

介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法--Aho-Corasick基于自动机的算法和Wu-Manber基于hash的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对各种多模式匹配算法的时空复杂度进行了分析比较.通过几个硬件实现的实例介绍了多模式匹配的硬件实现方法及策略.最后对多模式匹配的发展趋势进行了展望.     

基于源目的IP地址对数据库的防范DDos攻击策略

提出了一种基于源目的IP地址对数据库的防范分布式拒绝服务攻击(distributed denial of service attacks,简称DDos)攻击策略.该策略建立正常流量的源目的IP地址对数据库(source and destination IP address database,简称SDIAD),使用扩展的三维Bloom Filter表存储SDIAD,并采用改进的滑动窗口无参数CUSUM(cumulative sum)算法对新的源目的IP地址对进行累积分析,以快速准确地检测出DDos攻击.对于SDIAD的更新,采用延迟更新策略,以确保SDIAD的及时性、准确性和鲁棒性.实验表明,该防范DDos攻击策略主要应用于边缘路由器,无论是靠近攻击源端还是靠近受害者端,都能够有效地检测出DDos攻击,并且有很好的检测准确率.     

数据流中频繁项近似挖掘算法

提出新的数据结构ESBF(Extensible and Scalable Bloom Filter)-可扩展的Bloom Filter.并提出基于ESBF的数据流中频繁项近似挖掘算法,该算法在保证较高精度的同时,实现比同类算法具有更好的时间效率且在一般情况下具更好的空间效率,并证明只需ln(-M/lnρ)·e/ε·1/(ε·M)个计数器就能保证满足用户规定的误差ε及可信度ρ要求.     

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系统中.     

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

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

基于TCBF算法的网络流信息统计

针对传统的网络流信息统计算法容易溢出、频繁更新等特点,提出一种基于TCBF(time bloom filter & counting bloom filter)的网络流信息统计算法用于实时在线统计高速网络流信息.算法一方面利用短流超时特点使用time bloom filter抽取短流信息;另一方面利用网络流量分布呈现重尾分布的特性使用counting bloom filter 过滤长流报文.分析了算法的复杂度和误判率,并通过模拟数据分析了算法参数配置对于流信息统计准确性和抽样率的影响.理论分析和仿真结果表明,与标准counting bloom filter相比,TCBF算法可以在使用较少的存储空间的条件下,及时、准确地对网络流量信息进行统计,满足实际测量需要.     

采用RBF来支撑互联网络上的电路模拟服务

Circuit Emulation Service (CES) aims to enable packet switched networks to provide guaranteed services with comparable qualities of circuit switched networks. Our paper addresses the key issue of QoS of CES flows over Internet. Enlightened by the time division idea popularly used in circuit switched networks, we propose a time division based control mechanism to provide guaranteed QoS for the constant-rate CES flows. The control mechanism is able to estimate the arrival times of the coming packets in CES flows, and reserve the time slots for them. Accordingly, it enables the packets to consume the reserved time slots of their own, so the CES flows are guaranteed to be processed. Refreshing Bloom Filter (RBF), an efficient data representation structure, is proposed to support the time division control mechanism. It consists of multiple bloom filters, and can efficiently record the arrival time slots of millions of packets. The proposed control system model could be a practical tool to support Circuit Emulation Services over Internet.     

基于P2P技术的安全凭证回收方法

安全凭证回收的实现是公钥基础设施(PKI)所面临的一个主要的问题。许多种回收策略已经被提出,CRL是其中最简单,最容易实现的方法。但是如何有效地分布已经回收的安全凭证信息是这种方法所面临的一个挑战。论文提出利用P2P技术组织终端实体,并利用bloomfilter压缩向量代表安全凭证回收链CRL。通过实体间的协作和bloomfilter的压缩功能减少REPOSITORY和网络的负担。此外,为了有效地向终端实体发布CRL的bloomfilter压缩向量,提出一种高效的广播算法,在最小的TTL内尽量将向量广播到每一个节点。论文最后进行了模拟试验,实验证明提出的解决方案是有效的。     

通过V-GridFTP提高数据访问性能

数据网格需要文件传输服务(FTP)。但是,目前数据网格中使用的FTP服务具有存储内容独立的局限性,这一局限性造成了诸如数据定位困难、服务器之间负荷不均衡等问题。该文提出了V-GridFTP的概念,将原本内容独立的物理服务器联结起来协同工作,在信息服务的协助下,通过数据分区、复制以及GridFTP等技术,实现了资源分布动态自适应调整,为用户提供高性能、高可用性、高可靠性的FTP服务。这里开发了一个原型系统。测试显示系统运行良好。     

基于Bloom filter的远程对称差规模估算法

在内容分发网络、闲谈协议、移动数据同步等分布式系统中,远程主机上集合对称差规模的估算准确程度,直接影响基于CPISync算法的集合调和方法的消息交换轮数以及调和时间。对称差规模的估算误差越低,则集合调和的速度越快。本文提出基于布鲁姆过滤器的准交集查询法,该算法可显著降低对称差规模的估算误差,提高调和算法的效率。