融合Informer和深度哈希的时序数据相似性搜索研究

针对工业大数据相似性搜索的效率和准确率不高的问题,提出了一种融合Informer和深度哈希算法的时序数据相似性搜索方法。首先,基于Informer搭建深度哈希数据特征提取模型;然后,通过贪婪哈希函数和层归一化构建深度哈希函数,通过对损失函数进行优化提高深度哈希算法的性能;最后,对M树(M-tree)进行改进,提高时序数据相似性搜索的效率。基于不同数据集的实验结果表明,该方法在保证较高准确性的前提下,可以有效提高时序数据相似性搜索的速度。     

二进制特征与联合层叠结构的人脸识别研究

针对人脸识别阶段计算时间长的问题,提出一种基于二进制特征与联合层叠结构的人脸识别方法。在卷积神经网络中构建哈希层,将哈希层得到的编码作为分类器输入,同时加入Softmax分类损失函数和哈希损失函数作为优化目标之一;在学习特征表示的同时,学习它对应的哈希函数,使得提取到的特征从浮点型转换为二进制的特征,并使哈希函数满足独立性和量化误差最小的约束;针对哈希算法精度轻微下降的问题,通过联合级联结构将深度特征变换与深度二进制人脸哈希相结合,通过多种特征与多种度量的多次选择,最终匹配出最佳的目标作为结果。经实验验证,该算法在保证识别率的情况下,能缩短计算时间。     

IDS日志数据挖掘的改进算法

提出了一个基于最小完美哈希函数的关联规则的挖掘算法。基于Apriori的算法,在综合了传统哈希剪枝技术的同时,利用最小完美哈希函数的优点,保证了静态数据库关联规则挖掘,可以对关联规则的哈希结构数据进行动态的调整。该算法提高了挖掘效率,通过抑制哈希地址冲突提高了算法的稳定性和可用性。     

基于关联规则的二维哈希算法的改进

对关联规则发现中应用较多的Apriori算法进行了介绍和分析。在对Apriori算法改进的二维哈希算法中引入了新的哈希函数。这种哈希函数有效地避免了哈希“冲突”,有利于迅速产生二阶频繁项集,从而大幅度地提高了频繁项集产生的效率。     

一种基于子串识别的多模式串匹配算法

多模式串匹配算法是网络内容过滤系统的核心技术。巨大的存储空间开销是制约多模式匹配串算法应用的瓶颈之一。提出一种基于子串识别的多模式匹配算法—HashBOM,该算法利用位哈希表存储模式串的子串信息以大幅度减少存储空间,利用递归哈希函数计算字符串的哈希值以实现快速匹配。理论分析表明,该算法的空间复杂度为O(rm~2),优于基于子串识别的匹配算法BOM的空间复杂度O(mr|∑|log_2mr);该算法搜索匹配过程的平均时间复杂度为O(nlog|∑|)mr/m,与BOM算法相同(其中m为最短模式串的长度,r为模式串的个数,n为待匹配文本的长度,|∑|为字母表的大小)。在随机数据集和真实数据集上的实验表明,该算法的存储空间远远低于BOM算法,而匹配速度与BOM算法相当,非常适合在线实时匹配的应用环境。     

基于元学习的深度哈希检索算法

随着移动互联网技术的发展,图像数据的规模越来越大,大规模图像检索任务已经成为了一个紧要的问题。由于检索速度快和存储消耗低,哈希算法受到了研究者的广泛关注。基于深度学习的哈希算法要达到较好的检索性能,需要一定数量的高质量训练数据来训练模型。然而现存的哈希方法通常忽视了数据集存在数据类别非平衡的问题,而这可能会降低检索性能。针对上述问题,提出了一种基于元学习网络的深度哈希检索算法。所提算法可以直接从数据中自动学习加权函数。该加权函数是只有一个隐含层的多层感知机（MLP）,在少量无偏差元数据的指导下,加权函数的参数可以和模型训练过程中的参数同时进行优化更新。元学习网络参数的更新方程可以解释为：较符合元学习数据的样本权重将被提高,而不符合元学习数据的样本权重将被减小。基于元学习网络的深度哈希检索算法可以有效减少非平衡数据对图像检索的影响,并可以提高模型的鲁棒性。在CIFAR-10等广泛使用的基准数据集上进行的大量实验表明,在非平衡比率较大时,所提算法的平均准确率均值（mAP）最佳;在非平均比率为200的条件下,所提算法的mAP比中心相似度量化算法、非对称深度监督哈希（ADSH）算法和快速可扩展监督哈希（FSSH）算法分别提高0.54个百分点,30.93个百分点和48.43个百分点。     

