（以“=本组研究 = 实验室研究。 ==*研究定位== 数据分析层面：关联规则分析（功能）（对比集分析Contrast Set Mining）（协同过滤 Col...”为内容创建页面） |
|||
| （相同用户的41个中间修订版本未显示） | |||
| 第2行： | 第2行： | ||
实验室研究。 | 实验室研究。 | ||
| − | == | + | ==背景== |
| + | 云计算（Cloud Computing）对产业影响巨大，云平台提供商为了获得最大化的经济收益，对计算资源的优化使用具有很强的经济动能，将计算资源的效率发挥到了极致。 | ||
| − | + | 云平台提供商对软硬件计算资源的一体化掌控，对软件的性能、能效等专用目标的最优化。 | |
| − | + | *趋势1：软硬件协同设计，对一些负载（work load）进行加速器（accelerator）的设计，达到性能、能效等专用目标的最优化。 | |
| − | + | *趋势2：软件一体化设计，达到性能度量指标的最优能力。 | |
| − | + | ==研究定位== | |
| + | 数据分析层面（系统级、功能）：关联规则分析、对比集分析、协同过滤、图的可达性查询 | ||
| − | + | 算法实现层面（进程级）： A-Priori 算法、相似度计算、对比集挖掘 | |
| + | 数据结构层面（编程语言）：Bitmap/Bit_array/Bitset/... （C++、Go、Java 函数库） | ||
| + | |||
| + | 硬件执行层面（处理器层面）：BMI/SSE/AVX/AVX2/FMA （通用机器指令 Instructions） | ||
| + | |||
| + | 硬件执行层面（FPGA 层面）：专用机器指令、软硬件协同设计（HW/SW co-design） | ||
| + | |||
| + | ==本组工作== | ||
| + | |||
| + | ===数据分析层面=== | ||
| + | 协同过滤（Collaborative filtering） | ||
| + | |||
| + | ===数据结构层面=== | ||
| + | 2014年，本校学生温禹豪提出了SECOMPAX，进一步改进COMPAX算法。 | ||
| + | |||
| + | 2014年，本校学生常嘉辉提出了PLWAH+算法，改进了PLWAH算法。 | ||
| + | |||
| + | 2015年，本校学生常嘉辉提出了SPLWAH 算法。 | ||
| + | |||
| + | 2015年，本校学生吴垠鋆提出了CAMP算法，进一步改进WT(Wavelet Trie)算法。 | ||
| + | |||
| + | 2015年，本校学生吴垠鋆和温禹豪提出了COMBAT算法，进一步改进了了SECOMPAX算法。 | ||
| + | |||
| + | 2016年，本校学生温禹豪和王晗提出了MASC算法，进一步改进BBC/WAH算法。 | ||
| + | |||
| + | 2016年，本校学生李辰星等，提出了BAH算法，进一步改进了BBC算法。 | ||
| + | |||
| + | 2017年，本校学生郑文勋提出了CODIS方法，进一步改进性能。 | ||
| + | |||
| + | |||
| + | 位图索引方法 | ||
**CODIS （Compressing Dirty Snippet） （C++ ） | **CODIS （Compressing Dirty Snippet） （C++ ） | ||
| 第21行： | 第53行： | ||
**[https://github.com/thuwuyinjun/CAMP CAMP]（Common Affix Merging with Partition） （Java Language） | **[https://github.com/thuwuyinjun/CAMP CAMP]（Common Affix Merging with Partition） （Java Language） | ||
| − | **SPLWAH （SPLASH | + | **SPLWAH （SPLASH WAH）（CUDA Language） |
**COMBAT （COMbining Binary And Ternary encoding）（C++） | **COMBAT （COMbining Binary And Ternary encoding）（C++） | ||
| 第36行： | 第68行： | ||
# Yinjun Wu et al., COMBAT: a new bitmap index coding algorithm for big data. TST 2016. | # 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 | |
| − | + | ==研究方向== | |
| − | + | 研究点：使用位图索引支撑的[[大数据算法]]。 | |
| − | + | ==底层 == | |
| − | + | 处理器与FPGA | |
| − | + | === MPSoC增强的索引运算=== | |
| − | + | #Sebastian Haas et al., An MPSoC for Energy-Efficient Database Query Processing, DAC 2016. | |
| + | #Sebastian Haas et al., HW/SW-Database-CoDesign for Compressed Bitmap Index Processing, ASAP 2016. | ||
| − | + | === ISA增强的集运算=== | |
| − | + | #O. Arnold et al., An application-specific instruction set for accelerating set-oriented database primitives. SIGMOD 2014. | |
| − | |||
| − | + | === 有限状态机运行并行加速=== | |
| − | + | 使用Intel Xeon Phi加速卡。 | |
| − | + | #Peng Jiang et al., Combining SIMD and Many Multi-core Parallelism for Finite State Machines with Enumerative Speculation, PPoPP 2017. | |
| − | ==== | + | |
| + | ==上层 == | ||
| + | |||
| + | === 非循环图的可达性查询=== | ||
| + | |||
| + | #Sebastiaan J. van Schaik et al., A Memory Efficient Reachability Data Structure Through Bit Vector Compression, SOGMOD 2011. | ||
| + | |||
| + | === 频繁项目集发现 === | ||
| + | |||
| + | 查找频繁项目集（Frequent ItemSets）。其中最有名的算法是A-Priori算法。 | ||
| + | |||
| + | 从数据集中抽取频繁集，抽取的结果往往采用if-then 形式的规则集合来表示，这些规则被称为关联规则（association rule）。频繁项目集发现常常被看成关联规则挖掘（association rule mining）或关联规则发现。 | ||
基于位图的Apriori算法加速。 | 基于位图的Apriori算法加速。 | ||
| 第72行： | 第114行： | ||
#Sung-Tan Kim et al., "BAR: bitmap-based association rule: an implementation and its optimizations." ACM MoMM 2009. | #Sung-Tan Kim et al., "BAR: bitmap-based association rule: an implementation and its optimizations." ACM MoMM 2009. | ||
| − | + | === 对比度设置学习=== | |
对比度设置学习（对比集分析）是一种关联规则的学习 ，旨在找出有意义的不同的群体之间的差异，通过逆向工程的关键预测指标，确定每一个特定的组。 | 对比度设置学习（对比集分析）是一种关联规则的学习 ，旨在找出有意义的不同的群体之间的差异，通过逆向工程的关键预测指标，确定每一个特定的组。 | ||
基于位图的对比集挖掘算法加速。 | 基于位图的对比集挖掘算法加速。 | ||
| + | |||
#Gangyi Zhu et al., SciCSM: Novel Contrast Set Mining over Scientific Datasets Using Bitmap Indices, SSDBM 2015. | #Gangyi Zhu et al., SciCSM: Novel Contrast Set Mining over Scientific Datasets Using Bitmap Indices, SSDBM 2015. | ||
| − | |||
| − | === | + | === 数据采样 === |
| − | + | 数据采样（Data Sampling）。 | |
| − | + | 2014年，俄亥俄州立大学的Yu Su等提出了位图索引取样技术处理大规模分布式数据集，这样能保留原始数据的特征，并且造成的损失亦处在可接受范围内。 | |
| − | + | 基于位图索引的数据采样方法。 | |
| − | + | # 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） | ||
相关性分析位图索引加速。 | 相关性分析位图索引加速。 | ||
| 第96行： | 第142行： | ||
#Yu Su et al., In-Situ Bitmaps Generation and Efficient Data Analysis based on Bitmaps, HPDC 2015. | #Yu Su et al., In-Situ Bitmaps Generation and Efficient Data Analysis based on Bitmaps, HPDC 2015. | ||
| − | === | + | |
| + | === 子群发现 === | ||
| + | |||
| + | 子群发现（subgroup mining）是数据分析的一个重要方法。 | ||
基于位图索引的子群发现方法加速。 | 基于位图索引的子群发现方法加速。 | ||
# Yi Wang et al., SciSD: Novel Subgroup Discovery Over Scientific Datasets Using Bitmap Indices, #OSU-CISRC-3/15-TR03, March 2015. | # 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）方法。 | ||
| + | |||
| + | #Gheorghi Guzun et al., "Supporting Dynamic Quantization for High-Dimensional Data Analytics." ExploreDB 2017. | ||
| + | |||
| + | |||
| + | =研究应用= | ||
| + | |||
| + | 数码视讯、中国联通、百度公司、华为技术 | ||
| + | |||
| + | |||
| + | =教材= | ||
| + | # Leskovec, Jure, Anand Rajaraman, and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2014. [http://www.mmds.org/ MMDS_book] | ||
2017年9月24日 (日) 04:40的最后版本
本组研究
实验室研究。
背景
云计算（Cloud Computing）对产业影响巨大，云平台提供商为了获得最大化的经济收益，对计算资源的优化使用具有很强的经济动能，将计算资源的效率发挥到了极致。
云平台提供商对软硬件计算资源的一体化掌控，对软件的性能、能效等专用目标的最优化。
- 趋势1：软硬件协同设计，对一些负载（work load）进行加速器（accelerator）的设计，达到性能、能效等专用目标的最优化。
- 趋势2：软件一体化设计，达到性能度量指标的最优能力。
研究定位
数据分析层面（系统级、功能）：关联规则分析、对比集分析、协同过滤、图的可达性查询
算法实现层面（进程级）： A-Priori 算法、相似度计算、对比集挖掘
数据结构层面（编程语言）：Bitmap/Bit_array/Bitset/... （C++、Go、Java 函数库）
硬件执行层面（处理器层面）：BMI/SSE/AVX/AVX2/FMA （通用机器指令 Instructions）
硬件执行层面（FPGA 层面）：专用机器指令、软硬件协同设计（HW/SW co-design）
本组工作
数据分析层面
协同过滤（Collaborative filtering）
数据结构层面
2014年，本校学生温禹豪提出了SECOMPAX，进一步改进COMPAX算法。
2014年，本校学生常嘉辉提出了PLWAH+算法，改进了PLWAH算法。
2015年，本校学生常嘉辉提出了SPLWAH 算法。
2015年，本校学生吴垠鋆提出了CAMP算法，进一步改进WT(Wavelet Trie)算法。
2015年，本校学生吴垠鋆和温禹豪提出了COMBAT算法，进一步改进了了SECOMPAX算法。
2016年，本校学生温禹豪和王晗提出了MASC算法，进一步改进BBC/WAH算法。
2016年，本校学生李辰星等，提出了BAH算法，进一步改进了BBC算法。
2017年，本校学生郑文勋提出了CODIS方法，进一步改进性能。
位图索引方法
- 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++）
- 本组论文
- Wenxun Zheng et al., CODIS: A New Compression Scheme for Bitmap Indexes, ANCS 2017.
- Chenxing Li et al., BAH: A Bitmap Index Compression Algorithm for Fast Data Retrieval, LCN 2016.
- 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.
- Jiahui Chang et al., SPLWAH: A bitmap index compression scheme for searching in archival Internet traffic. ICC 2015.
- 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
研究方向
研究点：使用位图索引支撑的大数据算法。
底层
处理器与FPGA
MPSoC增强的索引运算
- Sebastian Haas et al., An MPSoC for Energy-Efficient Database Query Processing, DAC 2016.
- Sebastian Haas et al., HW/SW-Database-CoDesign for Compressed Bitmap Index Processing, ASAP 2016.
ISA增强的集运算
- O. Arnold et al., An application-specific instruction set for accelerating set-oriented database primitives. SIGMOD 2014.
有限状态机运行并行加速
使用Intel Xeon Phi加速卡。
- Peng Jiang et al., Combining SIMD and Many Multi-core Parallelism for Finite State Machines with Enumerative Speculation, PPoPP 2017.
上层
非循环图的可达性查询
- Sebastiaan J. van Schaik et al., A Memory Efficient Reachability Data Structure Through Bit Vector Compression, SOGMOD 2011.
频繁项目集发现
查找频繁项目集（Frequent ItemSets）。其中最有名的算法是A-Priori算法。
从数据集中抽取频繁集，抽取的结果往往采用if-then 形式的规则集合来表示，这些规则被称为关联规则（association rule）。频繁项目集发现常常被看成关联规则挖掘（association rule mining）或关联规则发现。
基于位图的Apriori算法加速。
- Sung-Tan Kim et al., "BAR: bitmap-based association rule: an implementation and its optimizations." ACM MoMM 2009.
对比度设置学习
对比度设置学习（对比集分析）是一种关联规则的学习 ，旨在找出有意义的不同的群体之间的差异，通过逆向工程的关键预测指标，确定每一个特定的组。
基于位图的对比集挖掘算法加速。
- Gangyi Zhu et al., SciCSM: Novel Contrast Set Mining over Scientific Datasets Using Bitmap Indices, SSDBM 2015.
数据采样
数据采样（Data Sampling）。
2014年，俄亥俄州立大学的Yu Su等提出了位图索引取样技术处理大规模分布式数据集，这样能保留原始数据的特征，并且造成的损失亦处在可接受范围内。
基于位图索引的数据采样方法。
- 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）
相关性分析位图索引加速。
- Yu Su et al., In-Situ Bitmaps Generation and Efficient Data Analysis based on Bitmaps, HPDC 2015.
子群发现
子群发现（subgroup mining）是数据分析的一个重要方法。
基于位图索引的子群发现方法加速。
- 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）方法。
- Gheorghi Guzun et al., "Supporting Dynamic Quantization for High-Dimensional Data Analytics." ExploreDB 2017.
研究应用
数码视讯、中国联通、百度公司、华为技术
教材
- Leskovec, Jure, Anand Rajaraman, and Jeffrey David Ullman. Mining of massive datasets. Cambridge University Press, 2014. MMDS_book