基于哈希的流式大数据筛选关键技术研究

How to capture the useful information from streaming big data is a pressing problem faced by people in the current era of big data. Due to the huge amount of data in the streaming big data, this project proposes a two levels Filter-and-Refine Framework that is used to sift streaming big data. The study includes: (1) We design variable distance Bloom filters, including the variable Euclidean distance Bloom filter and the variable Hamming distance Bloom filter. This type of filter can adapt to a variety of sifting rules proposed by users, and achieve fast rough filtering of large data set. (2) We design a distributed hashing technology to match the filtered data and rules. (3) For complex type streaming data, such as sequence data, and heterogeneous data, we design the hashing method which can map data to the unified feature space, and then the complex type data can be sifted in that space. (4) We propose a novel sketch, EFM sketch. EFM sketch can be used to estimate the cardinality of a set, the similarity of two sets, etc. (5) We propose an optimization method for sifting rules and design the method of generating the optimized execution plan. The study is a project of originality and will contribute significance theories and techniques for streaming big data processing.

如何从持续不断产生的流式大数据中及时捕捉到对己有用的信息是大数据时代人们所面临的一个迫切问题。本项目针对流式到来的数据量巨大，而其中大部分又非用户所需数据的特点，采用两层过滤-验证框架来实现流式大数据筛选。研究内容包括：(1)提出可变距离布鲁姆过滤器，适应不同用户的多种筛选规则，实现对大数据的快速过滤，去掉大部分不需要数据；(2)设计分布式哈希技术，实现过滤后的数据和筛选规则的匹配；(3)针对流式大数据中复杂类型数据，如序列型数据、异构型数据，设计将其映射到统一特征空间的哈希方法，实现复杂类型流式大数据的筛选；(4)构造能估算多种集合统计量的哈希结构，将流式大数据的概要压缩到该结构中，实现基于集合统计量的筛选；(5)对提交到系统的筛选规则集合，提出优化方法并生成优化后的筛选执行计划，以实现筛选系统整体上高效。本项目的研究成果对从大数据中及时获取有用信息具有重要的理论意义和实际应用价值。

如何从持续不断产生的流式大数据中及时捕捉到对己有用的信息是大数据时代人们所面临的一个迫切问题。本项目针对流式到来的数据量巨大，而其中大部分又非用户所需数据的特点，采用两层过滤-验证框架来实现流式大数据筛选。. 主要研究工作包括： .（1）设计可变欧氏距离和可变海明距离布鲁姆过滤器，实现对大数据的快速过滤。. 本项目提出一种可变欧氏距离的布鲁姆过滤器，可在过滤中根据不同的情况选择不同的过滤距离，更好地适应流式大数据的实时变化特性。对海明距离相似度，本项目研究提出可变海明距离的布鲁姆过滤器和相应的LSH函数，能够有效地支持海明距离下的近似过滤问题和多粒度的近似数据过滤问题。.（2）提出基于分布式哈希技术的筛选规则匹配算法。. 本项目采用基于LSH的近似搜索的思想，通过“过滤-验证”方式，先过滤掉大部分规则库中的规则，再进行实际的匹配比较，为此针对不同场景本项目提出了多种改进的基于LSH的近似搜索策略，如C2LSH、M2LSH、SLSB-forest等。.（3）设计序列型、集合型、图等复杂类型大数据的处理方法。. 为在持续流式到来的序列型数据中，及时筛选用户关心的序列模式，本项目提出了一种垂直化频繁生成序列算法。针对集合型数据，本项目提出了Min/Max包含度作为相似度度量方法并提出了相应的处理方法。图数据是一类有广泛应用的大数据，本项目针对图和图流提出了多种处理方法。.（4）设计基于集合统计量的流数据筛选方法。. 在实际应用中，经常需要从流式大数据中“筛选”出一个较小的且具有代表性的数据子集。筛选通常使用数据子集的某种统计量（效用函数）来评价所选子集的“代表性”是否达到目的。本项目提出基于次模最大化的分层流筛选和摘要算法解决流数据的筛选和摘要问题。.（5）基于机器学习优化的哈希模型。. 应用深度学习等机器学习方法从数据的分布中学习优化的哈希模型，即所谓学习型哈希方法，来更有效地处理各种复杂结构的大数据，本项目设计了多种采用不同机器学习方法的学习型哈希模型。