科学网 › 标签 › TransLab

标签: TransLab

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

巴西利亚大学TransLab诚聘研究员（博士后）: 热度 2 Liweigang 2014-8-30 19:38; 巴西利亚大学计算机系 TransLab 实验室诚聘研究员（博士后），为期一年，月薪按巴西科学技术发展委员会（ CNPq ）的博士后待遇统一标准（2100美元左右），报销赴巴往返机票。研究领域为智能交通，主要方向是航空流量管理（ ATM ）和协同决策（ CDM ）。候选条件：计算机科学与工程、航空交通科学与工程、系统工程与运筹学、复杂系统等专业博士毕业，有在该领域科研教学经历的在职人员优先考虑。根据签证情况，希望入选者能于今年 10 月或 11 月到职。 TransLab 实验室目前有在读博士生5人，硕士生4人，博士后研究员1人。明年还会有若干类似职务，同时也接受对方资助访问学者，有兴趣加入团队者请在科学网给本博发内部留言或电邮： weigangbr@gmail.com ，十分感谢。; 个人分类: 巴西人文|4697 次阅读|8 个评论

微博de故事: 映射化简找朋友: 热度 4 Liweigang 2013-3-29 07:32; ( 李伟钢郑建亚 ) Google技术团队于 2004 年首次公开提出映射和化简 (MapReduce) 的信息处理和文档管理模型，而原 Yahoo 团队于 2005 年着手开发 Hadoop 开放系统，实现这种并行计算理念。这一梦之旅几经捻转，形成目前位于美加州的 Greenplum 商务智能和云数据专营企业，并与另一跨国大数据企业 EMC 有着千丝万缕的联系。 Greenplum 的专家们在介绍 Hadoop 系统时，习惯用 “ 你应相识的朋友 ” (People You May Know) 问题来解释大数据问题的计算工作量，在此基础上介绍映射和化简概念和 Hadoop 解决方案。假设某社交圈有 1 亿人参与，平均每人有 100 位朋友，要为所有参与者通过其朋友找到最可能认识的新友人 Top-X ，这里的 X 可以是 5 、 10 、等小于 100 的数。图 1 是 Milind B. 老师年初在里约大数据暑假班上演讲时，介绍解决此类问题的普通算法。图 1 Milind B. 介绍的解决 “ 你应相识的朋友 ” 问题的普通算法。执行该算法时，首先要遍历社交圈内的 1 亿人 (u) ，每个 TA(u) 有 100 个朋友 TA(x) ，如图1中的 connection(u), 每个 TA (x) 又有自己的 100 个朋友 TA(y) ，统计出现次数最多的 (u,y) ，最后向每个 TA(u) 推荐前三名 y1, y2, y3 ，这里 Top-X ， X=3 。对此算法进行分析，计算次数应为： 10 8 x100x100 = 10 12 。如果对每个友人进行 101 次随机访问，每次访问需要时间 1ms ，在每个友人的访问上需要 100ms 。假如使用一台电脑计算的话，对于一亿友人，这项工作的全部计算量大约需要 100 天。规范算法分析结果表明，该问题的计算复杂度为 O(n 3 ) 。对于现代人来说，是没这个耐心等上 100 天来参与这种社交活动。假若使用若干电脑并行计算如何？本文开头提到的开源软件框架 ApacheHadoop ，以 Google 的映射和化简模型为指导，实现对大数据的并行计算，查找有用的索引数据及其它“有价值”的信息，将此结果返回给相关用户。 Hadoop 支持 4000 个节点和 PB 级数据的数据密集型、分布式分析。巴西利亚大学 TransLab 团队学习使用映射和化简模型解决 “ 你应相识的朋友 ” 问题。表 1 列出使用映射和化简模型对 “ 你应相识的朋友 ” 问题的求解思路。表 1 映射和化简模型对 “ 你应相识的朋友 ” 问题的求解思路注意表 1为笔者的读书札记，仅用于示意映射和化简模型思路，只列出 u1 的少部分计算来说明算法，也就是说在 u 的用户集里，共需要进行 1 亿次这样的计算。结合图 1 和表 1 ，解决该问题的在 Hadoop 系统环境下的算法重写为： 1) 建立关系对过程。对于每个 u 建立 (x,y) 关系对： x ϵ u 且 x 是 u 的朋友，即存在 connextion(u,x); y ϵ u, 且 y 是 x 的朋友，即存在 connextion(x,y), 暂时 u 和 y 不是朋友，即不存在 connextion(u,y) 。这里 u 为社交圈全部参与者， x 为每个 u 的友人， y 为每个 x 的友人。按 “ 你应相识的朋友 ” 问题的基本条件， u 的数集为 1 亿，每个 x 和 y 的数集小于 100 。 2) 映射 (Map) 过程。整理建立的关系对，映射 (Map) 出可能通过 x 建立的 u 和 y 的关系， connection (u,y) ，的用户集列表 (y1,(x1,x2,x3,...)) ，如表 1 中与 u1 可能建立关系的有， y1,y2,y3,y4 等等。注意这里的限制条件是 y≠x ，即 y 不在 connextion(u,x) 集内。 3) 化简 (Reduce) 过程。算出 Connection(u,y) 用户集，每个 y 与 u 通过 x 建立关系用户列表内的数量 Count(u,y) ，如表 1 中的 y1 通过 x1,x2,x3 和 u1 认识 , 即渠道共有 3 个，等等。 4) 排行过程 (Rank) 。对 Connection (u,y) 用户集内 u 通过 x 认识 y 的用户数量 Count(u,y) 排行，列出前几名和 x 联系最多的 y ，这些人都可以介绍给 u 。如表 1 中的 Count(u,y) ≥ 2 ，即 Top-2 ，应向 u1 推荐的新朋友为 y1,y2,y3 。对于在线社交网络的微博平台，朋友推荐已经成为了一项不可缺少的功能和需求，对用户社交关系的后端分析，向用户推荐其可能认识的人，促进用户关系的建立，通过增加参与者之间的粘连性来增加用户对社交平台的忠诚度。研究 “ 你应相识的朋友 ” 问题的目的在于将其推广到微博平台，进行在线即时和更为复杂的信息查询。后续博文将继续介绍 TransLab 团队把映射和化简理念与粉丝模型相结合，配置 Hadoop 系统联机，从 Twitter 的 75GB 实际数据中查询 Top-X 的最新研究成果。敬请博友关注。; 个人分类: 社交网络|5302 次阅读|8 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: TransLab

相关帖子

相关日志

关闭安全验证