2017年6月12日 (一) 09:07的版本

本组研究

实验室研究。

研究定位

数据分析层面（（系统级、功能））：关联规则分析、对比集分析、协同过滤、图的可达性查询

算法实现层面（进程级）： Apriori 算法、相似度计算、对比集挖掘

数据结构层面（编程语言）：Bitmap/Bit_array/Bitset/... （C++、Go、Java 函数库）

硬件执行层面（处理器层面）：BMI/SSE/AVX/AVX2/FMA （通用机器指令 Instructions）

硬件执行层面（FPGA 层面）：专用机器指令、软硬件协同设计（HW/SW co-design））

本组工作

数据分析层面

协同过滤（Collaborative filtering）

数据结构层面

位图索引方法

• • CODIS （Compressing Dirty Snippet） （C++ ）

• • BAH（Byte Aligned Hybrid） （C++ Language）

• • CAMP（Common Affix Merging with Partition） （Java Language）

• • SPLWAH （SPLASH WAH）（CUDA Language）

• • COMBAT （COMbining Binary And Ternary encoding）（C++）

• • MASC（MAximized Stride with Carrier）（C++）

• 本组论文

1. Wenxun Zheng et al., CODIS: A New Compression Scheme for Bitmap Indexes, ANCS 2017.
2. Chenxing Li et al., BAH: A Bitmap Index Compression Algorithm for Fast Data Retrieval, LCN 2016.
3. Yinjun Wu et al., CAMP: A new bitmap index for data retrieval in traffic archival, Communication Letters, Vol. 20, No. 6, pp.1128 - 1131, June 2016.
4. Jiahui Chang et al., SPLWAH: A bitmap index compression scheme for searching in archival Internet traffic. ICC 2015.
5. Yinjun Wu et al., COMBAT: a new bitmap index coding algorithm for big data. TST 2016.

• 论文列表

http://net.icenter.tsinghua.edu.cn/netplus/paper.html

研究方向

研究点：使用位图索引支撑的算法。

MPSoC增强的索引运算

1. Sebastian Haas et al., An MPSoC for Energy-Efficient Database Query Processing, DAC 2016.
2. Sebastian Haas et al., HW/SW-Database-CoDesign for Compressed Bitmap Index Processing, ASAP 2016.

非循环图的可达性查询

1. Sebastiaan J. van Schaik et al., A Memory Efficient Reachability Data Structure Through Bit Vector Compression, SOGMOD 2011.

ISA增强的集运算

1. O. Arnold et al., An application-specific instruction set for accelerating set-oriented database primitives. SIGMOD 2014.

关联规则挖掘

关联规则挖掘（association rule mining），查找频繁项目集（Frequent ItemSets）。其中最有名的算法是Apriori算法。

基于位图的Apriori算法加速。

1. Sung-Tan Kim et al., "BAR: bitmap-based association rule: an implementation and its optimizations." ACM MoMM 2009.

对比度设置学习

对比度设置学习（对比集分析）是一种关联规则的学习 ，旨在找出有意义的不同的群体之间的差异，通过逆向工程的关键预测指标，确定每一个特定的组。

基于位图的对比集挖掘算法加速。

1. Gangyi Zhu et al., SciCSM: Novel Contrast Set Mining over Scientific Datasets Using Bitmap Indices, SSDBM 2015.

数据采样

数据采样（Data Sampling）。

基于位图索引的数据采样方法。

1. Su, Yu, et al. "Taming massive distributed datasets: data sampling using bitmap indices." HPDC 2013.

相关性挖掘

• 相关性测度（Correlation Metrics ）
  • 地球移动距离（Earth Mover's Distance, EMD）
  • 香农熵（Shannon's Entropy）、互信息（Mutual Information）、条件熵（Conditional Entropy）

相关性分析位图索引加速。

1. Yu Su et al., In-Situ Bitmaps Generation and Efficient Data Analysis based on Bitmaps, HPDC 2015.

子群发现

子群发现（subgroup mining）是数据分析的一个重要方法。

基于位图索引的子群发现方法加速。

1. Yi Wang et al., SciSD: Novel Subgroup Discovery Over Scientific Datasets Using Bitmap Indices, #OSU-CISRC-3/15-TR03, March 2015.

相似性查询

相似性查询 （Similarity searches）是探索式数据分析（exploratory data analysis）的一个重要任务。距离度量（Distance metrics）方法是相似性查询的基础。

基于BSI(Bit Slice Index)位图索引方法加速K-近邻（kNN）方法。

1. Gheorghi Guzun et al., "Supporting Dynamic Quantization for High-Dimensional Data Analytics." ExploreDB 2017.

有限状态机运行并行加速

使用Intel Xeon Phi加速卡。

1. Peng Jiang et al., Combining SIMD and Many Multi-core Parallelism for Finite State Machines with Enumerative Speculation, PPoPP 2017.

研究应用

数码视讯、中国联通、百度公司、华为技术

教材

1. Leskovec, Jure, Anand Rajaraman, and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2014. MMDS_book