Mapreduce Расчет расстояния в Hadoop - PullRequest
Новая
       39

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

3 голосов
/ 01 августа 2010

Есть ли реализация расчета расстояния с использованием карты / сокращения hadoop.Я пытаюсь вычислить расстояние между заданным набором точек.

Ищу любые ресурсы.

Редактировать

Это очень разумное решение,Я попробовал кое-что как первый алгоритм, и я получил почти то, что искал.Я не беспокоюсь об оптимизации программы в данный момент, но моя проблема заключалась в том, что функция dist (X, Y) не работала.Когда я получил все точки на редукторе, я не смог пройти все точки на итераторе и вычислить расстояние.Кто-то на stackoverflow.com сказал мне, что Iterator на hadoop отличается от обычного 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]))

Ответы [ 2 ]

1 голос
/ 05 октября 2010

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

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 расстояний.Вопрос в том, оптимизирует ли это улей так, как вы можете аккуратно заниматься программированием в 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 перешел к редуктору, отсортированному в некотором порядке, например по 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 для настройки перфорации.

0 голосов
/ 10 августа 2010

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

...