Bloom搜索过滤器的优化设计与实现

基于Bloom搜索过滤器的搜索过滤机制会发生误判,且在查询目标进入过滤器后,查询整个关键字的步骤会耗费太多成本。该文提出一套新的搜索过滤器架构。经实验验证,该过滤器能减少误判率的发生,降低整个过滤器的搜索成本,提高搜索过滤器的整体性能。     

基于Bloom Filter路由表的P2P搜索算法

研究非结构化P2P网络的搜索机制,提出基于布莱姆过滤器(BF)路由表的改进算法。该算法利用BF技术生成路由条目并在一定范围内相互交换本地路由表,使节点能够了解一定范围内的节点共享信息,实现有针对性的搜索,避免传统的盲目性搜索。仿真结果表明,该算法查询搜索时产生的消息数量比传统算法减少一个数量级,并能够获得较好的查全率。     

Bloom Filter及其在网络中的应用综述

Bloom filter是用来表示集合的数据结构,并以较小的误判率为代价,实现较少的存储空间开销和常数的查找时间。对Bloom filter及其改进结构作了分析研究,并着重介绍最近几年在网络中包括在流量测量和网络安全方面出现的新应用。在一定误判率存在的情况下,Bloom filter为大规模数据集合元素表示、成员查询及多重集和动态集的元素频率查询等提供了解决方案。     

基于Counting Bloom Filter的DNS异常检测

鉴于失败的DNS查询（failed DNS query）能提供恶意网络活动的证据,以DNS查询失败的数据为切入口,提出一种轻量级的基于Counting Bloom Filter的DNS异常检测方法。该方法使用带语义特征的可逆哈希函数对被查询的域名及发起查询的IP进行快速的聚类和还原。实验结果证明该方法能以较少的空间占用和较快的计算速度有效识别出DNS流量中的异常,适用于僵尸网络、分布式拒绝服务（DDoS）攻击等异常检测的前期筛选和后期验证。     

布鲁姆过滤器查询算法

从理论和应用两方面系统地综述了布鲁姆过滤器查询算法迄今为止的主要研究成果,分析了目前布鲁姆过滤器查询算法的研究现状,最后展望了布鲁姆过滤器查询算法未来可能的研究方向.     

基于Bloom Filter的报文分类算法

针对传统报文分类算法在实际运行中存在的问题,提出一种基于Bloom Filter的报文分类算法。将该算法的思想应用于入侵防护系统硬件模型,建立相应的流信息预处理引擎,并介绍具体的实现方法。实验结果表明,该算法是有效实用的。     

布隆过滤器研究综述

布隆过滤器（BF）是一种基于哈希策略的二进制向量数据结构,凭借分摊哈希碰撞的思想、存在单向误判性的特点以及极小常数查询时间复杂度,常用于表示集合元素并作为进行集合元素查询操作的“加速器”。作为计算机工程中解决集合元素查询问题最好的数学工具,BF在网络工程、存储系统、数据库、文件系统、分布式系统等领域得到了广泛的应用和发展。近几年来,为了适用于各种硬件环境和应用场景,BF出现了大量基于改变结构、优化算法等思想的变种方案。随着大数据时代的发展,对BF自身特点和操作逻辑进行改进已经成为现有集合元素查询研究的一个重要方向。     

基于Bloom Filter的网页去重算法

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

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

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

基于Bloom Filter的混合云存储安全去重方案

针对现有云存储系统中数据去重采用的收敛加密算法容易遭到暴力破解以及猜测攻击等不足,提出一种基于布隆过滤器的混合云存储安全去重方案BFHDedup,改进现有混合云存储系统模型,私有云部署密钥服务器Key Server支持布隆过滤器认证用户的权限身份,实现了用户的细粒度访问控制。同时使用双层加密机制,在传统收敛加密算法基础上增加额外的加密算法并且将文件级别去重和块级别去重相结合实现细粒度去重。此外,BFHDedup采用密钥加密链机制应对去重带来的密钥管理难题。安全性分析及仿真实验结果表明,该方案在可容忍的时间开销代价下实现了较高的数据机密性,有效抵抗暴力破解以及猜测攻击,提高了去重比率并且减少了存储空间。     

基于DCBF的流抽样测量算法

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

基于边缘直方图的粒子滤波跟踪算法及其实现

以颜色直方图为特征的运动目标跟踪算法容易受到光线变化及视场内其它同色目标的干扰.采用运动目标的边缘方向直方图作为特征,利用序列重要性采样原理和粒子滤波算法实现了对人体运动目标的跟踪.实验显示了该算法在光线变化及存在同色目标干扰时能够有效跟踪目标.在算法实现过程中,采用积分图计算边缘方向直方图,减少了计算时间,提高了计算速度,达到了实时跟踪的效果.     