基于数据摘要奇偶性的集合相似性近似算法

在应用b位哈希函数近似计算两个集合的Jaccard相似性时,如果有多个元素与输入元素的Jaccard相似性都很高(接近于1),那么b位哈希函数不能对这些元素进行很好的区分。为了提高数据摘要函数的准确性并提高基于相似性的应用的性能,提出了一种基于数据摘要奇偶性的集合相似性近似算法。在应用minwise哈希函数得到两个变异集合后,用两个n位指示向量来表示变异集合中的元素在指示向量中出现的奇偶性,并基于这两个奇偶性向量来估计原集合间的Jaccard相似性。通过马尔科夫链和泊松分布两种模型对奇偶性数据摘要进行了推导,并证明了这两种方法的等价性。Enron数据集上的实验表明,提出的奇偶性数据摘要算法与传统的b位哈希函数相比具有更高的准确性,并且在重复文档检测和关联规则挖掘两种应用中具有更高的性能。     

语义保持哈希在跨模态检索中的应用

哈希表示能够节省存储空间,加快检索速度,所以基于哈希表示的跨模态检索已经引起广泛关注。多数有监督的跨模态哈希方法以一种回归或图约束的方式使哈希编码具有语义鉴别性,然而这种方式忽略了哈希函数的语义鉴别性,从而导致新样本不能获得语义保持的哈希编码,限制了检索准确率的提升。为了同时学习具有语义保持的哈希编码和哈希函数,提出一种语义保持哈希方法用于跨模态检索。通过引入两个不同模态的哈希函数,将不同模态空间的样本映射到共同的汉明空间。为使哈希编码和哈希函数均具有较好的语义鉴别性,引入了语义结构图,并结合局部结构保持的思想,将哈希编码和哈希函数的学习融合到同一个框架,使两者同时优化。三个多模态数据集上的大量实验证明了该方法在跨模态检索任务的有效性和优越性。     

动态测量系统的有界影响滤波

如何克服Kalman滤波对采样观测值中包含的异常数据的敏感性?这在状态估计的抗扰性分析中处重要位置。本文基于新息增量过程,引进了一个相当大的滤波族,称为W滤波族。为了控制异常数据对滤波估计的影响,本文主要关心它的一个有界影响子族,并给出在预定的影响界限制下的最优有界影响滤波的φ函数形式。     

稀疏差分网络和多监督哈希用于高效图像检索

针对基于深度哈希的图像检索中卷积神经网络（CNN）特征提取效率较低和特征相关性利用不充分的问题,提出一种融合稀疏差分网络和多监督哈希的新方法SDNMSH（sparse difference networks and multi-supervised hashing）,并将其用于高效图像检索。SDNMSH以成对的图像作为训练输入,通过精心设计的稀疏差分卷积神经网络和一个监督哈希函数来指导哈希码学习。稀疏差分卷积神经网络由稀疏差分卷积层和普通卷积层组成。稀疏差分卷积层能够快速提取丰富的特征信息,从而实现整个网络的高效特征提取。同时,为了更加充分地利用语义信息和特征的成对相关性,以促进网络提取的特征信息能够更加有效地转换为具有区分性的哈希码、进而实现SDNMSH的高效图像检索,采用一种多监督哈希（MSH）函数,并为此设计了一个目标函数。在MNIST、CIFAR-10和NUS-WIDE三个广泛使用的数据集上进行了大量的对比实验,实验结果表明,与其他先进的深度哈希方法相比,SDNMSH取得了较好的检索性能。     

跳跃滤波:一种面向大数据治理的动态数据摘要设计

