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

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

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

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

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

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

一种改进的Philips音频指纹检索算法

在Philips音频指纹检索算法中,构造一个查询表作为索引,由于内存消耗过大限制其广泛应用。为此,基于Philips音频指纹检索原型,提出一种改进算法。结合斐波那契数列和右移运算,构造新的哈希函数,通过斐波那契优化哈希值分布,并执行右移运算调整哈希表的长度。实验结果表明,改进算法能减少内存消耗,提高系统的实用性。     

基于HCBF的大流检测机制*

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

基于单哈希多维布隆过滤器的DDS自动发现算法

SDPBloom算法减小了基于简单发现协议的自动发现算法SDP_ADA的网络数据传输量和内存消耗,但在自动发现过程中存在哈希运算量大的问题,导致参与者端点之间发布/订阅消息的时间过长.为解决这一问题,在简单发现协议的基础上,提出一种基于单哈希多维布隆过滤器的自动发现算法SDP_OMBF.该算法将单哈希多维布隆过滤器向量(OMBF)用于参与者端点信息的匹配.实验结果表明,该算法提高了数据分发服务(Data Distribution Service,DDS)自动发现过程中的实时性.     

基于改进LSH的协同过滤推荐算法

协同过滤是个性化推荐系统中应用较为成功与广泛的技术之一,影响协同过滤推荐质量的关键在于获取目标用户的k近邻用户,然后基于k近邻对其未评价的项目进行评分预测与推荐。针对用户评分数据的规模大、维度高、高度稀疏以及直接进行相似性度量的实时性差等对推荐性能的影响,提出一种基于LSH的协同过滤推荐算法,并对其进行改进。该算法基于p稳态分布的局部敏感哈希对用户评分数据进行降维与索引,并采用多探寻的机制对其进行改进,缓解多个哈希表对内存的压力,快速获取目标用户的近邻用户集合,然后采用加权方法来预测用户评分并产生推荐。标准数据集上的实验结果表明,该方法能有效克服评分数据的高维稀疏,并在保证一定推荐精度的前提下,大幅度提高推荐效率和降低内存消耗。     

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

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

基于CBF的分布式元组空间叉积算法

针对分布式报文分类算法内存消耗大、可扩展性差的问题,提出分布式元组空间叉积算法。该算法采用独立域搜索引擎与树状多级聚合网络的分类结构,在聚合节点使用计数型布鲁姆过滤器(CBF)加速搜索,利用剪枝技术降低CBF内存消耗。仿真结果表明,对于 5×104条规模的9域规则库,聚合网络总内存消耗被控制在60 Kb内,该算法的查找速度达到100 Mp/s,且具有良好的可扩展性。     

基于CBF的分布式元组空间叉积算法

针对分布式报文分类算法内存消耗大、可扩展性差的问题,提出分布式元组空间叉积算法。该算法采用独立域搜索引擎与树状多级聚合网络的分类结构,在聚合节点使用计数型布鲁姆过滤器(CBF)加速搜索,利用剪枝技术降低CBF内存消耗。仿真结果表明,对于 5×104条规模的9域规则库,聚合网络总内存消耗被控制在60 Kb内,该算法的查找速度达到100 Mp/s,且具有良好的可扩展性。     

Bloom Filter及其应用综述

Bloom Filter对数据集合采用一个位串表示并能有效支持集合元素的哈希查找操作。本文对Bloom Filter及其改进型进行了综述性分析研究．探讨了它的实用性。较为详细地阐述了它在P2P网络文件存储系统OceanStore和文本检索系统中的应用情况。最后指出了进一步的研究方向。     

基于Counting Bloom Filter的DNS异常检测

鉴于失败的DNS查询（failed DNS query）能提供恶意网络活动的证据,以DNS查询失败的数据为切入口,提出一种轻量级的基于Counting Bloom Filter的DNS异常检测方法。该方法使用带语义特征的可逆哈希函数对被查询的域名及发起查询的IP进行快速的聚类和还原。实验结果证明该方法能以较少的空间占用和较快的计算速度有效识别出DNS流量中的异常,适用于僵尸网络、分布式拒绝服务（DDoS）攻击等异常检测的前期筛选和后期验证。     

