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

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

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

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

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

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

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

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

基于Bloom filter的远程对称差规模估算法

在内容分发网络、闲谈协议、移动数据同步等分布式系统中,远程主机上集合对称差规模的估算准确程度,直接影响基于CPISync算法的集合调和方法的消息交换轮数以及调和时间。对称差规模的估算误差越低,则集合调和的速度越快。本文提出基于布鲁姆过滤器的准交集查询法,该算法可显著降低对称差规模的估算误差,提高调和算法的效率。     

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

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

区块链应用下的新型区块链布隆过滤器

布隆过滤器(BF)可以高效查询元素是否在指定集合中,广泛应用于区块链成员查询中.针对现有的通用布隆过滤器无法充分利用区块链数据特性及通用设备计算资源的问题,提出一种新型区块链布隆过滤器(BBF).首先,改进布隆过滤器数据结构,对BBF以组为单位进行细分,从而将元素的映射范围限制在一个组内,减少访存失败次数,提高访存效率.其次,利用区块链数据的特性,提出一种简化的三阶段哈希映射函数,减少计算开销.在此基础上,使用单指令多数据流(SIMD)技术实现元素插入和查询操作的并行处理,提高BBF构建及查询速度,最终实现区块链上数据的高效查询和分析.实验结果显示,BBF与BF、OMBF两个主流布隆过滤器相比,其正向查询时的成员查询速度分别提高4倍、3倍,性能提升显著.     

基于值域二次哈希方法的布鲁姆过滤器

本文针对扩展式布鲁姆过滤器(EBF)内存消耗过大,提出一种基于值域哈希二次过滤的布鲁姆过滤器数据结构(VHBF)和相关算法,VHBF通过在布鲁姆过滤器中对集合中的每个特征进行k次哈希,并将此k次哈希值转化为相应特征的镜像特征。然后对此镜像进行二次过滤运算,运算后的结果保存在另一布鲁姆过滤器中。在对特征进行检索时,由于无需保存特征本身,因而空间效率比EBF更高。实验表明,VHBF的假阳性误判率的比扩展型布鲁姆过滤器(EBF)低,而VHBF内存消耗也低于EBF。     

基于单哈希计数布隆的DDS自动发现算法

针对DDS简单自动发现算法中网络传输量大、内存消耗高以及端点匹配时间长的问题,提出一种基于单哈希计数布隆过滤器的DDS自动发现算法——SDP＿OHCBF。通过将标准布隆过滤器升级为计数布隆过滤器以支持元素删除操作,使用单个哈希函数和取模运算代替标准布隆过滤器中的多个哈希运算,加快布隆过滤器的元素查询过程。仿真验证结果表明,该算法降低了DDS自动发现过程的网络传输量与内存消耗,支持元素删除操作,提高了数据发布/订阅的实时性。     

布鲁姆过滤器查询算法

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