2018年8月9日 (四) 02:44的版本

关系代数运算

关系（relation）是由列表头（称为属性）组成的表。

关系中的行称为元组（Tuple）。

关系中属性集合称为关系的模式（Schema）。

关系代数运算：

（1）选择（Selection）

（2）投影（Projection）

（3）并（union）、交（intersection）、差（differences）

（4）自然连接（Natural Join）：给定两个关系，比较两个关系中的每对元组。如果两个元组的所有公共属性的属性值一致，则生成一个新的元组。

（5）分组和聚合（Grouping and Aggregation）：聚合运算包括SUM、COUNT、AVG、MIN和MAX。

数据分析

数据分析（Data Analytic），是指对数据集（DataSet）的属性值进行统计，以发现有用的信息。

常用的操作有集合SUM，TopN，Rank，Select操作。交互式分析一般要求实时响应。

集合运算

集合（Set）

For a set of integers: S = {1, 2, 3, 1000}. Set operations include:

membership test: x ∈ S?

Set intersection: S1 ∩ S2

Set union: S1 ∪ S2

Set differences: S1 ∖ S2

Jaccard Index (Tanimoto similarity) ∣S1 ∩ S2 ∣/∣S1 ∪ S2 ∣

有序集合（Ordered Set）

• Iterate:

in sorted order,

in reverse order,

skippable iterators (jump to first value ≥ x)

• Rank: how many elements of the set are smaller than k? (counting the number of ones up to a given position)

• Select: find the kth smallest value (finding the position of the k-th bit set)

• Min/max: find the maximal and minimal value

Broadword Implementation of Rank/Select Queries

研究论文：

1. Vigna, Sebastiano. "Broadword implementation of rank/select queries." In International Workshop on Experimental and Efficient Algorithms, WEA 2008.

频繁项目集发现

查找频繁项目集ItemSets。其中最有名的算法是A-Priori算法。

从数据集中抽取频繁集，抽取的结果往往采用if-then 形式的规则集合来表示，这些规则被称为关联规则（association rule）。频繁项目集发现常常被看成关联规则挖掘（association rule mining）或关联规则发现。

基于位图的PCY算法。

1. Park, Jong Soo, Ming-Syan Chen, and Philip S. Yu. An effective hash-based algorithm for mining association rules. ACM Sigmod 1995.

基于位图的A-Priori算法加速。

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.

独立元素计数问题

FM（Flajolet-Martin）算法

1. Flajolet, Philippe, and G. Nigel Martin. "Probabilistic counting algorithms for data base applications." FoCS 1983.

窗口内计数问题

DGIM（Datar-Gionis-Indyk-Motwani）算法

1. Datar, M., Gionis, A., Indyk, P., & Motwani, R. (2002). Maintaining stream statistics over sliding windows. SIAM journal on computing, 31(6), 1794-1813.

基数预估

基数预估或估计（Cardinality Estimation），评估一个集合中不同数据项的个数的近似算法。比如，访问一个网站的独立IP个数。

基数预估主要研究如何统计一组数据中不同元素的个数。这看似是一个简单的工作，当时当数据量达到亿级时，想要在所有情况下短时间准确计算出不同元素个数是十分困难的。但是这在构造索引表的初始地址申请估计中有一些作用。同时在大数据时代的今天，高效地处理海量的数据也是十分必要的，而已有的算法hyperloglog给出了一个合理的回答，它能够较为准确地估计出不同元素的个数同时仅用少量的存储空间。

注意到对于一个[0,1]均匀分布，如果随机抽取n个点，那么期望下最小点的值为1/n。这给出了对于基数的一个可行估计，即可以通过求出所有值的最小值m,估计n为1/m。利用这个思想可以先通过hash函数来在保持数据重复性不变的情况下，保证数据的均匀随机性，之后即可应用这种方法完成估计。在实际中可以应用另一种方法——分析每个数据中结尾连续0的数目，以该连续数目最大值的2的幂次进行估计。

为进一步细化估计，可以采用将数据的值域分成若干小区间，对于每个小区叫分析，最后再合并。合并不是简单的合并，常规方法是求算术平均数，而hyperloglog却采用求调和平均数的方式并辅以常数的修正来完成组合。

注意到在中估计下如果基数太大或者太小都会严重影响结果的准确性，hyperloglog对此进行了处理。当划分后的值域小区域无法被大部分填满后，就可以利用填满的值域小区域的数目对结果进行估计，当每个小区域都被大量填满后，就需要对结果进行一定程度的修正。

利用这种方法可以利用极少的空间资源完成对海量数据的操作，因为主要的空间用于划分的值域小区域，而只需要很少的值域小区间就可以使得结果与准确解之间的差距被控制在可以接受的范围内。

• Cardinality Estimation Algorithm

1. Flajolet, Philippe, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. "Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm." DMTCS Proceedings 1 (2008).
2. Heule, Stefan, Marc Nunkesser, and Alexander Hall. "HyperLogLog in practice: algorithmic engineering of a state of the art cardinality estimation algorithm." In Proceedings of the 16th International Conference on Extending Database Technology, pp. 683-692. ACM, 2013.

聚类

聚类是对点集按照某种距离测度将它们聚成多个簇的过程。聚类目标是使得同一簇内的点之间距离较短，而不同的簇中的点之间距离较大。

相关性挖掘

相关性测度（Correlation Metrics ）

地球移动距离（Earth Mover's Distance, EMD）

香农熵（Shannon's Entropy）

互信息（Mutual Information）

条件熵（Conditional Entropy）

相关性挖掘（Correlation Mining）

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

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.

协同过滤

推荐系统

参考教材

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