多路平衡型矩阵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的变种及应用。     

一种去除重复URL的算法

通过对Bloom Filter算法及其改进型在Web信息采集时的去重策略进行分析,结合Dynamic Bloom Filter算法,采用动态数组对集合元素进行表示,提出了一种去重应用策略,实现了对集合中重复URL的频度查询和删除操作支持,最后使用该去重策略进行了实验并和其他策略进行了比较,实验证明该应用策略能够在误判率较低的情况下取得较好的去重效果。     

一种基于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 Filter过滤技术

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

云计算环境中支持模糊检索的加密算法

随着云计算的深入发展,隐私安全成为了云安全的一个关键问题。传统的加密方法是常用的保护敏感数据的方法,但是它们不支持对密文的直接操作。为了提供云计算环境中的隐私保护,提出了基于双哈希和带权重的Bloom Filter(DWBF),并构建了基于DWBF的支持模糊检索的加密算法KEDWBF。安全分析和性能评估证明KEDWBF是IND-CPA安全的,并能高效地实现对加密数据的模糊检索。     

双结构网络中URL去重机制研究

针对双结构网络的特点及其URL去重面临的挑战,根据Bloom Filter的工作原理,提出一种基于可扩展的动态可分裂Bloom Filter的URL去重机制,并在原型系统中进行实现和部署。实验结果表明,该机制能够有效适用于大规模、高性能和分布式的双结构网络爬虫应用。     

Bloom Filter和Weighted Bloom Filter的比较与研究

Bloom filter是一个简单的空间效率极高的数据结构,用于判别一个元素是否属于某个集合.Weighted Bloom filter和Bloom filter已经被建议作为共享Web cache信息的一种方式.利用Bloom filter表示共享信息的内容,大大降低了用于存储索引的空间消耗,减少了访问延迟.因为在代理之间只需传输Bloom filter而不是完整的cache目录表.分别从理论和实践方面比较了Bloom filter和Weighted Bloom filter,结果证明Bloom filter比Weighted Bloom filter更好.     

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

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

面向软件定义网络的流表优化方案

针对目前软件定义网络中细粒度的流匹配机制造成的网络流表项空间开销和查询开销爆炸式增长等问题,提出了一种全新的基于布隆过滤器(Bloom Filter)的多级流表结构。该结构为混合流表结构,采用Bloom Filter多级流表结构来存储流表项,主要着眼于提高软件定义网络(SDN)交换机流表的容量和加快流表项的匹配速度;在流表项语义层面,设计并实现了控制器与SDN交换机之间的中间适配层模块来解决语义冲突问题。基于真实流量的实验结果表明,在规则占用空间上,与传统流表相比,Bloom Filter在流表越精细的情况下优化比率越高,最高可达90.7%。随着流表项规则的增加,匹配耗时优化效率提高,匹配时间最多可减少99.4%。该问题的解决可望为SDN网络的大规模实用化部署奠定数据层面的基础。     

一种正则表达式集合快速搜索算法

正则表达式由于其强描述能力和灵活性,在信息检索,程序设计,数据挖掘,深度分组检测,生物信息处理等领域得到了广泛而深入的应用,然而正则表达式,尤其是正则表达式集合,由于搜索速度慢往往成为系统的性能瓶颈。现有的正则表达式搜索算法性能较好的是多模式过滤类型的算法,此类算法严重依赖于两个因素,从NFA的初始状态到终止状态的最短路径Lmin和正则表达式所表达的语言的前缀集合Pref（RE）的大小,Lmin越长,搜索速度越快,Pref（RE）越大,搜索速度越慢。针对上述问题提出了一种基于Bloom filter的正则表达式集合搜索算法,此方法利用Bloom filter的集合查询时间集合大小无关的特点,使得正则表达式搜索速度不受Pref（RE）大小的影响,如果采用多个Bloom filter并行,还可以间接增大Lmin的长度。分析与测试结果表明,本算法较大的加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,可以实现大规模正则表达式集合的快速搜索。     

复合式入侵检测方法的研究

所提出的复合式入侵检测算法是基于行为建模算法和模式匹配算法两种入侵检测算法的有效结合,其中行为建模算法扩展了基于异常的入侵检测算法,而模式匹配算法完全实现了基于特征的入侵检测算法.自适应的行为建模算法根据用户的行为和程序的行为建立合法的行为模板,而不需要任何人工干预.两种入侵检测算法能够有效的降低误报率的发生.采用Servlet Filter技术的安全代理是一个具有一定入侵分析功能的智能插件.     