随着信息技术的迅速发展,数据体量维持指数增长,数据价值挖掘困难,这为数据采集、清洗、存储、共享等数据生命周期中各环节的高效管控带来极大的挑战.数据摘要技术利用哈希表/矩阵/位向量对数据的频数、基数、成员关系等核心基础特性进行追踪,使得数据摘要自身成为元数据,并在共享、传输、更新等场景得到广泛应用.大数据的快速流转特性更是催生了动态数据摘要技术.现有的动态数据摘要技术通过动态维护链状或树状结构的概率数据结构列表,具有其容量随数据流大小而扩增或缩减的优势,然而也存在空间开销过大以及时间开销随数据基数增加而增长的缺陷.基于先进的跳跃一致性哈希理论,设计了一种面向大数据治理的动态数据摘要技术.该方法可以同时实现随数据基数线性增长的空间开销以及数据处理分析常数级别的时间开销,能够有效地支撑要求苛刻的多种大数据处理分析任务.在多种合成和真实数据集上,通过与传统方法实验对比,验证了所提方法的有效性和高效性.     

Adaptive Spatial Partitioning for Multidimensional Data Streams

We propose a space-efficient scheme for summarizing multidimensional data streams. Our sketch can be used to solve spatial versions of several classical data stream queries efficiently. For instance, we can track ε-hot spots, which are congruent boxes containing at least an ε fraction of the stream, and maintain hierarchical heavy hitters in d dimensions. Our sketch can also be viewed as a multidimensional generalization of the ε-approximate quantile summary. The space complexity of our scheme is O((1/ε) log R) if the points lie in the domain [0, R]^d, where d is assumed to be a constant. The scheme extends to the sliding window model with a log (ε n) factor increase in space, where n is the size of the sliding window. Our sketch can also be used to answer ε-approximate rectangular range queries over a stream of d-dimensional points.     

支持高并发数据流处理的MapReduce中间结果缓存

针对面向大规模历史数据的高并发数据流处理需求,为改进MapReduce的实时处理能力,提出了一种内存Hash B树、外存SSTable文件的keyvalue中间结果缓存,该结构具有可划分性、可扩展性和高效性.在此基础上,利用B树的平衡性特征提出了一种基于概率的B树构造算法和多路查询算法,利用读写开销估算和缓冲区信息改造了外存文件读写策略和内外存替换算法,进一步优化了中间结果的高并发读写性能.算法分析和实验证明了该缓存的有效性.     

云存储服务的动态数据完整性审计方案

云存储服务的数据完整性检查受到了学术界和工业界的广泛关注.然而动态数据审计方案容易受到恶意云服务器的重放攻击,且存在不能很好地支持用户多粒度的动态操作等问题.为此基于Merkle Hash树(Merkle Hash tree, MHT)和双线性对技术,提出一个分层次索引结构的动态数据完整性审计方案.通过分层次索引结构的方法将数据块分割为长度更小的数据块,同时使MHT的每个叶结点对应多个数据块,从而有效降低了MHT的高度.提出的方案不但能满足云存储服务的数据完整性审计方案的安全要求,而且支持用户多粒度的动态操作.此外,在该方案中用户执行动态操作和审计者执行审计操作的通信开销将被大大降低.安全分析和性能分析,表明该方案是安全和高效的.     

一种面向海量存储系统的高效元数据集群管理方案

高效的、去中心化的元数据管理方案对大型分布式存储系统的可靠性、可扩展性起至关重要的作用.针对基于Hash划分和基于子树划分的元数据管理方案扩展代价巨大、对集群变动敏感等问题,提出一种基于一致性Hash结构的元数据服务器(metadata server, MDS)集群化方案——CH-MMS(consistent Hash based metadata management schema).CH-MMS在一致性MDS集群上引入虚拟MDS(Virtual MDS),有效平衡MDS集群负载;将Standby机制与延迟更新策略融合并应用于MDS集群,实现MDS快速失效恢复以及集群变动时零数据迁移量.阐述了CH-MMS的体系结构,介绍了核心数据结构layout-table、虚拟MDS结构、延迟更新机制及相关算法,并对CH-MMS扩展性、容错性作了定性分析.最后通过原型系统和模拟实验说明,CH-MMS具有元数据平衡分布、快速失效恢复、灵活的扩展性以及零结点变动数据迁移量等特点,能满足数据量不断增加的大规模存储集群元数据灵活、高效管理的需求.     

Jump Filter: A Dynamic Sketch for Big Data Governance

