Расчет расстояния mapreduce в Hadoop

вам нужно выполнить самостоятельное соединение с этим набором данных. В улье это выглядело бы более или менее

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? Я не уверена. Это скетч в хаупе

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 добрался до редуктора, отсортированного в некотором порядке, например, по x, а затем по y, используя вторичные ключи сортировки (которые не влияют на группировку). Таким образом, каждый редуктор получает копию всех точек и работает со столбцом матрицы расстояний, которую вы пытаетесь сгенерировать. Требования к памяти минимальны. Вы можете обменять часть связи на память, реорганизовав вычисления таким образом, чтобы каждый редюсер вычислял квадратную подматрицу конечной матрицы, зная только два подмножества точек и вычисляя расстояния между ними. Для этого вам нужно явно указать порядок ваших точек, скажем, вы храните 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 для другого. Каждый редуктор должен хранить k значений в памяти (используя технику вторичного ключа, чтобы все строки попадали в редуктор раньше всех столбцов), а не только 2 раньше. Итак, вы видите, что есть компромиссы, и для второго алгоритма вы можете использовать параметр k для настройки производительности.

Эта проблема не кажется подходящей для уменьшения карты, поскольку вы не можете разбить ее на части и вычислить каждую часть независимо. Если бы у вас была отдельная программа, которая генерирует полный график ваших точек в виде списка (x1, y1, x2, y2), вы могли бы сделать простую карту, чтобы получить расстояние.