基于计数布隆过滤器的负载均衡算法

由于哈希冲突的存在,基于哈希表的网络流负载均衡算法无法约束最坏情况下算法的性能。针对该问题,设计一种多哈希算法,将需要调整的流保存在精确流匹配布隆过滤器结构中。与基本哈希表相比,该算法保持了会话的完整性以及更低的冲突概率,提高了查询性能。     

一种新型精确深度包检测引擎研究与设计

传统的深度包检测算法通常存在频率带宽瓶颈、不能精确匹配、不切实际的存储要求等其中之一或数个缺点.本文基于哈希与Bloom Filter提出一种新型精确匹配结构:Bloom Filter分类器,首先基于哈希对特征串分组,再用多组Bloom Filter对输入串分类,在每长度定位到唯一可能的匹配串并对比验证.对Snort、ClamAV集合进行了存储实验评估,以约1.22(字节/字符)的低存储代价实现对万条字符串集的精确匹配.该结构具有精确匹配、多字节匹配扩展简单、不存在带宽瓶颈等优点.     

基于多级CBF的长流识别

针对高速网络流量难测量的问题及长流占网络流量大部分的特点,提出一种基于多级CBF的长流识别算法,对报文进行抽样,将抽取的报文通过经过一系列哈希映射到长流信息表中,查找是否存在该流信息,若存在则更新流信息,若不存在则将该报文用多级CBF结构对流信息进行过滤,报文数达到阈值的流被识别为长流,并在长流信息表中创建和维护该长流的信息.该算法在很大程度上减少了短流因为哈希冲突而被误判为长流的概率,降低了资源开销,对指定报文数为阈值的长流识别具有很好的扩展性.     

Fast schemes for online record linkage

The process of integrating large volumes of data coming from disparate data sources, in order to detect records that refer to the same entities, has always been an important problem in both academia and industry. This problem becomes significantly more challenging when the integration involves a huge amount of records and needs to be conducted in a real-time fashion to address the requirements of critical applications. In this paper, we propose two novel schemes for online record linkage, which achieve very fast response times and high levels of recall and precision. Our proposed schemes embed the records into a Bloom filter space and employ the Hamming Locality-Sensitive Hashing technique for blocking. Each Bloom filter is hashed to a number of hash tables in order to amplify the probability of formulating similar Bloom filter pairs. The main theoretical premise behind our first scheme relies on the number of times a Bloom filter pair is formulated in the hash tables of the blocking mechanism. We prove that this number strongly depends on the distance of that Bloom filter pair. This correlation allows us to estimate in real-time the Hamming distances of Bloom filter pairs without performing the comparisons. The second scheme is progressive and achieves high recall, upfront during the linkage process, by continuously adjusting the sequence in which the hash tables are scanned, and also guarantees, with high probability, the identification of each similar Bloom filter pair. Our experimental evaluation, using four real-world data sets, shows that the proposed schemes outperform four state-of-the-art methods by achieving higher recall and precision, while being very efficient.     

基于Bloom Filter的网页去重算法

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

Using Parallel Bloom Filters for Multiattribute Representation on Network Services

One widely used mechanism for representing membership of a set of items is the simple space-efficient randomized data structure known as Bloom filters. Yet, Bloom filters are not entirely suitable for many new network applications that support network services like the representation and querying of items that have multiple attributes as opposed to a single attribute. In this paper, we present an approach to the accurate and efficient representation and querying of multiattribute items using Bloom filters. The approach proposes three variant structures of Bloom filters: Parallel Bloom Filter (referred as PBF) structure, PBF with a hash table (PBF-HT), and PBF with a Bloom filter (PBF-BF). PBF stores multiple attributes of an item in parallel Bloom filters. The auxiliary HT and BF provide functions to capture the inherent dependency of all attributes of an item. Compared to standard Bloom filters to represent items with multiple attributes, the proposed PBF facilitates much faster query service and both PBF-HT and PBF-BF structures achieve much lower false positive probability with a result to save storage space. Simulation and experimental results demonstrate that the new space-efficient Bloom filter structures can efficiently and accurately represent multiattribute items and quickly respond queries at the cost of a relatively small false positive probability.     

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

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