过滤器数据结构研究综述

过滤器数据结构可以近似地判断某个元素是否属于给定集合。典型的过滤器数据结构，如布隆过滤器、布谷鸟过滤器、商过滤器，以牺牲查询准确性为代价换取更低的内存空间消耗和查询时间开销。因此，得益于空间时间高效性，过滤器数据结构现已被广泛应用于计算机网络、物联网、数据库系统、文件系统、生物信息学、机器学习等领域的近似成员资格查询操作中。自20世纪70年代以来，过滤器数据结构受到了广泛的研究，在诸多领域取得了重要的进展，其研究思路也在不断变化。文中整理了近五十年来关于过滤器数据结构的经典研究成果，从过滤器数据结构的原理出发对已有工作进行分类总结，并比较不同工作之间的引证关系和改进思路，最后讨论了过滤器数据结构的未来研究方向。     

基于Bloom过滤器的精确位图索引

针对基于Bloom过滤器的位图索引方法查询结果不精确的问题,提出一种精确位图索引算法——FPT-Index。该算法采用Bloom过滤器对基本位图索引进行压缩,同时引入假阳表,对查询结果进行筛选,从而达到精确查询的目的。通过理论分析得出,在给定关键词出现频率的前提条件下,可计算出最小压缩率以及所需哈希函数的个数。实验结果表明,FPT-Index相较于WAH方法在压缩率和查询效率两方面都有较好的表现。     

布隆过滤器研究综述

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

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

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

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

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

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

布隆过滤器(BF)可以高效查询元素是否在指定集合中,广泛应用于区块链成员查询中.针对现有的通用布隆过滤器无法充分利用区块链数据特性及通用设备计算资源的问题,提出一种新型区块链布隆过滤器(BBF).首先,改进布隆过滤器数据结构,对BBF以组为单位进行细分,从而将元素的映射范围限制在一个组内,减少访存失败次数,提高访存效率...     

基于并行Bloom过滤器组的深度数据包检测算法

针对基于软件、硬件的深度数据包检测存在处理速度慢或规则集更新困难等方面的局限性,提出一种在多核平台上基于并行Bloom过滤器组的深度数据包检测算法。算法中首先将规则集按规则的长度分组,构造一个并行Bloom过滤器组,组中每个计数式 Bloom过滤器表示特定规则长度的规则集。为了减少执行过程中的冲突概率和计算量,构造了高性能的哈希函数,然后基于多核平台的并行处理能力使用并行编程实现了该算法。理论分析和实验结果表明该算法是一种时空高效的算法。     

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

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

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

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

智能数据库学习型索引研究综述

建立高效的索引结构是提升数据库存取性能的关键技术之一.在数据呈爆发式增长、海量聚集、高维复杂的大数据环境下,传统索引结构（例如B+树）处理海量数据时面临空间代价高、查询效率低、存取开销大等难题.学习型索引技术通过对底层数据分布、查询负载等特征进行建模和学习,有效的提升了索引性能,并减少了访存空间开销.本文从学习型索引技术的基础模型入手,对RMI基础模型实现原理、构造和查询过程进行了分析,并总结了基础模型的优点和存在的问题;以此为基础,按照索引结构特点对学习型索引技术进行分类,从索引创建方式和更新策略两方面对学习型索引技术进行了系统梳理,并对比分析了典型学习型索引技术的优点及不足之处.另外,本文总结了学习型索引技术的扩展研究.最后,对学习型索引的未来研究方向进行了展望.     

基于双Bloom过滤器与离散对数的虹膜模板保护方法

针对不可逆变换虹膜模板保护方法在虹膜识别系统中的模板泄露问题,提出一种融合人脸特征信息的基于双Bloom过滤器与离散对数的虹膜模板保护方法.采用Log-Gabor变换提取用户的虹膜特征,采用等价模式的LBP算法提取用户人脸特征,将量化的人脸特征通过离散对数转化为十进制密钥特征,然后将其嵌入到虹膜双Bloom过滤器变换中...     

基于Bloom过滤器改进的Growth Codes

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

布鲁姆过滤器查询算法

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

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

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

基于Multi-Bloom Filters的数据流聚集查询

