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

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

基于点对相似度的深度非松弛哈希算法

哈希学习能够在保持数据之间语义相似性的同时, 将高维数据投影到低维的二值空间中以降低数据维度实现快速检索. 传统的监督型哈希学习算法主要是将手工设计特征作为模型输入, 通过分类和量化生成哈希码. 手工设计特征缺乏自适应性且独立于量化过程使得检索的准确率不高. 本文提出了一种基于点对相似度的深度非松弛哈希算法, 在卷积神经网络的输出端使用可导的软阈值函数代替常用的符号函数使准哈希码非线性接近-1或1, 将网络输出的结果直接用于计算训练误差, 在损失函数中使用$\ell_1$范数约束准哈希码的各个哈希位接近二值编码. 模型训练完成之后, 在网络模型外部使用符号函数, 通过符号函数量化生成低维的二值哈希码, 在低维的二值空间中进行数据的存储与检索. 在公开数据集上的实验表明, 本文的算法能够有效地提取图像特征并准确地生成二值哈希码, 且在准确率上优于其他算法.     

基于平衡二叉树和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算法，分别减少...     

基于卡方分布的高维数据相似性连接查询算法

为了解决高维数据相似性连接查询中存在的维度灾难和计算代价高等问题,基于p-稳态分布,将高维数据映射到低维空间。根据卡方分布的性质,证明了如果低维空间的距离大于kε,则原始空间距离大于ε的概率具有一定的下界,从而可以在低维空间以较低的计算代价进行有效过滤。在此基础上,提出了基于卡方分布的高维数据相似性连接查询算法。为了进一步提高查询效率,提出了基于双重过滤的高维数据相似性连接查询算法。利用真实数据集进行了实验,实验结果表明所提方法具有较好的性能。基于卡方分布的相似性连接查询算法召回率可以达到90%以上。基于双重过滤的相似性连接查询算法可以进一步提高性能,但是会损失一定的召回率。对时间性能要求比较高、对召回率要求不太严格的查询任务可以采用基于双重过滤的相似性连接查询算法;反之,可以采用基于卡方分布的相似性连接查询算法。     

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

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

海量高维向量的并行Top-k连接查询

在很多应用领域中,向量的Top-k连接查询是一种很重要的操作,给定两个向量集合R和S,Top-k连接查询要求从R和S中返回距离最小的前k个向量对.由于数据的海量性和高维特性,传统的集中式算法已经无法在可接受的时间内完成连接查询任务.MapReduce作为一个并行处理框架,能够有效地处理大规模数据.由于其高可扩展性、高可用性等特点,MapReduce已经成为海量数据处理的首选实现方案,在很多领域都得到了广泛的应用.文中基于分段累积近似法对高维向量进行降维,然后利用符号累积近似法对高维向量进行分组;在此基础上,结合MapReduce框架,提出了基于SAX的并行Top-k连接查询算法.实验表明,文中所提方案具有良好的性能和扩展性.     

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

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

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

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

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

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

基于布鲁姆过滤器的计算机动态取证技术研究

静态取证时效性不足,动态取证则可获得更为真实、实时的证据。动态取证最关键的是证据识别。证据识别本质上是对网络数据流进行分类,以判断其行为是合法还是非法。布鲁姆过滤器采用一个位串表示数据集合并有效支持元素的哈希查询,从而被广泛应用于包分类算法中。首先对标准布鲁姆过滤器算法进行分析,并对算法存在的缺陷进行改进。在此基础上,设计一个基于布鲁姆过滤器的分布式计算机动态取证系统,并采取安全有效措施对证据进行传送。实验表明:该系统能对网络攻击行为进行动态地检测,且检测准确率高、误判率低。