TTJoin

Metadata

How improve Set Similarity Join based on prefix approach in distributed environment

paper

PPADJoin

• 作用：避免候选对重复
• 只对前缀的最后一个共同元素生成候选对

这个迁移到MapReduce会有点奇怪，除非只在一个节点上进行，PPJoin的这一步骤只是一层循环，但是这个是两层循环

负载均衡

• 贪心算法
• 负载预估
  • $NC=rSize\ast (rSize-1)/2$
  • $NC=rSize\ast sSize$

TTJoin

Two Token Filter

$DT(x)$ 表示元素存在于 x 但是不存在与 y中，可以理解为差集

TTJoin 这篇论文主要有三个点组成：

1. PPADJoin：消除重复候选对，只对前缀的最后一个共同元素生成候选对
2. 负载均衡：贪心算法
3. Two Token Filter：可以理解为前缀计算方式不一样的前缀过滤，由于需要两个集合的信息，所以不能用于候选对的生成，只能用于交集计算前的过程