基于布鲁姆过滤器距离的集合变动定量评估算法

布鲁姆过滤器(Bloom filter)对数据集合采用一个位串表示并能有效支持元素的哈希查找,是一种精简的信息表示方案,广泛应用于数据库、网络和分布式系统中.本文研究布鲁姆过滤器的序列分析方法,通过定义布鲁姆过滤器距离,用概率统计方法分析动态数据集合元素增加和删除的变化对布鲁姆过滤器的影响,提出了基于计数式布鲁姆过滤器距离的集合变动定量评估算法.理论分析和仿真实验表明,该评估算法评估准确率高达90%以上.     

基于双布鲁姆过滤器的数据排重技术

针对文件级单布鲁姆过滤器排重算法只能以文件为单位进行数据排重,数据块级单布鲁姆过滤器排重算法耗时过多的缺点,采用2个布鲁姆过滤器,创建文件级和数据块级2级数据排重的算法结构。实验结果表明,双布鲁姆过滤器排重算法可以以数据块为单位对数据排重,在保持低假阳性误判率的同时,相比数据块级单布鲁姆过滤器排重算法耗时缩短了43%~68%。     

基于MD5算法的重复数据删除技术的研究与改进

随着信息技术的快速发展,信息化已成为决定企业生存与发展的关键因素之一;然而随着企业数据信息量的不断地增加,海量数据信息的存储和不断备份已经给企业的存储空间带来了巨大的存储压力;为此,深入研究了重复数据删除技术,并针对目前重复数据删除技术中存在的数据丢失及性能低等问题以及MD5算法流程和重复数据删除策略的分析和研究,提出了一种重复数据删除技术优化模型;测试分析表明,该优化模型实现了高效和安全的重复数据删除功能,节省了企业内部存储空间的存储成本开销。     

布鲁姆过滤器查询算法

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

重复数据删除算法在VTL系统中的应用研究

为了使VTL(虚拟磁带库)系统能更有效地利用磁盘空间,存储更多的数据信息,介绍了一种带有重复数据删除算法的虚拟磁带库应用方法.该方法从性能和效率等多方面考虑,首先把磁带按文件级去重,再将文件切分成块,通过Bloom Filter和MD5算法双重计算,经查找和存储实现数据块级的重复删除.实验测试证明,该方案稳定地实现了数据的去重及加密功能,能有效节省虚拟磁带库的存储空间.     

面向缺失数据的布鲁姆近似成员查询算法

随着网络的发展，越来越多的场景需要在不完整数据下进行近似成员查询，传统成员查询的布鲁姆过滤器不能满足上述要求。提出面向缺失数据的布鲁姆近似查询算法，先对高维不完整数据的缺失部分进行预填充，通过PCA算法，将高维数据转换到低维数据，使用局部敏感哈希函数与标准哈希函数结合的方式将低维数据存储到布鲁姆过滤器中。使用两个真实数据集验证了所提算法的功能，所提面向缺失数据的布鲁姆近似查询算法，能有效地解决存在缺失数据的近似成员查询问题。     

计数布鲁姆过滤器代数运算

文中探讨计数布鲁姆过滤器的代数运算和集合运算的一致性关系,研究使用计数布鲁姆过滤器代数运算进行集合成员查询的性能.理论分析和实验结果表明,计数布鲁姆过滤器的并、交、补、减、异或运算产生的新过滤器依然保持计数布鲁姆过滤器的特征,支持元素的删除操作,不会出现假阴性,能用于集合并集、交集、补集、差集及对称差的成员查询;当使用两个原始的计数布鲁姆过滤器查询补集、差集及对称差元素时,会存在部分本来属于补集、差集或对称差的元素被判为不属于补集、差集或对称差的问题,而使用计数布鲁姆过滤器代数运算后的过滤器进行补集、差集及对称差成员查询,则不存在上述问题,空间效率能提高一倍,时间效率亦能显著地得到改善.计数布鲁姆过滤器代数运算的使用有利于进一步扩展计数布鲁姆过滤器的应用范围.譬如计数布鲁姆过滤器减运算可用作一种新的集合调和方法,用于分布式系统中大型文件的分发.     

基于混淆布鲁姆过滤器的云外包隐私集合比较协议

针对基于混淆布鲁姆过滤器的隐私集合比较（PSI）协议中存在参与方信息获取不对等及协议不能有效应用于云环境等问题,将混淆布鲁姆过滤器算法与代理不经意传输协议相结合,提出了一种基于混淆布鲁姆过滤器和代理不经意传输的云外包隐私集合比较协议。首先,该算法通过引入混淆布鲁姆过滤器的概念,解决了传统标准布鲁姆过滤器产生误判的问题,进而达到高效存储和传输大数据的目的;其次,采用代理不经意传输协议,能够将复杂耗时的计算外包给云代理服务器,使得云租户不需实时在线、仅需进行少量计算;最后,在云外包隐私集合比较过程中,云租户间无需交互,能够公平地得到集合比较结果。理论分析和性能对比表明,该算法的通信复杂度和计算复杂度是线性的,并且协议是安全和有效的。     

分档布鲁姆过滤器的查询算法

