这是一个创建于 2316 天前的主题，其中的信息可能已经有所发展或是发生改变。
现有一些社交数据如下，
id from to
1 A B
2 A C
3 B A
4 C A
去重复后如下，
id from to
1 A B
2 A C
尝试的解决方案:
1、采用 bloomfilter 去重，由于 bloomfilter 本身算法问题，会丢失一些数据；
2、使用数据库查询然后写入到新表，速度有点慢。
3、使用 BerkeleyDB ？
4、使用 hadoop 或者 spark 解决,网上找到的方式几乎都是使用 group by 或者 distinct 但这并不适合我这个场景，如何解决呢？
头大。。。新手上路。。。
21 条回复 • 2018-07-31 11:54:51 +08:00
 |
1
zjxzhqq 2018-07-30 10:29:25 +08:00 via Android
很简单吧你把后两个字段排下序，然后根据这两个字段去重就可以了
|
 |
2
bsidb 2018-07-30 10:37:34 +08:00  1
这个就是转无向图的过程吧？
使用 Spark SQL API （ Spark RDD API 的 distinct 有严重的 GC 问题，不推荐）。 1. 将数据导入 Spark SQL 的表 2. 将 from 和 to 规则化（确保 from 的顶点 ID 小于 to 的） 3. 使用 Spark SQL API 进行 distinct 去重 |
 |
3
liprais 2018-07-30 10:50:21 +08:00 via iPhone
from 和 to 拼起来再 group by 就行了
|
 |
4
omygod 2018-07-30 11:00:39 +08:00
|
 |
5
xwander 2018-07-30 11:08:49 +08:00
先用 bloomfilter 判断是否有这段数据，如果有，再进一步使用 md5 判断。
有时间深入，可以了解下，Online Deduplication。 https://ieeexplore.ieee.org/document/7996543/ |
 |
6
zhuanggu 2018-07-30 11:10:47 +08:00
select id, `from`, `to` from( select id, `from`, `to`,row_number() over(partition by `from`,`to` order by id) rk) t where rk=1
|
 |
7
luckychenhaha 2018-07-30 11:12:19 +08:00
from 和 to 做字母排序，然后 hadoop 的 kv 自动匹配就可以了
|
 |
10
pwrliang 2018-07-30 11:48:34 +08:00 via Android
尝试实现下 cuckoo hash ？ https://en.m.wikipedia.org/wiki/Cuckoo_hashing
|
 |
11
laxenade 2018-07-30 11:53:42 +08:00
map 阶段：让 from < to
reduce 阶段：做 distinct 这样不行吗 |
 |
12
owenliang 2018-07-30 12:18:40 +08:00
难道不是构造一个 from_to 的 key，直接走 spark 或者 mr 去重就可以了吗。。
|
|
13
bsidb 2018-07-30 12:24:48 +08:00 via Android
@BIGUFO RDD 的 distinct 中每一条记录会创建一个对象，10 亿条记录会创建 10 亿个对象，即使集群多机计算，中间生成这么多对象 GC 压力也很大。SQL API 有钨丝计划优化，gc 问题会小很多。
|
|
14
bsidb 2018-07-30 12:26:33 +08:00 via Android
@engineer9 如果 from > to 则 map 一个（ id, to, from ）否则 map(id, from, to)
|
 |
16
dangluren 2018-07-30 17:21:39 +08:00
为什么 spark,hadoop 不适合你们的场景。
是考虑到 A B B A 无法判断相同？ 这种情况可以将每一条看成一个对象，重写 equals 方法啊。 又或者是考虑到资源不足？ |
|
17
dangluren 2018-07-30 17:28:54 +08:00
bloomfilter 其实也是可以的， 首先第一步：
不在里面： 肯定不在里面。 在里面： 可能不在里面。 这时候，我们并不是把这条数据去掉，而是将这条数据给记录下来，敢肯定的是，由于布隆过滤器的概率，这种数据肯定很少很少。 下一步： 将这 10 亿条数据再遍历一次，看看上面保存的数据到底有没有重复。 这种需求简单的很呐 |
|
18
dangluren 2018-07-30 17:30:41 +08:00
布隆过滤器的原理和使用参考我之前写的：
https://blog.csdn.net/t1dmzks/article/details/79212179 |
 |
19
diginWu 2018-07-30 17:41:53 +08:00
百八十 M 的东西内存里面算不就行了么？
|
|
20
diginWu 2018-07-30 17:45:43 +08:00
不好意思少算了一个数量级。
|
 |
21
kavana 2018-07-31 11:54:51 +08:00
hadoop or spark 大数据去重，收藏待用
|
Select Language