阿里巴巴面试过程中碰到的一道大数据题,问问大家有啥好方法?


80万个向量,每个向量500维,计算cos距离,用map reduce 的方法,尽可能减少计算,求输出每一个向量距离它最近的top100个向量?
已邀请:

sd1527907 - 80后IT男

赞同来自: ZuckML


举个例子

假如我们把向量数量变成6个 1,2,3,4,5,6 那么如果要22计算cos,需要比较 C6 2 = 15次。
如果我们使用冗余存储的方式来做 3个为1组,那么 需要的组数量为 4+3+2+1 = 10 组 ((6-3+1)~1 的等差数列)
而每组内数据比较次数为 C3 2 = 3次

而这种思路正好符合map思路。 80W向量使用1个map来处理 先不说能不能放下,也要比较 80W*80W次

而如果我们将其冗余存储,比如使用70W为1组 需要 (80W-70W+1)~1 个组,而每组内只需比较 70W*70W次。

组分的越多,组内比较次数越少。

然后在每个map内,输出key为向量ID,value为比较向量ID和cos距离

combine里面进行一轮比较,取每个向量的top100 输出给reduce

reduce里面再比较,最终输出结果。

PS:由于条件太少,只能用这种硬办法来做,每个向量维度都没有用,如果能找到一些方式,类似minhash那样。
2个向量维度的汉明距离可以一定程度代表其cos距离的话,那样就比较好做的。
实际工作中,一般都不会像上面那么硬来,都是用类似minhash的方式过滤一轮,然后再精准计算。

要回复问题请先登录注册

收藏七月在线,一起向大牛进阶

ctrl+D或command+D可以快速收藏哦~