每周学点大数据 | No.43 相似连接的可扩展性

No.43期

相似连接的可扩展性

小可:那么具体是怎么做的呢?

Mr. 王:我们先来看看求单元函数值是如何在 MapReduce 上实现的吧。

图中有三个集合 M1、 M2、 M3。键值为集合名称,值为每种元素的个数。在经过 Mapper的过程中, key 依然不变,但 value 部分我们保存两种 value :第一种用 0 标记,用来统计这个Mapper 收到的来自某一个集合的元组个数。

比如第一个 Mapper 收到了 M1 两个、 M2 两个;第二种我们用 1 以上的数来做标志位,表示这个 Mapper 收到了多少种来自这一集合的元素,比如第一个 Mapper 收到了来自 M1 的一种元素(标志位记为 1),其后面的部分记录各种元素的数量(<a,2>),和之前一样。

这里包含了一个思想,就是合理设计 value 值的结构,让 value值可以有多种不同的类型,比如这里设计了一个标志位来区分不同类型的 value 值。

同时这个value 里面有一个次级键的思想,value 里面的第一个值就是一条记录的次级键,在洗牌的过程中,可以实现利用次级键进行二次排序。

接下来数据经过洗牌之后被送到了 Reducer 中,从图中可以看出, Reducer 对数据进行了整理,生成的键值对的第一个 value 属性就是每一个集合的计数,也就是单元函数值。

小可:那求合取函数值又是怎么做的呢?我觉得如果 HDFS 上可以存储前面的输出结果的话,那么求合取函数值时是不是可以对这个结果加以利用呢?

Mr. 王:对。之所以我们在求单元函数值的过程中保留着对各种元素的计数,就是要进一步应用这个结果。

在求合取函数值的过程中, Mapper 做的一件事情叫作交换键值。我们将元素反提出来,将集合名称放进 value 中,变成一种有利于做合取的形态。

接下来在 Reducer 中,每一个 Reducer整理一种元素,比如某一个 Reducer 整理 a,这个 Reducer 将其整理成key=<M1,M3,5,4>、value=<2,1> 这种形式。

它的意思是, M1 和 M3 中分别含有 5 个和 4 个元素,其中 a 的个数分别为 2 和 1。

小可:我想做到这一步,合取函数值已经求出来了吧?

Mr. 王:没错,做到这里,合取函数值已经可以通过这一步的结果知道了。我们进一步做下去,再用一轮 MapReduce 将相似度彻底求出来。

Mr. 王:下一轮的这个 Mapper,会把中间结果发送出去,而 Reducer 会收到这些结果,我们就能求出其根据三种不同计算方法的相似度。

这里有一点点小思考,我们可以对求单元函数值部分做出改进,让它的求解变得更快速一些。

首先还是要对表进行随机分割,但是在 Mapper 运行之后,我们尝试对 Mapper 生成的数据进行压缩。我们在 Mapper 中只统计元素的个数,而忽略它们具体是什么;在 Reducer 里面做一个求和就可以了。

小可:这样在求单元函数值时的确可以更加节省资源,但是后面的合取求解怎么做呢?

Mr. 王:当我们已经求出了每个集合中有多少个元素这张表保存在每一个 Mapper 中。

只要每个 Mapper 中都有这样的一个表,求解相应的占比也就容易得多了。但是对于 Mapper 来说,这样的表也是对内存的一种消耗。好在这个表不会太大,消耗的内存也不会太多。

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2017-06-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

深入理解树状数组

树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之...

27570
来自专栏程序生活

Python json 模块dumps、dump、loads、load的使用

本文主要讲下json.dumps和json.dump、json.loads和json.load的区别,因为经常需要加载json文件,读取数据,傻傻分不清...

9210
来自专栏小樱的经验随笔

详解斯坦纳点及斯坦纳树及模版归纳总结

①什么是斯坦纳点?   假设原来已经给定了个点,库朗等指出需要引进的点数至多为,此种点称为斯坦纳点。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成...

92860
来自专栏GIS讲堂

Geohash之范围搜索

很多时候,我们都会遇到这样的需求:查找某个点周边多少距离的点。从本质来说,是一个缓冲区分析+空间查找,本文结合Geohash来实现类似的功能。

27340
来自专栏灯塔大数据

每周学点大数据 | No.30前序计数

No.30期 前序计数 Mr. 王:我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍...

34770
来自专栏吴伟祥

UML 类图介绍 转

Unified Modeling Language (UML)又称统一建模语言或标准建模语言,是始于1997年一个OMG标准,它是一个支持模型化和软件系统开发的...

9010
来自专栏Duncan's Blog

Hive SQL 学习

example: 一个班有学生id,成绩,班级,现在将学生根据班级按照成绩排名。(partition by)

42820
来自专栏desperate633

LintCode 哈希函数题目代码

在数据结构中,哈希函数是用来将一个字符串(或任何其他类型)转化为小于哈希表大小且大于等于零的整数。一个好的哈希函数可以尽可能少地产生冲突。一种广泛使用的哈希函数...

11040
来自专栏机器学习入门

POJ 刷题系列:2965. The Pilots Brothers' refrigerator

POJ 刷题系列:2965. The Pilots Brothers’ refrigerator 传送门:POJ 2965. The Pilots Brothe...

20760
来自专栏mathor

奇数魔方阵(奇数幻方)

15930

扫码关注云+社区

领取腾讯云代金券