With the rapid development of information technology, the volume of data maintains exponential growth, and the value of data is hard to mine. This brings significant challenges to the efficient management and control of each link in the data life cycle, such as data collection, cleaning, storage, and sharing. Sketch uses a hash table/matrix/bit vector to track the core characteristics of data, such as frequency, cardinality, and membership. This mechanism makes the sketch itself metadata, which has been widely used in sharing, transmission, update, and other scenarios. The rapid flow characteristic of big data has spawned dynamic sketches. The existing dynamic sketches have the advantage of expanding or shrinking the capacity with the size of the data stream by dynamically maintaining a list of probabilistic data structures in a chain or tree structure. However, there are problems with the excessive space overhead and time overhead increasing with the increase in the dataset cardinality. This paper designs a dynamic sketch for big data governance on the basis of the advanced jump consistent hash. This method can simultaneously achieve the space overhead that grows linearly with the dataset cardinality and the constant time overhead of data processing and analysis, effectively supporting the demanding big data processing and analysis tasks for big data governance. The validity and efficiency of the proposed method are verified by the comparison with traditional methods on various synthetic and natural datasets.     

一种基于哈希链表的高效概念漂移连续属性处理算法

本文重点研究了数据流挖掘中存在概念漂移情形的连续属性处理算法。数据流是一种增量、在线、实时的数据模型。VFDT是数据流挖掘中数据呈稳态分布情形下最成功的算法之一;CVFDT是有效解决数据流挖掘中概念漂移问题的算法之一。基于CVFDT,本文提出了有效地解决数据流挖掘中存在概念漂移情形的连续属性处理问题的扩展哈希表算法HashCVFDT。该算法在属性值插入、查找和删除时具有哈希表的快速性,而在选取每个连续属性的最优化划分节点时解决了哈希表不能有序输出的缺点。     

基于分层计数型Bloom过滤器的进化数据流计数

许多应用场景所产生的数据流中,元素的频数分布符合重尾分布的特点,即大部分元素的频数较小而少部分元素的频数较大.为了解决数据流中所有相异元素及其频数的高效存储问题,提出了一个基于分层的计数型布卢姆过滤器(hierarchical counting Bloom filter,HCBF)保存所有元素频数的方法.该方法采用长度递减、计数单位递增的多层计数型布卢姆过滤器作为存储数据结构,多层过滤器共同组成元素的频数.与两个经典的计数型布卢姆过滤器CBF和DCF相比,HCBF更加适合真实数据流元素频数分布的重尾特点,在不影响查询性能和错误率的前提下,能够显著地降低空间开销.理论分析与实验结果验证了该结论.     

面向物联网的近地轨道超大规模卫星星座数据命名机制

基于信息中心网络（ICN）的近地轨道（LEO）超大规模卫星星座是一种支持物联网（IoT）非常理想的网络架构,而数据命名是ICN基本问题之一。针对IoT低时延传输、高吞吐量的数据分发的需要,提出了一种基于ICN的面向IoT的LEO超大规模卫星星座数据命名机制。首先,该数据命名机制采用一种融合分层、多分量、哈希的扁平一体结构。然后,采用前缀标记描述分层名称,满足网内功能中多源快速检索的需要。最后,为检验所提数据命名机制的性能,设计开发了一个基于网络仿真器3（NS-3）的面向IoT的LEO超大规模卫星星座仿真平台。测试仿真结果表明,与传统的基于互联网协议（IP）的体系结构相比,所提出的数据命名机制能够为面向IoT的LEO超大规模卫星星座提供高吞吐量和低延时等更高的服务质量（QoS）。     

一种基于区域划分的数据流子空间聚类方法

数据流子空间聚类的主要目的是在合理的时间段内准确找到数据流特征子空间中的聚类.现有的数据流子空间聚类算法受参数影响较大,通常要求预先给出聚类数目或特征子空间,且聚类结果不能及时反映数据流的变化情况.针对以上缺陷,提出一种新的数据流子空间聚类算法SC-RP,SC-RP无需预先给出聚类数目或特征子空间,对孤立点不敏感,可实现快速聚类,通过区域树结构记录数据流的变化并及时更新统计信息,进而根据数据流的变化调整聚类结果.通过在真实数据集与仿真数据集上的实验,证明了SC-RP在聚类精度和速度上优于现有的数据流子空间聚类算法,且对聚类数目及数据维度均具有良好的伸缩性.