分布式高维相似连接操作算法设计
(Distributed Similarity Join for High Dimensional Data)
丁方伟 21017036
2010 年 12 月 22 日
1 问题定义
输入：存放在站点 1 上的数据集 A 和站点 2 上的数据集 B。
输出：数据集 A 和 B 的距离链接。
算法目标：对 A 中每个点，在 B 中找到所有与其距离小于某阈值的点集。
相关假设：数据集 A 和 B 的数据点数分别为 M 和 N。集合 C 和 D 的元素数
分别为 P 和 Q。 每个数据点的维数为 p (>100)，数据点 x 可表示为 x(x
1
,x
2
,
…,x
p
)。阈值为 T。
2 算法描述
算法步骤和描述如下：
(1) 取出站点 1 上的数据集 A 中的每个数据点的前 维数的数据，发送
给站点 2。
(2) 取出站点 2 上的数据集 B 中的每个数据点的后 维数的数据，发送
给站点 1。
(3) 在站点 2 上：计算 A 中每个点 x 和 B 中的每个点 y 的前 维数的欧式
距离 。去掉那些大于等于阈值 T 的距离，余下的距离
组成集合 C。
(4) 在站点 1 上：计算 A 中每个点 x 和 B 中的每个点 y 的后 维数的欧式
距离 。去掉那些大于等于阈值 T 的距离，余下的距
评论1