大数据分析分享部分.ppt

《大数据分析分享部分.ppt》由会员分享，可在线阅读，更多相关《大数据分析分享部分.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析大数据分析分享部分 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日一、大数据时代一、大数据时代二、大数据分析基础二、大数据分析基础三、相似项发现三、相似项发现四、流数据分析四、流数据分析提纲提纲一、大数据

2、时代一、大数据时代一、大数据时代一、大数据时代二、大数据分析基础二、大数据分析基础三、相似项发现三、相似项发现四、流数据分析四、流数据分析电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日一、大数据时代一、大数据时代二、大数据分析基础二、大数据分析基础三、相似项发现三、相似项发现四、流数据分析四、流数据分析提纲提纲一、大数据时代一、大数据时代二、大数据分析基础二、大数据分析基础二、大数据分析基础二、大数据分析基础三、相似项发现三、相似项发现四、流数据分析四、流数据分析电子商务新进展：电

3、子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日准备知识准备知识vv向量空间模型向量空间模型向量空间模型向量空间模型(Vector Space Model)(Vector Space Model)：模型根据文本中的词汇：模型根据文本中的词汇：模型根据文本中的词汇：模型根据文本中的词汇出现在整个文本集中的频次为每个词汇计算出一个权重，形成出现在整个文本集中的频次为每个词汇计算出一个权重，形成出现在整个文本集中的频次为每个词汇计算出一个权重，形成出现在整个文本集中的频次为每个词汇计算出一个权重，形成关于该

4、文本的关于该文本的关于该文本的关于该文本的 向量空间。向量空间。向量空间。向量空间。vv假定文档集中有假定文档集中有假定文档集中有假定文档集中有N N篇文档，词项篇文档，词项篇文档，词项篇文档，词项i i出现在出现在出现在出现在n ni i个文档中且在文档个文档中且在文档个文档中且在文档个文档中且在文档j j中中中中出现的次数为出现的次数为出现的次数为出现的次数为f fij ij，文档，文档，文档，文档j j包含的词数为包含的词数为包含的词数为包含的词数为f fj j，则：，则：，则：，则：TF(Term Frequency):TFTF(Term Frequency):TFij ij=f fi

5、j ij/f fj jIDF(Inverse Document Frequency)IDF(Inverse Document Frequency)：IDFIDFi i=log=log2 2 N/N/n ni ivv则词项则词项则词项则词项i i在页面在页面在页面在页面j j上的权重上的权重上的权重上的权重w wij ij计算如下：计算如下：计算如下：计算如下：w wij ij=TF=TFij ijIDFIDFi i（TFIDFTFIDF模型：模型：模型：模型：有多种计算策略有多种计算策略有多种计算策略有多种计算策略）i i1 1i i2 2.i ik k0.120.120.500.50.0.0

6、70.07电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日准备知识准备知识vv哈希函数哈希函数哈希函数哈希函数h h：将哈希键值（整数）随机化。：将哈希键值（整数）随机化。：将哈希键值（整数）随机化。：将哈希键值（整数）随机化。输入：哈希键值输入：哈希键值输入：哈希键值输入：哈希键值(hash-key)(hash-key)输出：桶编号输出：桶编号输出：桶编号输出：桶编号(bucket number)(bucket number)不同类型的数据都可以转化成比特位序列，从而都可以解不同类

7、型的数据都可以转化成比特位序列，从而都可以解不同类型的数据都可以转化成比特位序列，从而都可以解不同类型的数据都可以转化成比特位序列，从而都可以解释为整数。释为整数。释为整数。释为整数。vv用哈希函数构建索引用哈希函数构建索引用哈希函数构建索引用哈希函数构建索引输入：用于建立索引的一个或多个字段输入：用于建立索引的一个或多个字段输入：用于建立索引的一个或多个字段输入：用于建立索引的一个或多个字段输出：桶编号，每条记录映射到一个桶，具有相同输入的输出：桶编号，每条记录映射到一个桶，具有相同输入的输出：桶编号，每条记录映射到一个桶，具有相同输入的输出：桶编号，每条记录映射到一个桶，具有相同输入的不同

