主权项 |
一种基于mapreduce框架下的大规模稀疏矩阵乘法运算的方法,即求矩阵C,使得C=A*B,其中A的存储格式为(i,k,A<sub>ik</sub>),B的存储格式为(k,j,B<sub>kj</sub>),C的存储格式为(i,j,C<sub>ij</sub>),其中1≤i≤m, 1≤k≤n, 1≤j≤l,所述算法由2个mapreduce的job完成,包括如下步骤:步骤1:第一个job,该job需要两个mapper和1个reduce完成:(i) 生成mapper1:对矩阵A的每一个元素(i,k,A<sub>ik</sub>),输出一个key‑value对, mapper1的key和value分别为key‑value对的形式,其中,key为(k, A’),value为(i, A<sub>ik</sub>), A’为常数,表示属于矩阵A;(ii) 生成mapper2:对矩阵B的每一个元素(k,j,B<sub>kj</sub>),输出一个key‑value对, mapper2的key和value分别为key‑value对的形式,其中,key为(k,B”),value为(j, B<sub>kj</sub>) , B”为常数,表示属于矩阵B;(iii) partitioner : 将mapper1和mapper2输出的key‑value对按照key中的key‑value对中的key 的hash进行partition;(iv) groupingComprator: 将mapper1和mapper2输出的key‑value对按照key中的key‑value对中的key进行分组;(v) reduce: 对reduce的每一个分组,声明两个hashmap,记为hashmapA和hashmapB,对mapper1和mapper2中的每一个value,将所述value所采用的key‑value对放到hashmap,如果mapper1和mapper2中的所述value对应的key的value是A’,则将mapper1和mapper2中的所述value放到hashmapA中, 如果mapper1和mapper2中的所述value对应key的value是B”,则将其放到hashmapB中,由于在mapper1和mapper2中,所述value采用的是key‑value对的形式,则,所述hashmapA和hashmapB中的key为所述mapper的value的key,value为所述mapper的value的value;(vi)对hashmapA的每一个元素(keyA,valueA)和hashmapB的每一个元素(keyB,valueB)做运算,输出一个key‑value对,其中key为(keyA,keyB),value为valueA*valueB;步骤2:第二个job,该job由一个mapper和一个reduce完成,(i)mapper:对每一个元素之间输出原样输出(ii)reducer: 对key相同的元素进行分组,对值进行累加。 |