《最新大数据分析分享部分教学课件.ppt》由会员分享，可在线阅读，更多相关《最新大数据分析分享部分教学课件.ppt（84页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、大数据分析分享部分大数据分析分享部分电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析一、大数据时代一、大数据时代一、大数据时代一、大数据时代二、大数据分析基础二、大数据分析基础二、大数据分析基础二、大数据分析基础三、相似项发现三、相似项发现三、相似项发现三、相似项发现四、流数据分析四、流数据分析四、流数据分析四、流数据分析提纲提纲一、大数据时代一、大数据时代一、大数据时代一、大数据时代二、大数据分析基础二、大数据分析基础二、大数据分析基础二、大数据分析基础三、相似项发现三、相似项发现三、相似项发现三、相似项发现四、流数据分析四、流数据分析
2、四、流数据分析四、流数据分析2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析电子商务新进展：
3、电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析基于基于Map-Reduce的基本运算的基本运算vv关系投影关系投影关系投影关系投影对关系对关系对关系对关系R R的某个属性子集的某个属性子集的某个属性子集的某个属性子集S S，从每个元组中得到仅包含，从每个元组中得到仅包含，从每个元组中得到仅包含，从每个元组中得到仅包含S S中属性的元素。记为中属性的元素。记为中属性的元素。记为中属性的元素。记为 S S(R)(R)。(selectSfromR)(sel
4、ectSfromR)MapMap函数：函数：函数：函数：对对对对R R中的每个元组中的每个元组中的每个元组中的每个元组t t，剔除，剔除，剔除，剔除t t中属性不在中属性不在中属性不在中属性不在S S中的中的中的中的字段得到元组字段得到元组字段得到元组字段得到元组t t，输出键值对，输出键值对，输出键值对，输出键值对(t,t)(t,t)。将可能存在。将可能存在。将可能存在。将可能存在t t相同的相同的相同的相同的多个键值对转换成键值表对，即多个键值对转换成键值表对，即多个键值对转换成键值表对，即多个键值对转换成键值表对，即(t,t,t,t)(t,t,t,t)ReduceReduce函数：函数：
5、函数：函数：将将将将(t,t,t,t)(t,t,t,t)转换成转换成转换成转换成(t,t)(t,t)输出，以保证输出，以保证输出，以保证输出，以保证对任意键对任意键对任意键对任意键t t仅产生一个键值对仅产生一个键值对仅产生一个键值对仅产生一个键值对(t,t)(t,t)。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析基于基于Map-Reduce的基本运算的基本运算vv分组与聚合分组与聚合分组与聚合分组与聚合设关系为设关系为设关系为设关系为R(A,B,C)R(A,B,C)，分组：分组：分组：分组：按照属
6、性子集按照属性子集按照属性子集按照属性子集A A对元组进行分对元组进行分对元组进行分对元组进行分割，割，割，割，A A的所有属性值相同的元组分为一组。的所有属性值相同的元组分为一组。的所有属性值相同的元组分为一组。的所有属性值相同的元组分为一组。聚合：聚合：聚合：聚合：对每个对每个对每个对每个组中所有元组的组中所有元组的组中所有元组的组中所有元组的B B属性值进行属性值进行属性值进行属性值进行 运算，运算，运算，运算，运算包括运算包括运算包括运算包括sum,sum,count,avg,min,maxcount,avg,min,max。A,A,(B)(B)(R)(R)，A A、B B由用户指定。
7、由用户指定。由用户指定。由用户指定。MapMap函数：函数：函数：函数：对对对对R R中的每个元组中的每个元组中的每个元组中的每个元组(a a,b b,c c)，生成键值对，生成键值对，生成键值对，生成键值对(a a,b b)ReduceReduce函数：函数：函数：函数：对于相同的键对于相同的键对于相同的键对于相同的键a a，输入到对应的，输入到对应的，输入到对应的，输入到对应的ReduceReduce任务任务任务任务的键值表对为的键值表对为的键值表对为的键值表对为(a a,b b1 1,.,.,b bn n)，对值表，对值表，对值表，对值表 b b1 1,.,.,b bn n 进行进行进行
8、进行 操作，操作，操作，操作，得到得到得到得到结结结结果果果果x x。则键则键则键则键a a对应的输出为：对应的输出为：对应的输出为：对应的输出为：(a a,x x)2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析基于基于Map-Reduce的基本运算的基本运算vv两个关系的并两个关系的并两个关系的并两个关系的并对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系R R、S S中的所有元组进行中的所有元组进行中的所有元组进行中的所有元组进行“并并并并”操作。操作。操作
9、。操作。Union(R,S)Union(R,S)MapMap函数：函数：函数：函数：将每个输入元组将每个输入元组将每个输入元组将每个输入元组t t转变为键值对转变为键值对转变为键值对转变为键值对(t,t)(t,t)。输入文件。输入文件。输入文件。输入文件可能来自关系可能来自关系可能来自关系可能来自关系R R的文件块，也可能来自关系的文件块，也可能来自关系的文件块，也可能来自关系的文件块，也可能来自关系S S的文件块。的文件块。的文件块。的文件块。ReduceReduce函数：函数：函数：函数：和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两
10、个值，和每个键关联的可能有一个值或两个值，两种情况下都输出两种情况下都输出两种情况下都输出两种情况下都输出(t,t)(t,t)。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析基于基于Map-Reduce的基本运算的基本运算vv两个关系的交两个关系的交两个关系的交两个关系的交对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系R R、S S中的所有元组进行中的所有元组进行中的所有元组进行中的所有元组进行“交交交交”操作。操作。操作。操作。Intersection(R,
11、S)Intersection(R,S)MapMap函数：函数：函数：函数：将每个输入元组将每个输入元组将每个输入元组将每个输入元组t t转变为键值对转变为键值对转变为键值对转变为键值对(t,t)(t,t)。ReduceReduce函数：函数：函数：函数：和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两个值，和每个键关联的可能有一个值或两个值，如果键值表对为如果键值表对为如果键值表对为如果键值表对为(t,t,t)(t,t,t)，则输出，则输出，则输出，则输出(t,t)(t,t)；若键值表对为；若键值表对为；若键值表对为；若键值表对为(t,t)
12、(t,t)，则输出，则输出，则输出，则输出(t,NULL)(t,NULL)2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析基于基于Map-Reduce的基本运算的基本运算vv两个关系的差两个关系的差两个关系的差两个关系的差对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系对两个属性集相同的关系R R、S S中的所有元组进行中的所有元组进行中的所有元组进行中的所有元组进行“差差差差”操作。操作。操作。操作。Difference(R,S)=R-SDifference(R,S)=R-SMapM
13、ap函数：函数：函数：函数：将每个输入元组将每个输入元组将每个输入元组将每个输入元组t t转变为键值对转变为键值对转变为键值对转变为键值对(t,R)(t,R)或或或或(t,S)(t,S)。ReduceReduce函数：函数：函数：函数：输入到输入到输入到输入到ReduceReduce函数的键值表对有三种情函数的键值表对有三种情函数的键值表对有三种情函数的键值表对有三种情况，即况，即况，即况，即(t,R),(t,S),(t,R,S)(t,R),(t,S),(t,R,S)，如果键值表对为，如果键值表对为，如果键值表对为，如果键值表对为(t,R)(t,R)，则输，则输，则输，则输出出出出(t,t)(
14、t,t)；否则输出；否则输出；否则输出；否则输出(t,NULL)(t,NULL)2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析基于基于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的每对元组，若两个
15、元组关于子集的每对元组，若两个元组关于子集的每对元组，若两个元组关于子集的每对元组，若两个元组关于子集B B的所有属性值相的所有属性值相的所有属性值相的所有属性值相同，则生成一个新元组同，则生成一个新元组同，则生成一个新元组同，则生成一个新元组(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)，生成键值对，生成键值对，生成
16、键值对，生成键值对(b b,(S,(S,c c)。ReduceReduce函数：函数：函数：函数：对于相同的键对于相同的键对于相同的键对于相同的键b b，输入到对应的，输入到对应的，输入到对应的，输入到对应的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
17、b,c cn n),(),(a amm,b b,c c1 1),(),(a amm,b b,c cn n)连接运算可能导致元组数目大大增加连接运算可能导致元组数目大大增加连接运算可能导致元组数目大大增加连接运算可能导致元组数目大大增加。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析基于基于Map-Reduce的基本运算的基本运算vv矩阵乘积矩阵乘积矩阵乘积矩阵乘积假定矩阵假定矩阵假定矩阵假定矩阵M=M=mmij ij mm l l，N=N=n njkjk l l n n处理思路：处理思路：处理思路：处
18、理思路：vv将将将将MM、N N分别看成两个关系分别看成两个关系分别看成两个关系分别看成两个关系M(I,J,V)M(I,J,V)、N(J,K,W)N(J,K,W)，对应的元组分别为对应的元组分别为对应的元组分别为对应的元组分别为(i i,j j,mmij ij)和和和和(j j,k k,n njkjk)。vv将矩阵乘法转换为两个关系的自然连接与分组和聚将矩阵乘法转换为两个关系的自然连接与分组和聚将矩阵乘法转换为两个关系的自然连接与分组和聚将矩阵乘法转换为两个关系的自然连接与分组和聚合运算。合运算。合运算。合运算。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展
19、：电子商务新进展：大数据分析大数据分析大数据分析大数据分析基于基于Map-Reduce的基本运算的基本运算vv矩阵乘积（两步运算）矩阵乘积（两步运算）矩阵乘积（两步运算）矩阵乘积（两步运算）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任务的键
20、值任务的键值任务的键值任务的键值表对为表对为表对为表对为(j j,(M,1,(M,1,mm1 1j j),(M,),(M,mm,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
21、),),mmij ijn njkjk)Reduce2Reduce2函数函数函数函数：对于每个键：对于每个键：对于每个键：对于每个键(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
22、 2k k+mmil iln nlklk ，输出，输出，输出，输出(i i,k k),),v v)，v v是矩阵是矩阵是矩阵是矩阵P=MNP=MN的第的第的第的第i i行第行第行第行第k k列的元素值。列的元素值。列的元素值。列的元素值。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析基于基于Map-Reduce的基本运算的基本运算vv矩阵乘积（单步运算）矩阵乘积（单步运算）矩阵乘积（单步运算）矩阵乘积（单步运算）MapMap函数函数函数函数：将：将：将：将mmij ij转换为转换为转换为转换为(i i
23、,k k),(M,),(M,j j,mmij ij)，k k=1,=1,n n；将；将；将；将n njkjk转换为转换为转换为转换为(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值排序放在不同的值排序放在不
24、同的值排序放在不同的值排序放在不同的列表中，将两个列表的第列表中，将两个列表的第列表中，将两个列表的第列表中，将两个列表的第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 nlklk2022/11/120
25、22/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析集群计算的算法效率问题（自学参考）集群计算的算法效率问题（自学参考）集群计算的算法效率问题（自学参考）集群计算的算法效率问题（自学参考）vv集群计算的通信开销模型集群计算的通信开销模型集群计算的通信开销模型集群计算的通信开销模型集群计算的开销主要来自任务间数据的移动：通信开销，而不集群计算的开销主要来自任务间数据的移动：通信开销，而不集群计算的开销主要来自任务间数据的移动：通信开销，而不集群计算的开销主要来自任务间数据的移动：通信开销，而不是任务的执行时间。因为：算法中每个执行
26、任务都非常简单，是任务的执行时间。因为：算法中每个执行任务都非常简单，是任务的执行时间。因为：算法中每个执行任务都非常简单，是任务的执行时间。因为：算法中每个执行任务都非常简单，时间复杂度最多和输入规模成线性关系；数据传输速度相对于时间复杂度最多和输入规模成线性关系；数据传输速度相对于时间复杂度最多和输入规模成线性关系；数据传输速度相对于时间复杂度最多和输入规模成线性关系；数据传输速度相对于处理器执行指令的速度要慢。处理器执行指令的速度要慢。处理器执行指令的速度要慢。处理器执行指令的速度要慢。通信开销仅考虑所有输入的开销而不考虑输出的开销。因为：通信开销仅考虑所有输入的开销而不考虑输出的开销。
27、因为：通信开销仅考虑所有输入的开销而不考虑输出的开销。因为：通信开销仅考虑所有输入的开销而不考虑输出的开销。因为：任务任务任务任务T T的输出是另一个任务的输入，因此当度量接收任务的输的输出是另一个任务的输入，因此当度量接收任务的输的输出是另一个任务的输入，因此当度量接收任务的输的输出是另一个任务的输入，因此当度量接收任务的输入规模时，入规模时，入规模时，入规模时，T T的输出规模已被计算；一般而言，最终输出结果的输出规模已被计算；一般而言，最终输出结果的输出规模已被计算；一般而言，最终输出结果的输出规模已被计算；一般而言，最终输出结果相对于输入规模或中间数据相比，都要更小一些。相对于输入规模
28、或中间数据相比，都要更小一些。相对于输入规模或中间数据相比，都要更小一些。相对于输入规模或中间数据相比，都要更小一些。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析集群计算的算法效率问题集群计算的算法效率问题vv实耗通信开销实耗通信开销实耗通信开销实耗通信开销在工作流网络中，所有路径中的最大通信开销。路径通信在工作流网络中，所有路径中的最大通信开销。路径通信在工作流网络中，所有路径中的最大通信开销。路径通信在工作流网络中，所有路径中的最大通信开销。路径通信开销是指该路径上所有任务的通信开销之和。开销是
29、指该路径上所有任务的通信开销之和。开销是指该路径上所有任务的通信开销之和。开销是指该路径上所有任务的通信开销之和。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析集群计算的算法效率问题集群计算的算法效率问题vv多路连接（多路连接（多路连接（多路连接（n n路连接）路连接）路连接）路连接）选定自然连接中的关系的选定自然连接中的关系的选定自然连接中的关系的选定自然连接中的关系的连接属性连接属性连接属性连接属性 A A1 1,A A2 2,A An n，并将这些属，并将这些属，并将这些属，并将这些属性值哈希到
30、一定数量的桶中（桶编号与哈希值一一对应）；性值哈希到一定数量的桶中（桶编号与哈希值一一对应）；性值哈希到一定数量的桶中（桶编号与哈希值一一对应）；性值哈希到一定数量的桶中（桶编号与哈希值一一对应）；对每个连接属性对每个连接属性对每个连接属性对每个连接属性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任
31、务数；任务数；任务数；任务数；记桶编号向量为记桶编号向量为记桶编号向量为记桶编号向量为V=V=v v1 1,v vi i,v vn n，其中，其中，其中，其中v vi i是连接属性是连接属性是连接属性是连接属性a ai i的某个的某个的某个的某个桶编号，每一个向量桶编号，每一个向量桶编号，每一个向量桶编号，每一个向量V V标记一个标记一个标记一个标记一个ReduceReduce任务；任务；任务；任务；将每个关系的元组传递给相应的将每个关系的元组传递给相应的将每个关系的元组传递给相应的将每个关系的元组传递给相应的ReduceReduce任务。由于元组可能任务。由于元组可能任务。由于元组可能任务。
32、由于元组可能只有部分连接属性有值，因此哈希形成的向量只有部分连接属性有值，因此哈希形成的向量只有部分连接属性有值，因此哈希形成的向量只有部分连接属性有值，因此哈希形成的向量V V中存在某些分中存在某些分中存在某些分中存在某些分量未知，因此要将该元组传递给未知分量所有可能取值所对量未知，因此要将该元组传递给未知分量所有可能取值所对量未知，因此要将该元组传递给未知分量所有可能取值所对量未知，因此要将该元组传递给未知分量所有可能取值所对应的所有应的所有应的所有应的所有ReduceReduce任务。任务。任务。任务。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电
33、子商务新进展：大数据分析大数据分析大数据分析大数据分析集群计算的算法效率问题集群计算的算法效率问题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。连接策略一连接策略一连接策略一连接
34、策略一：采用两次：采用两次：采用两次：采用两次二路连接二路连接二路连接二路连接完成三个关系的连接完成三个关系的连接完成三个关系的连接完成三个关系的连接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连接策略二连接策略二连接策略二连接策略二：采用一次：采用一
35、次：采用一次：采用一次三路连接三路连接三路连接三路连接完成三个关系的连接完成三个关系的连接完成三个关系的连接完成三个关系的连接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
36、j，对应桶，对应桶，对应桶，对应桶(i i,j j)的的的的ReduceReduce任务就负责连接元组任务就负责连接元组任务就负责连接元组任务就负责连接元组R(R(u u,v v),S(),S(v v,w w)和和和和T(T(w w,x x)。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析集群计算的算法效率问题集群计算的算法效率问题vv三个关系的连接三个关系的连接三个关系的连接三个关系的连接计算连接策略二的通信开销计算连接策略二的通信开销计算连接策略二的通信开销计算连接策略二的通信开销MapMap的输
37、入总开销：的输入总开销：的输入总开销：的输入总开销：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，此时桶编号向量为，此时桶编号向量为，此时桶编号向量为，
38、此时桶编号向量为(h h(v v),NULL),NULL)，因此必，因此必，因此必，因此必须要将该元组传递给桶编号向量的第一个分量为须要将该元组传递给桶编号向量的第一个分量为须要将该元组传递给桶编号向量的第一个分量为须要将该元组传递给桶编号向量的第一个分量为h h(v v)所对应所对应所对应所对应的所有的所有的所有的所有ReduceReduce任务，共计任务，共计任务，共计任务，共计c c个。个。个。个。优化设计：优化设计：优化设计：优化设计：r r+s s+t t是常数，可优化的对象是是常数，可优化的对象是是常数，可优化的对象是是常数，可优化的对象是ReduceReduce的输入总开的输入总
39、开的输入总开的输入总开销，约束条件是销，约束条件是销，约束条件是销，约束条件是bcbc=k k，求解可得，求解可得，求解可得，求解可得b b=(=(krkr/t t)1/21/2时开销最小。时开销最小。时开销最小。时开销最小。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析集群计算的算法效率问题集群计算的算法效率问题vv三个关系的连接三个关系的连接三个关系的连接三个关系的连接比较连接策略一与连接策略二的通信开销优劣比较连接策略一与连接策略二的通信开销优劣比较连接策略一与连接策略二的通信开销优劣比较连接策
40、略一与连接策略二的通信开销优劣连接策略一的总开销为连接策略一的总开销为连接策略一的总开销为连接策略一的总开销为2 2r r+2+2s s+2+2prsprs+2+2t t 。连接策略二的总开销为连接策略二的总开销为连接策略二的总开销为连接策略二的总开销为r r+s s+t t+s s+2(+2(krtkrt)1/21/2假设假设假设假设R,S,TR,S,T都是同一个关系都是同一个关系都是同一个关系都是同一个关系R R，R R是是是是FacebookFacebook上的朋友关系，则上的朋友关系，则上的朋友关系，则上的朋友关系，则R R R R R R可找出每个用户所拥有的朋友的朋友的朋友的数目或
41、可找出每个用户所拥有的朋友的朋友的朋友的数目或可找出每个用户所拥有的朋友的朋友的朋友的数目或可找出每个用户所拥有的朋友的朋友的朋友的数目或具有最多的朋友的朋友的朋友的用户。具有最多的朋友的朋友的朋友的用户。具有最多的朋友的朋友的朋友的用户。具有最多的朋友的朋友的朋友的用户。连接策略一的总开销为连接策略一的总开销为连接策略一的总开销为连接策略一的总开销为6 6r r+2+2prpr2 2=6=6r r+2+2drdr（d d为每个用户的朋友数）为每个用户的朋友数）为每个用户的朋友数）为每个用户的朋友数）连接策略二的总开销为连接策略二的总开销为连接策略二的总开销为连接策略二的总开销为4 4r r+
42、2+2rkrk1/21/2若两种策略没有优劣之分，则有若两种策略没有优劣之分，则有若两种策略没有优劣之分，则有若两种策略没有优劣之分，则有d d+1=+1=k k1/21/2可见，可见，可见，可见，d d越大越不宜使用策略一，越大越不宜使用策略一，越大越不宜使用策略一，越大越不宜使用策略一，k k越大则越不宜使用策略二。越大则越不宜使用策略二。越大则越不宜使用策略二。越大则越不宜使用策略二。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析集群计算的算法效率问题集群计算的算法效率问题vv星型连接星型连接星
43、型连接星型连接R(A,B,C,X),S(A,D),T(B,E),U(C,F)R(A,B,C,X),S(A,D),T(B,E),U(C,F)多路连接的通信开销：多路连接的通信开销：多路连接的通信开销：多路连接的通信开销：T=r+s+t+u+r+sbc+tac+uab,T=r+s+t+u+r+sbc+tac+uab,其其其其中中中中abc=kabc=k。优化结果：优化结果：优化结果：优化结果：a=(ksa=(ks2 2/tu)/tu)1/31/3,b=(kt,b=(kt2 2/su)/su)1/31/3,c=(ku,c=(ku2 2/st)/st)1/31/3T=2r+s+t+u+3(kT=2r+
44、s+t+u+3(k2 2tus)tus)1/31/3若若若若s=t=us=t=u，则，则，则，则T=2r+3s(1+kT=2r+3s(1+k2/32/3)通常情况下，通常情况下，通常情况下，通常情况下，rsrs，因此适合使用多路连接策略。，因此适合使用多路连接策略。，因此适合使用多路连接策略。，因此适合使用多路连接策略。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析一、大数据时代一、大数据时代一、大数据时代一、大数据时代二、大数据分析基础二、大数据分析基础二、大数据分析基础二、大数据分析基础三、相似项
45、发现三、相似项发现三、相似项发现三、相似项发现四、流数据分析四、流数据分析四、流数据分析四、流数据分析提纲提纲一、大数据时代一、大数据时代一、大数据时代一、大数据时代二、大数据分析基础二、大数据分析基础二、大数据分析基础二、大数据分析基础三、相似项发现三、相似项发现三、相似项发现三、相似项发现四、流数据分析四、流数据分析四、流数据分析四、流数据分析2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析相似项发现的应用相似项发现的应用vv相似项发现（邻近搜索）相似项发现（邻近搜索）相似项发现（邻近搜索）相似项发
46、现（邻近搜索）是许多数据分析任务的基是许多数据分析任务的基是许多数据分析任务的基是许多数据分析任务的基础。在管理实践中也有着广泛的应用。例如，文档础。在管理实践中也有着广泛的应用。例如，文档础。在管理实践中也有着广泛的应用。例如，文档础。在管理实践中也有着广泛的应用。例如，文档相似性（抄袭、镜像、同源新闻稿）、图片相似性相似性（抄袭、镜像、同源新闻稿）、图片相似性相似性（抄袭、镜像、同源新闻稿）、图片相似性相似性（抄袭、镜像、同源新闻稿）、图片相似性（识别未知图片的身份）等等。（识别未知图片的身份）等等。（识别未知图片的身份）等等。（识别未知图片的身份）等等。vv下面我们以文档间的相似性发现加
47、以阐述。下面我们以文档间的相似性发现加以阐述。下面我们以文档间的相似性发现加以阐述。下面我们以文档间的相似性发现加以阐述。2022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析距离测度距离测度vv欧式距离欧式距离欧式距离欧式距离vvJaccardJaccard距离距离距离距离集合集合集合集合S S和和和和T T的的的的JaccardJaccard相似度定义为相似度定义为相似度定义为相似度定义为|ST|/|S|ST|/|S T|T|。vv余弦距离：余弦距离：余弦距离：余弦距离：两个向量夹角的余弦。两个向量夹角的
48、余弦。两个向量夹角的余弦。两个向量夹角的余弦。vv编辑距离：编辑距离：编辑距离：编辑距离：仅适用于字符串比较，两个字符串仅适用于字符串比较，两个字符串仅适用于字符串比较，两个字符串仅适用于字符串比较，两个字符串x,yx,y的距离等的距离等的距离等的距离等于将于将于将于将x x转换为转换为转换为转换为y y所需要的单字符插入及删除操作的最小数目。所需要的单字符插入及删除操作的最小数目。所需要的单字符插入及删除操作的最小数目。所需要的单字符插入及删除操作的最小数目。x=abcde,y=acfdeg,dx=abcde,y=acfdeg,dxyxy=3=3vv海明距离：海明距离：海明距离：海明距离：给
49、定一个向量空间，海明距离定义为两个向量中给定一个向量空间，海明距离定义为两个向量中给定一个向量空间，海明距离定义为两个向量中给定一个向量空间，海明距离定义为两个向量中不同分量的个数。不同分量的个数。不同分量的个数。不同分量的个数。x=10101,y=11011,dx=10101,y=11011,dxyxy=3=32022/11/12022/11/1电子商务新进展：电子商务新进展：电子商务新进展：电子商务新进展：大数据分析大数据分析大数据分析大数据分析文档的文档的Shinglingvvk-Shinglek-Shingle文档的文档的文档的文档的k-shinglek-shingle定义为其中任意长
50、度为定义为其中任意长度为定义为其中任意长度为定义为其中任意长度为k k的子串。的子串。的子串。的子串。D=abcdabd,k=2D=abcdabd,k=2，D D2-shingle2-shingle=ab,bc,cd,da,bd=ab,bc,cd,da,bdvvk k的选择的选择的选择的选择k k值的大小依赖于文档的典型长度以及典型的字符表大小。值的大小依赖于文档的典型长度以及典型的字符表大小。值的大小依赖于文档的典型长度以及典型的字符表大小。值的大小依赖于文档的典型长度以及典型的字符表大小。k k的大小应保证随机产生的的大小应保证随机产生的的大小应保证随机产生的的大小应保证随机产生的k-Sh