L-priorities bloom filter: A new member of the bloom filter family

A Bloom filter is a space-efficient data structure used for concisely representing a set as well as membership queries at the expense of introducing false positive. In this paper, we propose the L-priorities Bloom filter (LPBF) as a new member of the Bloom filter (BF) family, it uses a limited multidimensional bit space matrix to replace the bit vector of standard bloom filters in order to support different priorities for the elements of a set. We demonstrate the time and space complexity, especially the false positive rate of LPBF. Furthermore, we also present a detailed practical evaluation of the false positive rate achieved by LPBF. The results show that LPBF performs better than standard BFs with respect to false positive rate.     

一种渐进式的抽样策略及其性能分析

介绍了一种新的特征匹配算法-渐进式抽样一致算法,该算法首先按匹配度大小将初步匹配集合中的匹配对按匹配度作降序排列,然后根据规定的增长函数从前至后作抽样。详细介绍了算法的设计思想、增长函数的设计策略、抽样中指标准。将该算法成功的应用到图像配准问题中,实验结果表明该算法较传统算法在抽样终止标准相同条件下时间复杂度有较大改善。     

Bias-compensated constrained least mean square adaptive filter algorithm for noisy input and its performance analysis

A bias-compensated constrained least mean square (BC-CLMS) adaptive filter algorithm for noisy input is proposed. To derive the proposed algorithm, we present a novel cost function whose gradient vector is unbiased. Thereby, the proposed algorithm can mitigate the effect of input noise and obtain an unbiased estimation. Then, the detail performance analysis of the proposed algorithm is also provided. Finally, simulations are carried out to illustrate the advantage of the proposed algorithm. In addition, the correctness of performance analysis is also verified by simulations.     

基于最小延迟代价的Web缓存替换算法研究

命中率、字节命中率和延迟时间是Web缓存系统中最重要的性能指标,但是却难以准确、合理地度量不同大小的Web对象的访问延迟.引入字节延迟的概念,为不同的对象延迟建立了一个比较合理的评价标准.提出最小延迟代价的Web缓存替换算法LLC,使用户访问的延迟时间尽可能缩短.实验结果表明,与常用的缓存替换算法相比,LLC算法在有效减少用户感知的访问延迟方面具有较好的性能表现.     

一种改进的粒子滤波算法及其性能分析

针对非线性、非高斯系统状态的在线估计问题,提出了一种改进的粒子滤波算法。该算法采用Unscented卡尔曼滤波器（UKF）产生系统的状态估计,并在量测更新过程中加入衰减记忆因子,消弱滤波器对历史信息的依赖,增强当前量测信息对滤波器的修正作用,从而产生一个优选的建议分布函数,较好地抑制了粒子退化问题。理论分析和实验表明：引入记忆衰减因子的粒子滤波,即衰减记忆无味粒子滤波（MAUPF）的性能明显优于标准的粒子滤波以及Unscented粒子滤波。     

基于CIC抽取滤波器的谐波分析算法

为消除非同步采样引起的频谱泄漏,提高电网信号的谐波分析精度,提出了基于级联积分梳状(CIC)抽取滤波器的谐波分析算法。在前端AD过采样的情况下,该算法采用逆向搜索的方法实现非同步采样数据的整周期截断,用基于CIC抽取滤波器变频的方法实现信号采样频率与信号基波频率同步,通过快速傅立叶变换(FFT)得到信号频谱,计算基波及各次谐波的幅值和相位。仿真实验结果及误差分析表明,相对于常规的分析方法,该算法具有较高的测量精度。该算法对于非稳态周期信号的谐波分析只需单周期采样,简单易实现,是一种有效的测量方法。     

MPI_ALLGATHER实现算法的改进与性能分析

首先分析了影响MPI组通信性能的各方面因素,提出了一种衡量算法性能的模型。基于这种分析及模型,提出了一种将邻居交换和递归倍增两种算法结合的新的MPI_ALLGATHER实现算法。新的算法比邻居交换算法通信次数少,比递归倍增算法具有较好的通信局部性。通过在高性能机群系统中的测试,发现新算法在多种情况下比邻居交换算法具有更优的性能,在中等长度消息通信时具有最优的性能,在长消息通信时性能比递归倍增算法和Bruck算法的性能更优,且在长消息通信时多数情况下性能最优。     

MPI_ALLTOALL实现算法的改进号性能分析

通过分析全互换通信中4种算法的性能,提出了一种改进算法.该改进算法递归倍增的创建子进程,通过增加通信进程数目来减少通信次数.对比分析改进算法与成对互换算法的通信次数,改进算法的通信次数是成对互换算法的一半.实验机群是在版本为MPICH2-1.0.8并行环境下测试,结果表明,消息类型为长消息通信且通信进程教为2的幂次方时,该改进算法比成对互换算法的性能更优.