[图数据管理和挖掘]笔记 — 下

Managing Large Graph Data – Bin Shao

我个人认为这是一个非常难得的talk,从system的角度来剖析big graph的处理。
主要介绍的是MSRA在做的一个”distributed graph database and computing platform” — Trinity

Bin Shao老师首先提到了一个观点,就是所谓的big data的价值,在于数据之间的关系。
然后提到了现在多种多样的图数据的处理方式:

image

介绍了目前和大数据/大图数据处理相关的一些系统:

image

这些系统要么并不是专门针对图数据而设计的,要么只能够满足部分operation的需求,或者只能够支持中等规模的数据。

也提到了图数据处理的两个特性:
Poor locality (random access is required)
Data or graph structure driven

Trinity的一些设计choice:
类似google的做法,scale-out优于scale-up;
数据全部放在memory中;

它的简单架构如下图所示:

image

在最底层是一个memory cloud,有一些特殊的设计和数据结构用于存储图数据,之上会提供一些操作图数据的通用接口,再往上就是一些Programming Model。它的一个好处是并不仅仅局限于某个Programming Model(比如MapReduce),而是期望支持多种Model,以应对不同的算法。

此外,还比较评价了现在其它的一些系统:
MapReduce
  “is not a native graph model”
Pregel
    google的Pregel只适合vertex-based computation model. 仅有少量算法适用。
Pegasus
  Pegasus我之前也了解过一些。它是基于Hadoop之上的。所以它本质上还是用MapReduce来解决图的算法问题。基本的思路就是将图表示成矩阵,图的算法变成矩阵上的操作,然后用MapReduce实现。它的问题也是很多算法没法用。而且有些算法需要迭代操作,意味着要重复执行多次MapReduce,速度很慢。

很遗憾的是,Trinity并没有开源。而且按照MS的风格,未来也不太可能。

Querying Big Social Data – Wenfei Fan

第二天都是keynote speaker的talk,可惜三位大师所讲内容都太前沿了,且个个语速惊人。因为我不太了解对应的领域,基本上就听了个囫囵吞枣。

Fan老师是一个特激情的演讲人。他主要讲的是Graph Pattern Matching in Social Network。包括:
1) subgraph isomorphism
2) graph simulation

特别是提到了大数据情况下常用的一些手段:
1) approximate(计算近似值,而不是精确计算)
2) incremental graph
整个大图的计算很费时间,当计算完整个图之后,后续都只需要计算增量变化的部分
3) query preserving graph compression(希望没记错..)
意思是,给graph做降维,或者将大图压缩成小图
4) distribution
将图切割,做分布式计算
5) answering graph queries using views
这个view的概念类似于数据库中的view
将graph转换成view,将pattern转换成view空间上的pattern
6) top-K matching
不需要全部结果,只需要top-k的结果
可以在计算过程中做剪枝

还提到一个很有意思的观点:
目前SSD最快的读取是6GB/s,按照这个速度,扫描1PB的数据需要1.9 days。
所以在大数据条件下,传统的计算复杂度理论可能不适用。
“O(n) time is already beyond reach on big data.
Polynomial time queries become intractable in big data”

Some Research Issues in Online Social Network – Jeffrey Xu Yu

Yu老师提到了他现在关注的4个方向:
1) Computing bias and prestige in trust networks
2) Influenceability estimation in social network
3) diversified ranking
4) diversifying top-k result

他分别介绍了4个方向的进展,但说实话,我听懂的不多。

谈到Influenceability estimation,提到现在的model都是采用Independent cascade model,即每个node有一个独立概率影响到其它的邻居,这样构成了一个概率网络。

Privacy Preserved Graph Data Publishing – Lei Chen

Chen老师介绍的内容主要是,当一个有social network数据的组织/公司,打算对外发布社交网络数据的时候,应该对数据采取哪些措施,使得数据仍然能够有价值被挖掘,而又不泄露用户的隐私。

有非常多(在我看来)tricky的方法,比如增删一些节点或者边,比如做一些小图的clustering。坦率的说,这事在我看来有些机关枪打蚊子,小题大做。但是它引出了一个非常有意思的领域,就是社交网络的攻防。我觉着这上面还是有很多可做的东西。

会议的最后,还有一个Panel Discussion。haixun老师提了几个启发式的问题:
1) How to generate a social network ?
2) How to build a system for big graph ?
3) Can distributed computing solve the graph problem ?
4) killer app for facebook

我印象比较深的是有位老师(好像是Lei Chen)提到,他觉着众包服务会是将来的一个killer app。

个人的一些感想

未来的big graph system一定会是一个基于内存的分布式处理系统:
1. graph数据是能够被加载到内存当中的;
2. graph的处理需要大量的jump,只有放在内存中性能才能够好;
3. graph的很多处理都需要多次迭代操作,放在内存中也能节省不少的IO;
4. 放入内存并不意味着万事大吉,内存中的设计细节仍然会有很多讲究;
另外,也许会诞生一个或几个新的Programming Model。

big graph的处理目前仍然是一个不算成熟的领域,还有很多复杂的操作和计算现在没有太好的办法。所以前景还是很光明的。

Advertisements
相册 | 此条目发表在Large Scale, Social Network分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s