浅析Bloom Filter

Bloom Filter是一种空间和时间效率很高的二进制项量数据结构,它利用位数组很简单地表示一个集合,并能检索一个元素是否属于这个集合。Bloom Filter的高效检索是由有一定误报率换来的。因此,Bloom Filter只适合那些允许一定误报率的应用场合。     

Bloom Filter技术及应用

Bloom Filter采用位串向量表示数据集合,能够实现高效集合查询的数据结构。首先介绍了标准布隆过滤器的概念和工作原理,然后通过实验分析布隆过滤器的错误率、空间向量和哈希函数数量三者之间的动态相关关系,并对独立空间布隆过滤器和标准布隆过滤器性能进行对比,最后讨论了Bloom Filter的变种及应用。     

多路平衡型矩阵Bloom Filter

海量数据的高效表示和查找成为目前存储系统面临的重要挑战.针对存储系统中大规模动态数据集的表示和查找效率问题,提出一种多路平衡型矩阵Bloom Filter结构(M-BMBF)及其插入和查询算法.M-BMBF根据数据集合大小建立一个r×m矩阵型Bloom Filter,设计多个定位哈希函数将该矩阵Bloom Filter分为多组(多路)以实现平衡插入和高效查询操作.为减缓Bloom Filter中比特的消耗速度,使用一种"最长位匹配"填充算法,新元素的插入将从多路备选Bloom Filter中选择新置为1比特个数最少的Bloom Filter中进行.实验结果表明,相较典型拆分Bloom Filter,M-BMBF能在维持算法消耗时间为常量的基础上,有效节省存储空间,降低误判率.     

基于Bloom filter引擎的分布式网络取证系统

针对目前网络取证的特点和技术挑战,提出和设计了一种基于Bloom filter引擎的分布式网络取证系统.该系统以Bloom filter引擎为核心,能够实时的对网络原始数据进行过滤,映射压缩和存储,捕获完整的证据,节省存储空间,有效支持网络取证的事后分析查询.     

分布式环境下改进的Bloom Filter过滤技术

分析了Bloom Filter技术在特殊的分布式系统———P2P系统中的应用.基于Bloom Filter提出了一种新的Division Bloom Filter(DBF)技术,DBF技术采用了一组相互独立的哈希函数来计算数据对象的地址序列,然后使用这组地址序列将数据对象存储到一个分片的位向量中,所以DBF技术可以有效减少数据对象的存储空间.实验证明,DBF不仅可以解决Bloom Filter在分布式环境下的动态更新问题,还可以有效减少BloomFilter的错误率以及改善其稳定性.最后还使用数据压缩技术进一步减少在P2P系统中使用DBF技术的结点间通信代价.     

基于Bloom Filter的路由循环实时被动检测方法

为了解决网络中路由循环的实时检测问题,提出了一种基于Bloom Filter的路由循环实时被动检测方法.这种方法利用Bloom Filter存储资源占用小和查找时间消耗少的优点快速地发现源、宿地址,源、宿端口号均相同的疑似循环路由报文,再通过对报文TTL值递减特征的判断确定循环路由现象的存在.对于Bloom Filter本身存在误判率的问题,该方法采用增大位向量的长度的方法予以解决.实验结果表明本方法可以准确地发现循环路由,与传统主被动探测路由循环方式相比,减少了对网络带宽资源的占用,同时极大提高了算法的实时性.     

基于Bloom Filters的流抽样算法研究

本文提出了基于Bloom Filters的流抽样算法,对测量间隔内到达的报文进行抽样,并采用Bloom Filters哈希结构映射到流信息表来创建和维护流信息。该方法具有灵活性、简单性,在误差允许的情况下,有效地减少了流测量所需的存储空间。     

一种基于Bloom Filter的正则表达式集合快速搜索算法

正则表达式搜索算法的性能与从非确定性有限状态自动机(NFA)的初始状态到终止状态的最短路径Lmin成正比,与正则表达式所表达的语言的前缀集合Pref(RE)成反比,而一般情况下Pref(RE)较大,确定Pref(RE)中的元素在目标文本中的出现位置比较困难.文中提出了一种基于Bloom Filter的正则表达式集合搜索算法,此算法利用Bloom Filter集合查询时间与集合大小无关的特点,可以快速准备定位Pref(RE)的出现位置,使得搜索速度不受Pref(RE)的影响,如果采用多个Bloom Filter并行,还可以间接增大Lmin.分析与测试结果表明,该算法较大地加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,在Lmin较长、Pref(RE)较大时,搜索速度可以提高数倍至数十倍,适合大规模的多正则表达式的快速搜索.     