针对数据流上任意时闯段的历史数据的聚集查询问题,提出基于BF技术的概要存储模型MBF。采用全局比特位向量提供数据元素的快速插入和查找,结合动态分配的局部计数器向量存储不同时间段下的历史数据,使MBF支持不同时间粒度上历史数据的有效存储和高效查询,给出历史时间跨度较大情况下MBF的压缩方法以及MBF模型的参数最优化设置。理论分析证明,MBF具有较大的灵活性,能有效支持时间范围内历史数据元素的近似聚集查询。     

截取过滤器模式实现策略综述

截取过滤器是构建客户端请求处理管道的设计模式．而客户端请求处理管道是Web程序运行的基石。对截取过滤器实现策略进行探讨．论述和分析这些实现策略的实现方案以及各自的优缺点。     

一种面向深度数据包检测的索引拆分Bloom过滤器

高速数据包处理迫切需要时空高效的深度数据包检测(DPI),满足其线速处理和低存储空间需求.Trie位图内容分析器(TriBiCa)采用片上位图Trie树来实现元素的最小完美Hash;但是,TriBiCa存在更新开销高和假阳性访问次数多等问题.共享节点快速Hash表(SFHT)采用片上计数Bloom过滤器(CBF)来实现硬件Hash表的快速查找;但是,SFHT存在更新开销高和存储空间需求大等问题.文中提出了一种索引拆分Bloom过滤器(ISBF).ISBF是由片上多组并行CBF和片外元素集构成,其核心思想是:元素的片外索引值被拆分成多组比特,每组比特采用多个片上并行CBF表示元素集;当查询元素时,每组并行CBF产生多个比特值,并合成候选元素的片外索引值.为了降低ISBF的更新开销,文中又提出了懒惰删除(lazyd eletion)算法和空缺插入(vacant insertion)算法,即采用一个片上删除位图,仅在片上并行CBF中删除或插入元素,而不需要调整其他元素的片外索引值.ISBF是一种时空高效的数据结构,其插入、删除和查询操作的平均片外存储器访问次数均为O(1);与TriBiCa和SFHT相比,ISBF在...     

加密数据库快速关键词查询技术

为保证敏感信息的数据安全,用户通常会将其加密后存储到云端数据库,这为数据库管理及后续使用增加了难度。提出一种安全查询方案,在不暴露敏感信息的情况下可获得符合查询条件的结果集。使用伪随机函数和Bloom过滤器,对敏感信息的关键词集合进行预处理,在数据库中生成相应的索引数据结构,支持不固定数量的关键词查询与高效的数据更新。查询时,客户端计算出关键词相应的陷门并将其发送给服务器,服务器使用陷门执行查询,将多关键词计算出的陷门进行串接,可将多关键词查询问题转换成单关键词查询问题,并且不提高时间复杂度。此外,有效的陷门只能由拥有密钥的用户产生,陷门不会泄露任何敏感信息,故该方案不依赖完全可信的数据库服务提供商。与现有的采用特殊双层结构的加密方式相比,提高了查询效率,解决了加密数据库处理用户查询请求时的敏感信息泄露问题,且允许用户对敏感信息采用不同的加密方式,具有很强的兼容性。使用TPC-H的数据库测试方案和测试数据进行实验,实验结果证明了算法具有较高的执行效率。     

基于平衡二叉树和Bloom过滤器的可变长地址路由查找算法

可变长地址是未来网络领域的重要研究内容之一。针对传统路由查找算法在面向可变长地址时查找效率低的问题,提出一种基于平衡二叉树AVL(Adelson-Velskii and Landis)树和Bloom过滤器的适用于可变长地址的高效路由查找算法,简称为AVL-Bloom算法。首先,针对可变长地址灵活可变且无界的特点,利用多个片外哈希表分别存储前缀比特位数相同的路由条目及其下一跳信息,同时应用片上Bloom过滤器加速搜索可能匹配的路由前缀;其次,为了解决基于哈希技术的路由查找算法在查找最长前缀路由时需多次哈希对比的问题,引入AVL树技术,即通过AVL树组织每组路由前缀集合的Bloom过滤器及其哈希表,优化路由前缀长度的查询顺序,并减少哈希计算次数进而降低查询时间;最后,在3种不同的可变长地址数据集上将所提算法与METrie(Multi-Entrance-Trie)和COBF(Controlled prefix and One-hashing Bloom Filter)这两种传统路由查找算法进行对比实验。实验结果表明,AVL-Bloom算法的查询时间明显少于METrie和COBF算法,分别减少...     

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

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