多维数据布鲁姆过滤器的理论与技术

With data filtering technology, valuable data can be fast purified from static or dynamic big data for further processing. This technology is a very effective tool in the current era of data explosion. Although the data filters for single dimension data have been researched and used for many years, the research on filters for multi-dimensional data is being seldom studied, even the minor contribution is mainly from the judgment of belonging to a low-dimensional data set. Focusing on processing multi-dimensional data, we propose some new theories and implementation techniques for high-performance data filters. The study includes: (1) We propose Bloom filter based associative deletion theory and algorithms for low-dimensional data. This theory can also provide direct calculation method for many other operations, such as semi-join, update of sliding-window, etc. (2) We propose theories and algorithms of multi-granularity locality-sensitive Bloom filter for high-dimensional data. (3) We propose a new hardware coprocessor using pipeline acceleration for filtering in front-ends of data processing. (4) We propose batch processing and pipeline processing methods in the MapReduce framework for filtering acceleration in a back-end data processing server. The study is a project of originality and will contribute significance theories and techniquies for data processing.

数据过滤技术能够从静态或动态的海量数据中快速提纯出有价值的数据做进一步处理，它是当前数据爆炸时代非常有效的工具。尽管单维数据过滤器已经研究和应用多年，但针对多维数据过滤器的研究还不多，且主要集中在低维数据的集合判断问题。基于数据管理技术的前瞻性考虑，项目以多维数据为处理对象，探索高性能数据过滤器的理论和实现技术，为大数据处理领域提供先进、实用的解决方案。研究内容包括：(1)提出低维数据布鲁姆过滤器关联删除概念和方法，该方法也能用于半连接、窗口更新等其它操作；(2)针对高维数据的不同过滤粒度，提出多粒度距离敏感布鲁姆过滤器方案；(3)结合硬件和并行计算的高效性，设计实现可用于数据处理前端流水线加速的硬过滤器；(4)设计实现后端数据处理服务器的基于MapReduce的批处理和流水线加速方法。该项研究具有原创性，对提高数据处理速度，拓展数据管理技术的理论和方法有重要的理论和现实意义。

数据过滤技术能够从静态或动态的海量数据中快速提纯出有价值的数据做进一步处理，是当前数据爆炸时代非常有效的工具。基于数据管理技术的前瞻性考虑，项目以多维数据为处理对象，探索高性能数据过滤器的理论和实现技术，为大数据处理领域提供先进、实用的解决方案。研究内容包括：提出低维数据布鲁姆过滤器关联删除概念和方法，该方法也能用于半连接、窗口更新等其它操作；针对高维数据的不同过滤粒度，提出多粒度距离敏感布鲁姆过滤器方案；结合硬件和并行计算的高效性，设计实现可用于数据处理前端流水线加速的硬过滤器；设计实现后端数据处理服务器的基于MapReduce 的批处理和流水线加速方法。项目按计划执行，很好地完成了预定目标，部分成果如：（1）创造性地提出可对齐的局部性敏感哈希函数族，在此基础上，提出了新型多粒度距离敏感布鲁姆过滤器，可以处理多个不同距离的近似查询。提出控制假阳性和假阴性的理论和方法。论文得到审稿专家高度评价，还被包括《美国科学院院刊》(PNAS)等期刊和会议多次引用。（2）提出一种新的数据结构，能够分别保持两维数据单独的摘要信息，还能够保持两维数据之间的关联信息并执行一般数据和流数据的关联删除，并采用硬件协处理器来加速运算。（3）大数据时代的数据很多是用海明码表示的，而在海明空间不能采用前述多粒度距离敏感布鲁姆过滤器方案，因为无法构造虚拟的过滤器。我们创造性的将查询点虚拟化，扩大查询半径，分析相关参数和理论，实现海明空间的多粒度距离敏感布鲁姆过滤器。共发表高水平学术论文24篇，其中SCI检索7篇、EI检索14篇，申请人有3篇一作为CCF推荐的A类期刊，申请发明专利14项，其中授权发明专利4项，软件著作权2项。培养研究生24名、博士生2名，毕业研究生13名。该项研究具有原创性，可广泛应用于大数据粗粒度和细粒度处理，对提高数据处理速度，拓展数据管理技术的理论和方法有重要的理论和现实意义。