hadoop中的mapreduce距离计算
是否有使用hadoop map / reduce的距离计算实现。 我想计算一组给定点之间的距离。
寻找任何资源。
编辑
这是一个非常智能的解决方案。 我尝试了一些与第一种算法相似的方法，而且我几乎得到了我想要的东西。 我现在并不关心优化程序，但我的问题是dist（X，Y）函数无效。 当我得到减速器上的所有点时，我无法通过迭代器上的所有点并计算距离。 stackoverflow.com上的某个人告诉我，hadoop上的Iterator与普通的JAVA Iterator不同，我不确定。 但是，如果我能找到一种简单的方法来通过我的dist（）函数上的迭代器，我可以使用你的第二个算法进行优化。
//This is your code and I am refering to that code too, just to make my point clear. map(x,y) { for i in 1:N #number of points emit(i, (x,y)) //i did exactly like this reduce (i, X) p1 = X[i] for j in i:N // here is my problem, I can't get the values from the Iterator. emit(dist(X[i], X[j])) 你需要在该数据集上进行自联接。 在蜂巢中看起来像或多或少
select dist(P1.x,P1.y,P2.x, P2.y) from points P1 join points P2 on (True) where P1.x < P2.x or (P1.x = P2.x and P1.y < P2.y)
函数dist需要使用其他配置单元函数实现，或者用Java编写并添加为UDF。 此外，我不确定True常数，但你可以写0 = 0到相同的效果。 where子句是为了避免计算相同的距离两次或0距离。 问题是：hive会优化这种方式，你可以在hadoop中仔细编程吗？ 我不确定。 这是hadoop中的草图
map(x,y) { for i in 1:N #number of points emit(i, (x,y)) reduce (i, X) p1 = X[i] for j in i:N emit(dist(X[i], X[j]))
要使其工作，您需要X以某种顺序排序到reducer，例如x，然后使用辅助排序键（不影响分组）。 这样每个reducer都会获得所有点的副本，并在您尝试生成的距离矩阵的列上工作。 内存要求很少。 您可以通过重新组织计算来交换一些内存通信，以便每个缩减器计算最终矩阵的方形子矩阵，只知道两个点的子集并计算所有这些子集之间的距离。 要实现这一点，你需要明确你的点的顺序，比如你要存储i，x，y
map(i,x,y) { for j in 1:N/k #k is size of submatrix emit((i/k, j), ("row", (x,y))) emit((j, i/k), ("col", (x,y))) reduce ((a,b), Z) split Z in rows X and cols Y for x in X for y in Y emit(dist(x,y))
在这种情况下，您可以看到地图阶段仅发出2 * N * N / k个点，而之前的算法发出N ^ 2。 这里我们有（N / k）^ 2减少器与另一个减去N. 每个reducer必须在内存中保存k值（使用二级密钥技术让所有行在所有列之前到达reducer），而之前只有2。 因此，您会看到存在权衡，对于第二种算法，您可以使用参数k进行性能调整。
这个问题听起来不太适合map-reduce，因为你真的不能把它分成碎片并独立计算每一块。 如果你有一个单独的程序可以生成点的完整图形作为列表（x1，y1，x2，y2），那么你可以做一个简单的地图来获得距离。