Хеширование локальной чувствительности используется для размещения sh похожих входных элементов в одни и те же «корзины» с высокой вероятностью. Я не уверен в определении L SH в вашем исходном вопросе, я никогда не видел, чтобы он определялся таким образом. В частности, утверждение «с высокой вероятностью» очень важно для понимания того, почему L SH полезен.
На высоком уровне L SH является противоположностью типичных хеш-функций. Используя типичные функции хеширования, мы хотим гарантировать минимальное количество конфликтов ведра, даже / особенно для аналогичных элементов ввода. Это свойство полезно для создания таблиц ha sh, обеспечивающих эффективные операции.
В L SH цель состоит в том, чтобы создать хеш-функцию, такую, что две точки p1 и p2 в d мерное пространство с высокой вероятностью попадает в одну корзину, когда p1 и p2 являются «близкими», где близость определяется заданным значением c или расстоянием (обычно L1 или L2). Аналогично, две точки p1 и p2, которые не являются близкими, должны попасть в разные сегменты с высокой вероятностью.
Чтобы дать типичный пример семейства функций, которые используются для создания L SH, функция
f(x) = 1 if dot(x,r) > 0 else 0
с r, взятым из d нормального распределения размеров. Отрисовка m таких функций даст m бит ha sh. Использование n таких m битовых хэшей даст базовый c L SH, который можно использовать для приблизительного поиска ближайших соседей по заданной метрике c (обычно L1 или L2.)