问一个大数据处理问题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一个大数据处理问题

问一个大数据处理问题# JobHunting - 待字闺中

f*42012-03-27 07:03

1 楼

最近在做一个 social network data analysis 的project
我自己想的算法效率很低，跪求大神指教。。
一个超大的txt文件（4G吧）(ID有10^6个，edge有10^8个)
全部是如下格式：
1 5
1 6
2 7
1 7
都是无序的。。这些ID
数字代表ID，我要做的是找出一个概率P（分数）：（A->C）/(A->B , B->C)，也就是
传递性，找到这个txt里三角形（传递关系）的概率
比如，如果这个txt里只有1、5、8、9、2、6.
1 5
5 8
5 9
1 8
2 6
1认识5,5认识8,1认识8,；1认识5,5认识9,但1不认识9。这个P就等于0.5。。（A->C）
/(A->B , B->C)（因为2、6无法和另一个ID产生关系，因此不要）我的target就是要求
出这个P。。
因为这些ID肯定都是long型，然后edge估计有个N*10^8,我不确定是否可以用内存（我
们服务器内存15Gb）。
目前，我是这么做的：把这个大txt，按ID的除余，分成0-19999两万个hash txt，然后
操作，这种做I/O明显是很大的，然后处理，又因为无序性，我每次很naive的线性找，
，然后就越来越慢了。。
问问大家，有没有好办法解决。
还有个问题就是说，有的数据集是undirected，有的是directed。按照要求，我得把所
有的directed转换成undirected，所以比较麻烦。

l*d2012-03-27 07:03

2 楼

借地问一下，多大的data算big data？
最近做一个project处理数据，总共有 100 TB的数据吧。但光数据量大不算big data吧
，还得考虑实时性什么的？

f*42012-03-27 07:03

3 楼

表示没人回应啊。。。。谁能给点意见

D*g2012-03-27 07:03

4 楼

可以这么做，如果你能access 某个map reduce的cluster的话：
Mapper:
map edges A->B to key=A&value=A|B and key=B&value=B|A
Combiner:
For each bucket corresponding to key A, collect all possible inlinks into A
and outlinks from A, generating all possbible combinations via A. Output:
key=NodeToA|NodeFromA&value=1
Reducer:
Reduce on key NodeToA|NodeFromA and aggregate count, you will get count of
all combinations of form A->*->B. If you don't care about aggregated count,
you canonly output all the unique A->*->B.
Put all direct edges in a bit map, indexed by each unique A->B. 10^8 / 8 /
10^6 = 12.5 MB
Then go through all A->*->B from the reducer output one by one (streaming in
), and look up in the bit map.

【在 f*******4 的大作中提到】

: 最近在做一个 social network data analysis 的project
: 我自己想的算法效率很低，跪求大神指教。。
: 一个超大的txt文件（4G吧）(ID有10^6个，edge有10^8个)
: 全部是如下格式：
: 1 5
: 1 6
: 2 7
: 1 7
: 都是无序的。。这些ID
: 数字代表ID，我要做的是找出一个概率P（分数）：（A->C）/(A->B , B->C)，也就是