Статьи

Хеширование с учетом местоположения в MapReduce

Август 17, 2018

Скажем, есть N элементов (с N в миллиардах), и мы хотим найти все те, которые похожи друг на друга, сходство определяется функцией расстояния. Цель состоит в том, чтобы вывести матрицу подобия — обратите внимание, что эта матрица очень разрежена и большинство ячеек бесконечно.

Один наивный способ сделать это — вычислить сходство каждой возможной пары элементов — отсюда огромная проблема O (N ^ 2). Можем ли мы уменьшить порядок сложности?

Хеширование с учетом местоположения

Первая идея: найти функцию хеширования таким образом, чтобы аналогичные элементы (скажем, расстояние было меньше предварительно определенного порога) будут хэшироваться в один и тот же сегмент.

Скажем, если мы выберем хеш-функцию так, чтобы вероятность (H (a) == H (b)) была пропорциональна сходству между a и b. И затем мы выполняем детальное сравнение только тех предметов, которые попадают в одну корзину.

Вот некоторый R-код, который отображает взаимосвязь между сходством и возможностью выполнения детального сравнения:

x <- seq(0, 1, 0.01)
y <- x
plot(x, y, xlab="similarity", ylab="prob of detail compare")


Допустим, мы заинтересованы в сравнении всех пар предметов, чье сходство выше 0,3, у нас есть проблема, потому что у нас есть вероятность пропустить их 0,7 = 1 — 0,3 (так как они не попадают в одно ведро). Мы хотим, чтобы механизм был очень избирательным; вероятность выполнения детального сравнения должна быть близка к единице, если сходство выше 0,3, и близко к нулю, если сходство меньше 0,3.

Вторая идея: давайте использовать 100 хеш-функций и 2 элемента, которые имеют 30 или более совпадений таких хеш-функций, будут выбраны для детального сравнения.

Вот некоторый R-код, который отображает взаимосвязь между сходством и возможностью выполнения детального сравнения.

# Probability of having more than "threshold" matches out 
# of "no_of_hash" with a range of varying similarities

prob_select <- function(threshold, similarity, no_of_hash) {
  sum <- rep(0, length(similarity))
  for (k in 0:floor(no_of_hash * threshold)) {
    sum <- sum + dbinom(k, no_of_hash, similarity)
  }
  return(1 - sum)
}

x <- seq(0, 1, 0.01)
y <- prob_select(0.3, x, 100)
plot(x, y, main="black: 100 hashes, Red: 1000 hashes", 
xlab="similarity", ylab="prob of detail compare")
lines(x, y)
y <- prob_select(0.3, x, 1000)
lines(x, y, col="red")

На этот раз график выглядит намного лучше, вероятность выбора для сравнения деталей резко возрастает с нуля до единицы, когда сходство пересекает 0,3

Чтобы сравнить элементы, которые похожи, мы сначала вычисляем 100 хешей (на основе 100 различных хеш-функций) для каждого элемента и выводим все 30 комбинаций в качестве ключа. Затем мы выполняем парное сравнение для всех элементов, имеющих одинаковый ключ.

Но посмотрите на комбинацию 30 из 100, она равна 100! / (30! * 70!) = 2,93 * 10 ^ 25, что практически невозможно. Даже график хороший, мы не можем использовать этот механизм на практике.

Третья идея: давайте используем 100 хеш-функций и разбиваем их на b групп по r в каждой (то есть: b * r = 100). Далее, давайте предположим, что b = 20 и r = 5. Другими словами, у нас есть 20 групп, и у Group1 есть hash1 до hash5, у Group2 есть hash6 до hash10 … и т. Д. Теперь мы называем itemA group1, совпадает с group1 itemB, если все их hash1 to hash5 равны друг другу. Теперь мы выполним подробное сравнение itemA и itemB, если какие-либо группы равны друг другу.

Вероятность быть выбранным 1 — (1-s ^ r) ^ b

Идея может быть визуализирована следующим образом

Обратите внимание, что в этой модели поиск r и b на основе s является методом проб и ошибок. Здесь мы пытаемся 20 на 5, 33 на 3, 10 на 10.

prob_select2 <- function(similarity, row_per_grp, no_of_grp) {
  return(1 - (1 - similarity^row_per_grp)^no_of_grp)
}

x <- seq(0, 1, 0.01)
y <- prob_select2(x, 5, 20)

plot(x, y, 
main="black:20 by 5, red:10 by 10, blue:33 by 3", 
xlab="similarity", ylab="prob of detail compare")

lines(x, y)
y <- prob_select2(x, 10, 10)
lines(x, y, col="red")
y <- prob_select2(x, 3, 33)
lines(x, y, col="blue")

Из графика видно, что синяя кривая лучше подходит для выбора сходства на уровне 0,3. Итак, давайте используем 33 на 3.

Чтобы выполнить детальное сравнение, мы можем использовать параллельную реализацию Map / Reduce.

Карта Сократить Осуществление

Здесь у нас есть два раунда Map / Reduce. В первом раунде функция map вычисляет все значения groupKeys для каждого элемента и генерирует groupKey вместе с элементом. Все элементы, у которых есть совпадения groupKey, попадут на один и тот же редуктор, который создает все возможные пары элементов (это кандидаты для парного сравнения).

Однако мы не хотим выполнять детальное сравнение в первом раунде, так как может быть много дубликатов для пар элементов, которые соответствуют более чем одной группе. Поэтому мы хотим выполнить еще один раунд Map / Reduction, чтобы удалить дубликаты.

Первый раунд проходит следующим образом …

После этого второй тур проходит следующим образом …

Комбинируя хеширование с учетом местоположения и Map / Reduce, мы можем эффективно выполнить крупномасштабное вычисление подобия.

 

40
Share: