Почему k и l для LSH используются для приблизительных ближайших соседей?

Question

Во всех объяснениях, связанных с локальным хешированием (то есть http://en.wikipedia.org/wiki/Locality-sensitive_hashing)

Они описывают, что генерируются k хеш-функций, но только х (l

Зачем вообще генерировать k, а не просто генерировать l?

Почему отдельные факторы к и л?

Я не понимаю это

Answer 1

Все хеш-функции фактически используются. Это имеет больше смысла, если вы помните, что, например, в разделе "Выборка битов для расстояния Хэмминга" отдельная хеш-функция может просто вернуть один бит. Фактически, другим примером хэш-функции LSH является рассмотрение случайно выбранной плоскости в некотором d-мерном месте и возвращение 0 или 1 в зависимости от того, с какой стороны плоскости находится хешируемая точка.

Чтобы обратиться к одной таблице, поскольку хеш-функции могут возвращать только один бит, вы оцениваете k хеш-функций и объединяете результат, чтобы получить, возможно, k-битный ключ. Теперь с l таблицами вам нужно l разных ключей, так что на самом деле вам нужно всего l * k хеш-функций.

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