布鲁姆过滤器是一种能够简洁地表示集合并支持集合查询的数据结构,广泛应用于数据库、网络和分布式系统中.针对现有的布鲁姆过滤器没有考虑查询失效代价这一缺陷,文中提出一种新的代价敏感的分档布鲁姆过滤器查询算法.它将元素根据不同的查询代价分为不同的子集,通过考查每档子集最低查询失效率的关系,建立由每档子集合最低查询失效假阳性概率表示的集合最低查询失效总代价目标函数,使用类目标函数梯度遗传算法获得每档的最优Hash函数个数ki,完成集合到向量的映射与查找.仿真实验结果表明,使用新结构的查询算法和标准布鲁姆过滤器算法相比,所用的查询计算时间基本相同,因为区分对待集合元素,查询失效总代价仅为标准算法的27%.     

基于HCBF的大流检测机制*

针对计数性布鲁姆过滤器存储数据时计数器溢出的缺陷,提出了一种基于分层计数型布鲁姆过滤器（hierarchy counting Bloom filter,HCBF)的大流检测机制。该方法结合溢出概率函数的特性,将计数型布鲁姆过滤器从一层扩展到多层,并能自适应地配置各层计数型布鲁姆过滤器的参数,能够对大流进行较好的识别。基于互联网数据进行了仿真实验,结果显示：与计数型布鲁姆过滤器相比,在同样溢出概率条件下,提高大流检测精度的同时节省了大量的内存资源。     

中文短文本去重方法研究

针对中文短文本冗余问题,提出了有效的去重算法框架。考虑到短文本海量性和简短性的特点,以及中文与英文之间的区别,引入了Bloom Filter、Trie树以及SimHash算法。算法框架的第一阶段由Bloom Filter或Trie树进行完全去重,第二阶段由SimHash算法进行相似去重。设计了该算法框架的各项参数,并通过仿真实验证实了该算法框架的可行性及合理性。     

一种双层网页去重方法研究

利用Bloom Filter数据结构、shingling算法和MD5编码,构造双层网页去重模型。通过Bloom Filter结构,在网络蜘蛛程序下载网页时,去除重复的网址,并讨论了Bloom Filter出错概率。对已下载的网页用shingling算法去重,阐述了相似网页的判断方法。通过实验,得到了最后的结果,并指出了模型存在的缺点和该方法的后续研究方向。     

基于Bloom Filter的网页去重算法

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

基于Bloom Filter的海量数据分布式快速匹配算法研究

海量数据的快速匹配已经成为当前应用系统一个严峻问题,针对此问题展开深入讨论,将分布式技术与Bloom Filter技术有效结合,给出一种基于Bloom Filter的分布式快速匹配算法。与传统算法相比,此方法大大降低了程序对服务器内存的要求,同时提高了匹配效率,解决了制约应用程序运行效率的瓶颈问题。     

基于副本复制和Bloom Filter 的P2P 概率路由算法

非结构化P2P网络资源定位过程中的查询延迟、查准率和查询成本难以同时被优化,为此,提出一种基于副本复制和Bloom Filter技术的P2P概率路由算法DCBF(data copying and Bloom Filter).DCBF基于有向随机网络,对资源对象进行少量的复制,并将各个副本随机路由给网络中的节点;接收副本的节点,以分布式衰减Bloom Filter向邻近节点传递副本的成员资格信息.理论分析和实验结果均表明,DCBF仅需复制少量的副本,通过以分布式衰减Bloom Filter传递副本的成员资格信息,使得网络中的绝大多数节点能够感知到副本的成员资格信息,从而使得各个节点能够以极低的查询代价,在较低的路由延迟范围内,高概率地将查询路由到目标节点.     

Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows

Detecting duplicates in data streams is an important problem that has a wide range of applications. In general,precisely detecting duplicates in an unbounded data stream is not feasible in most streaming scenarios,and,on the other hand,the elements in data streams are always time sensitive. These make it particular significant approximately detecting duplicates among newly arrived elements of a data stream within a fixed time frame. In this paper,we present a novel data structure,Decaying Bloom Filter(DBF),as an extension of the Counting Bloom Filter,that effectively removes stale elements as new elements continuously arrive over sliding windows. On the DBF basis we present an efficient algorithm to approximately detect duplicates over sliding windows. Our algorithm may produce false positive errors,but not false negative errors as in many previous results. We analyze the time complexity and detection accuracy,and give a tight upper bound of false positive rate. For a given space G bits and sliding window size W,our algorithm has an amortized time complexity of O((G/W))~(1/2). Both analytical and experimental results on synthetic data demonstrate that our algorithm is superior in both execution time and detection accuracy to the previous results.     

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

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

Spark环境下基于多维布隆过滤器的星型连接算法

为了适应联机分析处理(OLAP)系统中实时数据高性能分析需求不断提高的需求,提出一种能够适合Spark环境并结合多维Bloom Filter(MDBF)的星型连接算法SMDBFSJ。首先,根据多个维表构建MDBF,利用其占用空间小的特点,广播到所有节点;然后,在本地节点完成事实表过滤操作,事实表不需要在节点间移动数据;最后,过滤后的事实表与维表采用重划分方式进行连接,进而得到最终结果。SMDBFSJ算法避免了事实表数据移动,通过MDBF减小了需要广播的数据量,充分结合了广播连接和重划分连接的优势。实验结果表明了该算法的有效性,在单机和集群环境下,该算法相比重划分连接均获得了3倍左右的性能提升。     

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

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

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

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