8、字段，可以映射到同一个桶。不同字段，可以映射到同一个桶。不同字段，可以映射到同一个桶。不同字段，可以映射到同一个桶。vv其他相关知识：磁盘存储、幂律分布其他相关知识：磁盘存储、幂律分布其他相关知识：磁盘存储、幂律分布其他相关知识：磁盘存储、幂律分布电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv矩阵矩阵矩阵矩阵-向量乘积向量乘积向量乘积向量乘积假定矩阵假定矩阵假定矩阵假定矩阵M=mM=mij ij nnnn，向量，向量，向量，向量V

9、=vV=vj j n n,n,n足够大，但足够大，但足够大，但足够大，但V V可以一次读入内存可以一次读入内存可以一次读入内存可以一次读入内存MapMap函数：函数：函数：函数：每个每个每个每个MapMap任务将任务将任务将任务将整个向量整个向量整个向量整个向量V V和矩阵和矩阵和矩阵和矩阵MM的一个文件块作为输的一个文件块作为输的一个文件块作为输的一个文件块作为输入。对每个矩阵元素入。对每个矩阵元素入。对每个矩阵元素入。对每个矩阵元素mmij ij，MapMap任务会产生键值对任务会产生键值对任务会产生键值对任务会产生键值对(i,m(i,mij ijv vj j)。例如，。例如，。例如，。例

10、如，(i,(i,mmi1i1v v1 1),(i,m),(i,mininv vn n)ReduceReduce函数：函数：函数：函数：ReduceReduce任务将所有与给定键任务将所有与给定键任务将所有与给定键任务将所有与给定键i i关联的值相加即可得到。关联的值相加即可得到。关联的值相加即可得到。关联的值相加即可得到。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv矩阵矩阵矩阵矩阵-向量乘积向量乘积向量乘积向量乘积假定矩阵假定矩

11、阵假定矩阵假定矩阵M=mM=mij ij nnnn，向量，向量，向量，向量V=vV=vj j n n,n,n足够大且足够大且足够大且足够大且V V无法一次读入内存无法一次读入内存无法一次读入内存无法一次读入内存处理思路：处理思路：处理思路：处理思路：vv将将将将MM分割成分割成分割成分割成k k个宽度相等的垂直条，对应的将个宽度相等的垂直条，对应的将个宽度相等的垂直条，对应的将个宽度相等的垂直条，对应的将V V分成分成分成分成k k个高度相个高度相个高度相个高度相等的水平条。分割后的每个水平条都能够放入内存。等的水平条。分割后的每个水平条都能够放入内存。等的水平条。分割后的每个水平条都能够放入

12、内存。等的水平条。分割后的每个水平条都能够放入内存。vv将每个垂直条、水平条都存成一个文件将每个垂直条、水平条都存成一个文件将每个垂直条、水平条都存成一个文件将每个垂直条、水平条都存成一个文件vv这样就转换成向量可读入内存的矩阵这样就转换成向量可读入内存的矩阵这样就转换成向量可读入内存的矩阵这样就转换成向量可读入内存的矩阵-向量乘积。向量乘积。向量乘积。向量乘积。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv关系选择关系选择关系选

13、择关系选择对关系对关系对关系对关系R R的每个元组应用条件的每个元组应用条件的每个元组应用条件的每个元组应用条件C C，得到仅满足条件，得到仅满足条件，得到仅满足条件，得到仅满足条件C C的元的元的元的元组，记为组，记为组，记为组，记为 C C(R)(R)。(select*where C from R)(select*where C from R)MapMap函数：函数：函数：函数：对对对对R R中的每个元组中的每个元组中的每个元组中的每个元组t t，检测它是否满足，检测它是否满足，检测它是否满足，检测它是否满足C C。如果。如果。如果。如果满足，则产生一个键值对满足，则产生一个键值对满足，则

14、产生一个键值对满足，则产生一个键值对(t,t)(t,t)。键和值都是。键和值都是。键和值都是。键和值都是t t。ReduceReduce函数：函数：函数：函数：类似于恒等运算，将每个键值对传递到输类似于恒等运算，将每个键值对传递到输类似于恒等运算，将每个键值对传递到输类似于恒等运算，将每个键值对传递到输出部分即可。出部分即可。出部分即可。出部分即可。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv关系投影关系投影关系投影关系投影对关

15、系对关系对关系对关系R R的某个属性子集的某个属性子集的某个属性子集的某个属性子集S S，从每个元组中得到仅包含，从每个元组中得到仅包含，从每个元组中得到仅包含，从每个元组中得到仅包含S S中属性的元素。记为中属性的元素。记为中属性的元素。记为中属性的元素。记为 S S(R)(R)。(select S from R)(select S from R)MapMap函数：函数：函数：函数：对对对对R R中的每个元组中的每个元组中的每个元组中的每个元组t t，剔除，剔除，剔除，剔除t t中属性不在中属性不在中属性不在中属性不在S S中的中的中的中的字段得到元组字段得到元组字段得到元组字段得到元组t

16、t，输出键值对，输出键值对，输出键值对，输出键值对(t,t)(t,t)。将可能存在。将可能存在。将可能存在。将可能存在t t相同的相同的相同的相同的多个键值对转换成键值表对，即多个键值对转换成键值表对，即多个键值对转换成键值表对，即多个键值对转换成键值表对，即(t,t,t,t)(t,t,t,t)ReduceReduce函数：函数：函数：函数：将将将将(t,t,t,t)(t,t,t,t)转换成转换成转换成转换成(t,t)(t,t)输出，以保证输出，以保证输出，以保证输出，以保证对任意键对任意键对任意键对任意键t t仅产生一个键值对仅产生一个键值对仅产生一个键值对仅产生一个键值对(t,t)(t,t

17、)。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv分组与聚合分组与聚合分组与聚合分组与聚合设关系为设关系为设关系为设关系为R(A,B,C)R(A,B,C)，分组：分组：分组：分组：按照属性子集按照属性子集按照属性子集按照属性子集A A对元组进行分对元组进行分对元组进行分对元组进行分割，割，割，割，A A的所有属性值相同的元组分为一组。的所有属性值相同的元组分为一组。的所有属性值相同的元组分为一组。的所有属性值相同的元组分为一组。聚

18、合：聚合：聚合：聚合：对每个对每个对每个对每个组中所有元组的组中所有元组的组中所有元组的组中所有元组的B B属性值进行属性值进行属性值进行属性值进行 运算，运算，运算，运算，运算包括运算包括运算包括运算包括sum,sum,count,avg,min,maxcount,avg,min,max。A,A,(B)(B)(R)(R)，A A、B B由用户指定。由用户指定。由用户指定。由用户指定。MapMap函数：函数：函数：函数：对对对对R R中的每个元组中的每个元组中的每个元组中的每个元组(a a,b b,c c)，生成键值对，生成键值对，生成键值对，生成键值对(a a,b b)ReduceReduc

19、e函数：函数：函数：函数：对于相同的键对于相同的键对于相同的键对于相同的键a a，输入到对应的，输入到对应的，输入到对应的，输入到对应的ReduceReduce任务任务任务任务的键值表对为的键值表对为的键值表对为的键值表对为(a a,b b1 1,.,.,b bn n)，对值表，对值表，对值表，对值表 b b1 1,.,.,b bn n 进行进行进行进行 操作，操作，操作，操作，得到得到得到得到结结结结果果果果x x。则键则键则键则键a a对应的输出为：对应的输出为：对应的输出为：对应的输出为：(a a,x x)电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分

20、析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv两个关系的并两个关系的并两个关系的并两个关系的并对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系R R、S S中的所有元组进行中的所有元组进行中的所有元组进行中的所有元组进行“并并并并”操作。操作。操作。操作。Union(R,S)Union(R,S)MapMap函数：函数：函数：函数：将每个输入元组将每个输入元组将每个输入元组将每个输入元组t t转变为键值对转变为键值对转变为键值对转变为键值对(t,t)(t,t)。输入文件。输

21、入文件。输入文件。输入文件可能来自关系可能来自关系可能来自关系可能来自关系R R的文件块，也可能来自关系的文件块，也可能来自关系的文件块，也可能来自关系的文件块，也可能来自关系S S的文件块。的文件块。的文件块。的文件块。ReduceReduce函数：函数：函数：函数：和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两个值，两种情况下都输出两种情况下都输出两种情况下都输出两种情况下都输出(t,t)(t,t)。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据

22、分析20222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv两个关系的交两个关系的交两个关系的交两个关系的交对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系R R、S S中的所有元组进行中的所有元组进行中的所有元组进行中的所有元组进行“交交交交”操作。操作。操作。操作。Intersection(R,S)Intersection(R,S)MapMap函数：函数：函数：函数：将每个输入元组将每个输入元组将每个输入元组将每个输入元组t t转变为键值对转变为键值对转变为键值对转变为键值对(t,t)(t,t)。R

23、educeReduce函数：函数：函数：函数：和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两个值，如果键值表对为如果键值表对为如果键值表对为如果键值表对为(t,t,t)(t,t,t)，则输出，则输出，则输出，则输出(t,t)(t,t)；若键值表对为；若键值表对为；若键值表对为；若键值表对为(t,t)(t,t)，则输出，则输出，则输出，则输出(t,NULL)(t,NULL)电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年111

24、1月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv两个关系的差两个关系的差两个关系的差两个关系的差对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系R R、S S中的所有元组进行中的所有元组进行中的所有元组进行中的所有元组进行“差差差差”操作。操作。操作。操作。Difference(R,S)=R-SDifference(R,S)=R-SMapMap函数：函数：函数：函数：将每个输入元组将每个输入元组将每个输入元组将每个输入元组t t转变为键值对转变为键值对转变为键值对转变为键值对(t,R)(t,R)或或或或(t,S)(t,S)。

25、ReduceReduce函数：函数：函数：函数：输入到输入到输入到输入到ReduceReduce函数的键值表对有三种情函数的键值表对有三种情函数的键值表对有三种情函数的键值表对有三种情况，即况，即况，即况，即(t,R),(t,S),(t,R,S)(t,R),(t,S),(t,R,S)，如果键值表对为，如果键值表对为，如果键值表对为，如果键值表对为(t,R)(t,R)，则输，则输，则输，则输出出出出(t,t)(t,t)；否则输出；否则输出；否则输出；否则输出(t,NULL)(t,NULL)电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20

26、222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv两个关系的自然连接两个关系的自然连接两个关系的自然连接两个关系的自然连接给定两个关系给定两个关系给定两个关系给定两个关系R(A,B)R(A,B)、S(B,C)S(B,C)，B B是是是是R R、S S的所有共同属性子集。的所有共同属性子集。的所有共同属性子集。的所有共同属性子集。比较比较比较比较R R、S S的每对元组，若两个元组关于子集的每对元组，若两个元组关于子集的每对元组，若两个元组关于子集的每对元组，若两个元组关于子集B B的所有属性值相的所有属性值相的所有属性值相的所有属性值相同，

27、则生成一个新元组同，则生成一个新元组同，则生成一个新元组同，则生成一个新元组(A,B,C)(A,B,C)。R R S SMapMap函数：函数：函数：函数：对于对于对于对于R R的每个元组的每个元组的每个元组的每个元组(a a,b b)，生成键值对，生成键值对，生成键值对，生成键值对(b b,(R,(R,a a)；对；对；对；对于于于于S S的每个元组的每个元组的每个元组的每个元组(b b,c c)，生成键值对，生成键值对，生成键值对，生成键值对(b b,(S,(S,c c)。ReduceReduce函数：函数：函数：函数：对于相同的键对于相同的键对于相同的键对于相同的键b b，输入到对应的，

28、输入到对应的，输入到对应的，输入到对应的ReduceReduce任务的键任务的键任务的键任务的键值表对为值表对为值表对为值表对为(b b,(R,(R,a a1 1),.,(R,),.,(R,a amm);(S,);(S,c c1 1),(S,),(S,c cn n)，则键，则键，则键，则键b b对应的输对应的输对应的输对应的输出为：出为：出为：出为：(b b,(,(a a1 1,b b,c c1 1),(),(a a1 1,b b,c cn n),(),(a amm,b b,c c1 1),(),(a amm,b b,c cn n)连接运算可能导致元组数目大大增加连接运算可能导致元组数目大大增

29、加连接运算可能导致元组数目大大增加连接运算可能导致元组数目大大增加。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv矩阵乘积矩阵乘积矩阵乘积矩阵乘积假定矩阵假定矩阵假定矩阵假定矩阵M=M=mmij ij mm l l，N=N=n njkjk l l n n处理思路：处理思路：处理思路：处理思路：vv将将将将MM、N N分别看成两个关系分别看成两个关系分别看成两个关系分别看成两个关系M(I,J,V)M(I,J,V)、N(J,K,W)N

30、(J,K,W)，对应的元组分别为对应的元组分别为对应的元组分别为对应的元组分别为(i i,j j,mmij ij)和和和和(j j,k k,n njkjk)。vv将矩阵乘法转换为两个关系的自然连接与分组和聚将矩阵乘法转换为两个关系的自然连接与分组和聚将矩阵乘法转换为两个关系的自然连接与分组和聚将矩阵乘法转换为两个关系的自然连接与分组和聚合运算。合运算。合运算。合运算。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv矩阵乘积（两步运算

31、）矩阵乘积（两步运算）矩阵乘积（两步运算）矩阵乘积（两步运算）Map1Map1函数函数函数函数：将：将：将：将mmij ij转换为转换为转换为转换为(j j,(M,(M,i i,mmij ij)，将，将，将，将n njkjk转换为转换为转换为转换为(j j,(N,(N,k k,n njkjk)Reduce1Reduce1函数函数函数函数：对于每个键：对于每个键：对于每个键：对于每个键j j，输入到指定，输入到指定，输入到指定，输入到指定ReduceReduce任务的键值任务的键值任务的键值任务的键值表对为表对为表对为表对为(j j,(M,1,(M,1,mm1 1j j),(M,),(M,mm,

32、mmmjmj);(N,1,);(N,1,n nj j1 1),(N,),(N,n n,n njnjn)，输，输，输，输出为出为出为出为(j j,(,(i i,k k,mmij ijn njkjk),;),;i i=1,=1,mm;k k=1,=1,n n)Map2Map2函数函数函数函数：将：将：将：将ReduceReduce的输出作为的输出作为的输出作为的输出作为Map2Map2的输入，输出键值对的输入，输出键值对的输入，输出键值对的输入，输出键值对(i i,k k),),mmij ijn njkjk)Reduce2Reduce2函数函数函数函数：对于每个键：对于每个键：对于每个键：对于每个

33、键(i i,k k)，输入到指定，输入到指定，输入到指定，输入到指定ReduceReduce任务的任务的任务的任务的键值表对为键值表对为键值表对为键值表对为(i i,k k),),mmi i1 1n n1 1k k,mmi i2 2n n2 2k k,mmil iln nlklk)，计算与键，计算与键，计算与键，计算与键(i i,k k)关关关关联的所有值之和联的所有值之和联的所有值之和联的所有值之和v v=mmi i1 1n n1 1k k+mmi i2 2n n2 2k k+mmil iln nlklk ，输出，输出，输出，输出(i i,k k),),v v)，v v是矩阵是矩阵是矩阵是矩

34、阵P=MNP=MN的第的第的第的第i i行第行第行第行第k k列的元素值。列的元素值。列的元素值。列的元素值。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日基于基于Map-Reduce的基本运算的基本运算vv矩阵乘积（单步运算）矩阵乘积（单步运算）矩阵乘积（单步运算）矩阵乘积（单步运算）MapMap函数函数函数函数：将：将：将：将mmij ij转换为转换为转换为转换为(i i,k k),(M,),(M,j j,mmij ij)，k k=1,=1,n n；将；将；将；将n njkjk

35、转换为转换为转换为转换为(i i,k k),(N,),(N,j j,n njkjk)，i i=1,=1,mmReduceReduce函数函数函数函数：每个键：每个键：每个键：每个键(i i,k k)关联的值为关联的值为关联的值为关联的值为(M,(M,j j,mmij ij)和和和和(N,(N,j j,n njkjk)，j j=1,2,=1,2,l l。将。将。将。将 (M,(M,j j,mmij ij)和和和和(N,(N,j j,n njkjk)按按按按j j值排序放在不同的值排序放在不同的值排序放在不同的值排序放在不同的列表中，将两个列表的第列表中，将两个列表的第列表中，将两个列表的第列表中

36、，将两个列表的第j j个元组中的个元组中的个元组中的个元组中的mmij ij和和和和n njkjk抽出来相乘，然后再将积按抽出来相乘，然后再将积按抽出来相乘，然后再将积按抽出来相乘，然后再将积按j j相加得相加得相加得相加得到到到到v v，最后输出，最后输出，最后输出，最后输出(i i,k k),),v v)。MM1 1mmi i1 1MM2 2mmi2i2MMl lmmil ilN N1 1n n1 1k kN N2 2n n2 2k kN Nl ln nlklk电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1

37、111月月月月2222日日日日集群计算的算法效率问题（自学参考）集群计算的算法效率问题（自学参考）集群计算的算法效率问题（自学参考）集群计算的算法效率问题（自学参考）vv集群计算的通信开销模型集群计算的通信开销模型集群计算的通信开销模型集群计算的通信开销模型集群计算的开销主要来自任务间数据的移动：通信开销，而不集群计算的开销主要来自任务间数据的移动：通信开销，而不集群计算的开销主要来自任务间数据的移动：通信开销，而不集群计算的开销主要来自任务间数据的移动：通信开销，而不是任务的执行时间。因为：算法中每个执行任务都非常简单，是任务的执行时间。因为：算法中每个执行任务都非常简单，是任务的执行时间。

38、因为：算法中每个执行任务都非常简单，是任务的执行时间。因为：算法中每个执行任务都非常简单，时间复杂度最多和输入规模成线性关系；数据传输速度相对于时间复杂度最多和输入规模成线性关系；数据传输速度相对于时间复杂度最多和输入规模成线性关系；数据传输速度相对于时间复杂度最多和输入规模成线性关系；数据传输速度相对于处理器执行指令的速度要慢。处理器执行指令的速度要慢。处理器执行指令的速度要慢。处理器执行指令的速度要慢。通信开销仅考虑所有输入的开销而不考虑输出的开销。因为：通信开销仅考虑所有输入的开销而不考虑输出的开销。因为：通信开销仅考虑所有输入的开销而不考虑输出的开销。因为：通信开销仅考虑所有输入的开销

39、而不考虑输出的开销。因为：任务任务任务任务T T的输出是另一个任务的输入，因此当度量接收任务的输的输出是另一个任务的输入，因此当度量接收任务的输的输出是另一个任务的输入，因此当度量接收任务的输的输出是另一个任务的输入，因此当度量接收任务的输入规模时，入规模时，入规模时，入规模时，T T的输出规模已被计算；一般而言，最终输出结果的输出规模已被计算；一般而言，最终输出结果的输出规模已被计算；一般而言，最终输出结果的输出规模已被计算；一般而言，最终输出结果相对于输入规模或中间数据相比，都要更小一些。相对于输入规模或中间数据相比，都要更小一些。相对于输入规模或中间数据相比，都要更小一些。相对于输入规模

40、或中间数据相比，都要更小一些。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日集群计算的算法效率问题集群计算的算法效率问题vv实耗通信开销实耗通信开销实耗通信开销实耗通信开销在工作流网络中，所有路径中的最大通信开销。路径通信在工作流网络中，所有路径中的最大通信开销。路径通信在工作流网络中，所有路径中的最大通信开销。路径通信在工作流网络中，所有路径中的最大通信开销。路径通信开销是指该路径上所有任务的通信开销之和。开销是指该路径上所有任务的通信开销之和。开销是指该路径上所有任务的通信开销

41、之和。开销是指该路径上所有任务的通信开销之和。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日集群计算的算法效率问题集群计算的算法效率问题vv多路连接（多路连接（多路连接（多路连接（n n路连接）路连接）路连接）路连接）选定自然连接中的关系的选定自然连接中的关系的选定自然连接中的关系的选定自然连接中的关系的连接属性连接属性连接属性连接属性 A A1 1,A A2 2,A An n，并将这些属，并将这些属，并将这些属，并将这些属性值哈希到一定数量的桶中（桶编号与哈希值一一对应）；性值哈

42、希到一定数量的桶中（桶编号与哈希值一一对应）；性值哈希到一定数量的桶中（桶编号与哈希值一一对应）；性值哈希到一定数量的桶中（桶编号与哈希值一一对应）；对每个连接属性对每个连接属性对每个连接属性对每个连接属性A Ai i(i i=1,=1,n n)选定桶的数量选定桶的数量选定桶的数量选定桶的数量t ti i（对应的桶编号记（对应的桶编号记（对应的桶编号记（对应的桶编号记为为为为0(0(i i),),t ti i-1(-1(i i)），使得），使得），使得），使得t t1 1 t t2 2t tn n=k k，k k为为为为ReduceReduce任务数；任务数；任务数；任务数；记桶编号向量为记桶

43、编号向量为记桶编号向量为记桶编号向量为V=V=v v1 1,v vi i,v vn n，其中，其中，其中，其中v vi i是连接属性是连接属性是连接属性是连接属性a ai i的某个的某个的某个的某个桶编号，每一个向量桶编号，每一个向量桶编号，每一个向量桶编号，每一个向量V V标记一个标记一个标记一个标记一个ReduceReduce任务；任务；任务；任务；将每个关系的元组传递给相应的将每个关系的元组传递给相应的将每个关系的元组传递给相应的将每个关系的元组传递给相应的ReduceReduce任务。由于元组可能任务。由于元组可能任务。由于元组可能任务。由于元组可能只有部分连接属性有值，因此哈希形成的

44、向量只有部分连接属性有值，因此哈希形成的向量只有部分连接属性有值，因此哈希形成的向量只有部分连接属性有值，因此哈希形成的向量V V中存在某些分中存在某些分中存在某些分中存在某些分量未知，因此要将该元组传递给未知分量所有可能取值所对量未知，因此要将该元组传递给未知分量所有可能取值所对量未知，因此要将该元组传递给未知分量所有可能取值所对量未知，因此要将该元组传递给未知分量所有可能取值所对应的所有应的所有应的所有应的所有ReduceReduce任务。任务。任务。任务。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年111

45、1月月月月2222日日日日集群计算的算法效率问题集群计算的算法效率问题vv三个关系的连接三个关系的连接三个关系的连接三个关系的连接设待连接的三个关系分别为设待连接的三个关系分别为设待连接的三个关系分别为设待连接的三个关系分别为R(C,AR(C,A1 1)、S(AS(A1 1,A,A2 2)、T(AT(A2 2,D),D)，规，规，规，规模分别为模分别为模分别为模分别为r r,s s,t t。且假定。且假定。且假定。且假定R R与与与与S S、S S与与与与T T可连接的概率均为可连接的概率均为可连接的概率均为可连接的概率均为p p。连接策略一连接策略一连接策略一连接策略一：采用两次：采用两次：

46、采用两次：采用两次二路连接二路连接二路连接二路连接完成三个关系的连接完成三个关系的连接完成三个关系的连接完成三个关系的连接vv先连接先连接先连接先连接R R S S，再连接，再连接，再连接，再连接T T，总通信开销为，总通信开销为，总通信开销为，总通信开销为2 2r r+2+2s s+2+2prsprs+2+2t tvv先连接先连接先连接先连接S S T T，再连接，再连接，再连接，再连接R R，总通信开销为，总通信开销为，总通信开销为，总通信开销为2 2t t+2+2s s+2+2ptspts+2+2r r连接策略二连接策略二连接策略二连接策略二：采用一次：采用一次：采用一次：采用一次三路连

47、接三路连接三路连接三路连接完成三个关系的连接完成三个关系的连接完成三个关系的连接完成三个关系的连接vv设计划的设计划的设计划的设计划的ReduceReduce任务数为任务数为任务数为任务数为k k，记，记，记，记b b,c c为将连接属性为将连接属性为将连接属性为将连接属性A A1 1和和和和A A2 2哈哈哈哈希到的桶数，希到的桶数，希到的桶数，希到的桶数，bcbc=k k，对应的哈希函数分别为，对应的哈希函数分别为，对应的哈希函数分别为，对应的哈希函数分别为h h和和和和g g。每当。每当。每当。每当h h(v v)=)=i i且且且且g g(w w)=)=j j，对应桶，对应桶，对应桶，

48、对应桶(i i,j j)的的的的ReduceReduce任务就负责连接元组任务就负责连接元组任务就负责连接元组任务就负责连接元组R(R(u u,v v),S(),S(v v,w w)和和和和T(T(w w,x x)。电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析20222022年年年年1111月月月月2222日日日日集群计算的算法效率问题集群计算的算法效率问题vv三个关系的连接三个关系的连接三个关系的连接三个关系的连接计算连接策略二的通信开销计算连接策略二的通信开销计算连接策略二的通信开销计算连接策略二的通信开销MapMap的输入总开销

49、：的输入总开销：的输入总开销：的输入总开销：r r+s s+t tReduceReduce的输入总开销：的输入总开销：的输入总开销：的输入总开销：rcrc+s s+btbt。由于。由于。由于。由于MapMap任务在传递任务在传递任务在传递任务在传递R R中的中的中的中的某个元组（设某个元组（设某个元组（设某个元组（设R.AR.A1 1=v v）时，只能知道）时，只能知道）时，只能知道）时，只能知道A A1 1的哈希值的哈希值的哈希值的哈希值h h(v v)，R R中中中中的元组不包含的元组不包含的元组不包含的元组不包含A A2 2，此时桶编号向量为，此时桶编号向量为，此时桶编号向量为，此时桶编

50、号向量为(h h(v v),NULL),NULL)，因此必，因此必，因此必，因此必须要将该元组传递给桶编号向量的第一个分量为须要将该元组传递给桶编号向量的第一个分量为须要将该元组传递给桶编号向量的第一个分量为须要将该元组传递给桶编号向量的第一个分量为h h(v v)所对应所对应所对应所对应的所有的所有的所有的所有ReduceReduce任务，共计任务，共计任务，共计任务，共计c c个。个。个。个。优化设计：优化设计：优化设计：优化设计：r r+s s+t t是常数，可优化的对象是是常数，可优化的对象是是常数，可优化的对象是是常数，可优化的对象是ReduceReduce的输入总开的输入总开的输入