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

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

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

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

双布鲁姆过滤器法查询集合成员

探讨双布鲁姆过滤器查询法查询集合并集、交集、补集、差集或对称差成员的性能问题。理论分析和实验结果表明,双布鲁姆过滤器查询法能够较好地支持集合并集、交集、补集、差集及对称差的成员查询问题,其中双布鲁姆过滤器并集及交集查询不会产生假阴性,仅有少量假阳性的存在,而双布鲁姆过滤器补集、差集及对称差查询则除存在少量假阳性外,还存在少量假阴性。     

一种基于树形结构的布鲁姆过滤器

本文提出一种基于多层次结构的树形布鲁姆过滤器TBF。多层次结构是近年来布鲁姆过滤器及相关数据结构研究的热点。这一结构使得多层次的存储方式得以实现,减轻了片上存储的负担,而且也加快了片上查找的速度。TBF是针对BloomingTree算法存在的缺陷所改进的一种更高效的算法,它能够在低于CBF的空间需求的条件下实现与CBF相同的功能。实验证明:与BloomingTree算法相比,TBF能够有效地解决BloomingTree算法在逻辑索引时的错误问题,而且比BloomingTree算法时间上更加高效:在层数不变假阳性相同条件下,查询时间平均提高13.4%;在假阳性不变层数相同条件下,插入时间平均提高17.9%,删除时间平均提高12%。     

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

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

一种面向覆盖查询的布鲁姆过滤器设计

在分布式系统中,覆盖查询对于保持文件的完整性以及数据的一致性有重要作用。虽然布鲁姆过滤器可以支持快速的元素从属查询,但是布鲁姆过滤器只能存储和表示离散的数据集合。为此,用前缀集合表示范围规则,并提出一个前缀编码的转化函数,将每一个前缀码转化为唯一对应的二进制串。为了支持覆盖查询,将计数布鲁姆过滤器与一组链表相结合,设计一个BFrange系统来存储包含规则标识以及具体存储元素的二元组。通过BFrange进行覆盖查询,使查询时间与存储的规则个数无关,复杂度仅为O(1)。仿真实验结果验证了BFrange能实现高效和准确的覆盖查询。     

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

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

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

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

基于MD5和布鲁姆过滤器的重复数据删除算法

针对目前重复数据处理技术的低效性和不可靠性,本文提出了一种基于MD5算法和布鲁姆过滤器的重复数据删除算法。新算法采用两级布鲁姆过滤器并有效结合MDS算法的方式,在发挥布鲁姆过滤器空间效率的同时汲取了MD5算法的可靠性,使得文件级别和数据块级别的重复数据删除策略交替工作。测试分析表明,新算法性能稳定并且实现了高效且可靠的重复数据删除功能。     

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

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

BFSQ:处理空间成员查询的方法

随着普适计算技术、定位技术、移动通讯技术的进步,移动对象数据管理技术在诸多领域中得到广泛应用。在移动对象数据管理领域中,隐私保护是一个不可忽视的问题。用户不仅期望获取高质量的服务,同时也期望能够尽量保护自身的隐私信息。研究了空间成员查询,检验在空间某区域内是否存在移动对象。所提出的BFSQ(Bloom filter-based spatial query)方法的一大特点是能够较好地保护移动数据/用户查询的隐私,同时查询结果的质量也维持在一个较高的水平。实验结果表明了新方法的高效率和有效性。     

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

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

基于有状态Bloom filter引擎的高速分组检测

越来越多的网络安全技术通过分析网络分组中的内容来检测报文中是否含有恶意攻击代码.为了能够在线检测攻击,部署在路由器中的分组检测模块对于分组检测的速度也提出了越来越高的要求.虽然在这个领域已有很多研究工作,然而在性能、可扩展性和适用性方面还有很多可研究的空间.提出了一种基于有状态Bloom filter引擎的高速分组检测方法State-Based Bloom filter engine(SABFE).通过并行查找Bloom filter和前缀寄存器堆,以及利用多个并行的Bloom filter引擎进行流并行检测,达到了较高的吞吐性能.同时,利用快速查找表和前缀寄存器堆保存当前子串的匹配状态来检测长的规则.分析和模拟实验表明:该方法在规则长度增加时依然保持了较高的吞吐性能,可以实现线速的分组检测,同时,极大地减少了硬件资源开销,提高了可扩展性.     

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

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

一种基于Bloom过滤器的服务模糊匹配算法

针对基于内容的发布/订阅系统中常用的查找匹配算法要求严格、不能很好地支持服务模糊匹配的问题,提 出了一种支持模糊匹配的服务匹配算法。该算法的基本思想是首先将服务与需求分别用两个Bloom过滤器来表示, 然后通过比较两个Bloom过滤器比特向量的相似程度,估算需求与服务之间的匹配程度。理论分析及仿真结果表 明,此算法可通过简单的Bloom过滤器运算实现基于内容的服务模糊匹配,准确度在95%以上。     

基于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表示与查找法（matrix Bloom filter,MBF）,它使用一个s×m位矩阵对数据集合进行哈希表示与查找,较同类算法SBF和DBF,能继承Bloom filter算法常数查找开销的基本精髓。     

基于Bloom过滤器改进的Growth Codes

Growth Codes是为提高灾难环境中传感器网络的持久性而设计的网络编码方案,但它完全随机的数据交换方式导致较多的传输冗余。针对此问题,通过在Growth Codes算法中引入Bloom过滤器减少冗余数据传输。仿真结果表明,改进的Growth Codes算法在包交换数量和解码速度方面优于Growth Codes。