位图索引技术及其研究综述

位图索引是一种新兴的索引技术,特别适合于只读性海量数据的索引。本文对现有各种位图索引进行了分类,介绍了BBC、WAH、范围编码、区间编码、分箱和基于Bloom Filter编码的位图索引压缩和查询技术。比较了各种位图索引的空间和时间复杂度,讨论了如何根据数据的特性选择合适的位图索引,并指出位图索引的未来研究问题和方向。     

一种新型软件缺陷预测模型研究

对软件度量元的选择问题是软件缺陷预测中的重要研究内容之一。文中通过采用互信息(MI)来计算度量元与度量元、度量元与目标类别之间的相关性,提出了信息损失最小准则,并将该准则作为Filter模型中消除冗余度量元的依据,然后结合现有的Wrapper模型来选择最终对分类有帮助的度量元集合。该方法既能减轻Wrapper模型高计算成本的负担,又能弥补单纯使用Filter模型对软件缺陷的预测能力相对较弱的缺点。实验表明:该方法在召回率、F-measure值上都有明显的提高,具有一定的有效性和实用性。     

一种两阶段的神经网络属性选择方法

神经网络的输入属性选择一直是一个比较困难的问题.由于神经网络反复训练的时间复杂度,Wrap-per方法是不适用的,而单纯使用Filter方法也难以获得很好的分类精度.文中提出了一种两阶段的神经网络属性选择方法,以综合Filter和Wrapper两类方法的优势.该方法首先采用基于不一致率的遗传算法GFSIC来删除属性集合中的无关属性,然后采用基于敏感性度量的属性选择算法SBFCV来删除冗余和无用的属性.研究和实验结果表明,该方法可以有效地删除原始数据中的无关和冗余属性,增强神经网络的泛化能力.     

基于核化局部敏感哈希的快速文档检索方法

在大规模文档中进行快速的相似搜索对绝大多数信息检索应用程序是至关重要的.基于局部敏感哈希的检索方法将高维的空间数据映射到低维的二进制海明空间,从而实现了快速搜索.本文给出了一个基于核化局部敏感哈希的快速文档检索方法,可以在保证时间效率下允许算法使用不同的相似函数进行快速检索.实验结果表明该方法在大规模文档集合检索中具有较好的效率和准确率.     

逆P-集合与信息智能融合挖掘-发现

逆P-集合是一个新的动态数学模型, 它是把动态特性引入到有限普通集合X内, 改进有限普通集合X被提出的。逆P-集合是由内逆P-集合F与外逆P-集合构成的元素集合对。或者, (F,)是逆P-集合, 逆P-集合具有动态特性。在一定的条件下, 逆P-集合被还原成有限普通集合。逆P-集合具有P-集合相反的动态特性。逆P-推理是逆P-集合生成的一个动态推理。利用逆P-集合, 逆P-推理, 本文给出信息智能融合生成, 信息智能融合度概念, 给出信息智能融合挖掘-发现与信息智能融合挖掘-发现定理, 给出挖掘-发现准则。最后,利用这些结果给出信息智能融合挖掘-发现的应用。     

用教育目标分类理论改进C++语言课程教学模式

本文讨论如何应用Bloom认知领域教育目标分类理论来改进C++程序设计语言课程的教学模式。首先讨论Bloom教育目标分类理论的基本框架、应用原理及其在C++课程教学中的应用方法,陈述C++课程的宏观教学目标和课程特点,给出较为合理的理论教学和实验教学学时安排,阐述理论教学和实验教学的总体目标。接着讨论应用Bloom教育目标分类理论构建C++课程理论教学目标的方法,给出一个理论教学要点的教学目标具体构建实例及其用途。最后以一个实验的教学设计实例,详细讨论Bloom教育目标分类理论在实验教学环节中的应用模式,按照学习过程和分类理论的相应关系,提出可行的实验教学应用框架、实验教学目标和理论教学目标的关系、实验活动的结构与实验内容的设计方法、实验任务分配和检查表。     

子群的指数集对有限群的影响

子群的指数是群的一个重要数量性质,主要研究子群的指数集合对有限群的影响,得出了如果两个群的子群的指数集合相等,若其中一个可解,则另一个也可解,且两个群的阶也相等,并对指数集合中的数字的连续性也进行了一定的研究.     

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

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