命名数据网络中基于多级计数Bloom过滤器的名字查找方法研究

针对目前NDN中大多数基于Bloom过滤器的名字查找方法仅考虑速率而忽略冲突概率的局限,提出了一种考虑名字冲突概率并基于多级计数Bloom过滤器的名字查找方法.该方法的实验结果表明:相对于目前广泛研究的计数Bloom过滤器、哈希函数和d-left计数Bloom过滤器,所提方法能有效降低冲突概率.     

基于Servlet Filter的安全Web访问

安全web访问是web应用开发中的一项十分重要的内容.为此本文介绍了一种基于servlet filter的安全web访问结构,此结构利用servlet filter、访问处理模块和安全策略来保证访问安全性.本文随后通过安全访问实例描述了这一结构的实现过程.这一结构将为中小型安全web访问提供一种良好的解决方案.     

基于布鲁姆过滤器的RFID中间件数据过滤算法设计

RFID（Radio Frequency Identification,RFID）中间件在RFID系统中起着承上启下的作用,数据过滤作为RFID中间件的核心功能,对其算法的研究一直是RFID领域研究的热点与重点。通过对现有过滤算法的分析,提出基于布鲁姆过滤器的数据过滤算法,鲁姆过滤器在空间和时间上有着更低的复杂度,并通过对布鲁姆过滤器算法的分析和仿真,选择了最优的布鲁姆参数,降低了算法的假阳性误判率。     

Bloom Filter在手机垃圾短信过滤中的应用

针对当前手机垃圾短信过滤系统的不足和手机资源紧张的特点,构建了基于独立空间布隆过滤器的手机垃圾短信过滤系统,具体给出了系统结构、工作流程及其算法。实验分析结果表明,在允许一定"假阳性"误报率的条件下,该系统可以有效节省手机资源。     

一种基于bank-column缓存划分的多核共享缓存能耗优化方法

针对支持IABA(Interference-Aware Bus Arbiter)总线的多核共享缓存能耗问题,提出了一种基于bank-column缓存划分的多核共享缓存能耗优化方法.该方法在保证硬实时任务能够在截止期前完成的前提下,通过优化bank-column缓存划分来减少共享缓存能耗.实验结果表明,在保证硬实时任务能够在截止期前完成的前提下,提出的优化方法能够减少共享缓存能耗,与优化路-组缓存划分相比,35nm制造工艺时至少能够减少约10%的共享缓存能耗.     

基于多核处理器的动态共享缓存分配算法

对于具有共享缓存结构的多核处理器,存在并行应用对共享缓存冲突访问导致性能下降的现象.为合理地分配共享缓存以有效地解决这类问题,提出了一种共享缓存分配方法,通过将并行应用对共享缓存访问未命中的情况进行分类与追踪,并根据建立的性能增益模型在行的粒度上进行动态地分配共享缓存,使系统的整体性能得到改善.实验结果表明,新算法能合...     

基于Bloom Filter的XML数据流压缩技术研究

现今,XML数据管理的一个重要问题是如何对XML数据进行高效的查询处理。以XML数据流的压缩为目标．提出了一种基于BloomFilter的XML数据流压缩技术,利用Dom4j的Aelfred2解析器对XMLSchema进行解析,构建dom4j树。采用压缩布鲁姆过滤器思想进行算术编码,达到压缩的目的。     

分布式共享存储器型多处理机的研究

文章提出了一台分层结构的分布式共享存储器的型多处理机ＤＳＭＡｒｃ的系统结构，该系统采用总线监听和目录式相结合的ｃａｃｈｅ一致性协议，来保持分布式局部ｃａｃｈｅ与共享主存内容一致，为压缩目录所需存储空间，文章提出了一种新的目录存储结构－目录ｃａｃｈｅ在ＳｕｎＳｐａｒｃ工作站上对ＤＳＭＡｒｃ原型进行了模拟，根据模拟结果对ＤＳＭＡｒｃ的性能作了初步分析。     

基于博弈论的城市褐色土地再开发利益冲突解析

开发价值和污染风险并存是城市褐色土地的两面性,也是导致褐色土地再开发中冲突事件不断发生的主要原因.本文在明确城市褐色土地再开发中的利益相关者类型的基础上,分析了利益主体间的关系及其冲突类型,并引入博弈论对各利益主体间的冲突根源进行讨论,最后指出,从法律、资金、公众、政府等方面构建城市褐色土地再开发管治体系是促进褐色土地成功开发的有效途径.