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

В информатике хеширование с учетом местоположения ( LSH ) - это алгоритмический метод, который с высокой вероятностью хэширует аналогичные входные элементы в одни и те же «корзины». (Количество сегментов намного меньше, чем набор возможных входных элементов.) Поскольку похожие элементы попадают в одни и те же сегменты, этот метод можно использовать для кластеризации данных и поиска ближайшего соседа . Он отличается от обычных методов хеширования тем, что конфликты хеширования максимизируются, а не минимизируются. В качестве альтернативы, этот метод можно рассматривать как способ уменьшить размерность данных большой размерности; элементы ввода с высокой размерностью могут быть уменьшены до версий с меньшей размерностью, сохраняя при этом относительные расстояния между элементами.

Алгоритмы приблизительного поиска ближайшего соседа на основе хеширования обычно используют одну из двух основных категорий методов хеширования: либо методы, не зависящие от данных, такие как хеширование с учетом местоположения (LSH); или методы, зависящие от данных, такие как хеширование с сохранением местоположения (LPH).

Определения

Семьи LSH определяется для метрического пространства , порога , коэффициента аппроксимации , а также вероятностей и . Это семейство представляет собой набор функций, которые отображают элементы метрического пространства в корзины . Семейство LSH должно удовлетворять следующим условиям для любых двух точек и любой хэш-функции, выбранной равномерно случайным образом из : ${\ Displaystyle {\ mathcal {F}}}$ ${\ Displaystyle {\ mathcal {M}} = (M, d)}$ ${\ displaystyle R> 0}$ ${\ displaystyle c> 1}$ ${\ displaystyle P_ {1}}$ ${\ displaystyle P_ {2}}$ ${\ Displaystyle {\ mathcal {F}}}$ ${\ displaystyle h: M \ to S}$ ${\ displaystyle s \ in S}$ ${\ displaystyle p, q \ in M}$ ${\ displaystyle h}$ ${\ Displaystyle {\ mathcal {F}}}$

если , то (т. е. $p$ и $q$ сталкиваются) с вероятностью не менее , ${\ displaystyle d (p, q) \ leq R}$ ${\ Displaystyle ч (р) = ч (д)}$ ${\ displaystyle P_ {1}}$
если , то с максимальной вероятностью . ${\ displaystyle d (p, q) \ geq cR}$ ${\ Displaystyle ч (р) = ч (д)}$ ${\ displaystyle P_ {2}}$

Семья - это интересно, когда . Такая семья называется -чувствительной . ${\ displaystyle P_ {1}> P_ {2}}$ ${\ Displaystyle {\ mathcal {F}}}$ ${\ displaystyle (R, cR, P_ {1}, P_ {2})}$

В качестве альтернативы он определен по отношению к вселенным элементам $U$ , которые имеют сходство функции . Схема LSH - это семейство хэш-функций $H,$ связанных с распределением вероятностей $D$ по функциям, таким образом, что функция, выбранная согласно $D,$ удовлетворяет свойству, что для любого . ${\ displaystyle \ phi: U \ times U \ to [0,1]}$ ${\ displaystyle h \ in H}$ ${\ Displaystyle Pr_ {час \ в H} [час (а) = час (Ь)] = \ фи (а, Ь)}$ ${\ displaystyle a, b \ in U}$

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

Сохраняющий локальность хеш - это хеш-функция f, которая отображает точки в метрическом пространстве в скалярное значение, такое что ${\ Displaystyle {\ mathcal {M}} = (M, d)}$

{\ Displaystyle d (p, q) <d (q, r) \ Rightarrow | f (p) -f (q) | <| f (q) -f (r) |. \,}

для любых трех точек . ${\ displaystyle p, q, r \ in M}$

Другими словами, это хеш-функции, в которых относительное расстояние между входными значениями сохраняется в относительном расстоянии между выходными хеш-значениями; входные значения, которые находятся ближе друг к другу, будут производить выходные хеш-значения, которые ближе друг к другу.

Это контрастирует с криптографическими хэш-функциями и контрольными суммами , которые предназначены для получения случайной разности выходных данных между соседними входами .

Хэши, сохраняющие локальность, связаны с кривыми заполнения пространства .

Усиление

Учитывая -чувствительное семейство , мы можем построить новые семейства с помощью И-конструкции или ИЛИ-конструкции . ${\ displaystyle (d_ {1}, d_ {2}, p_ {1}, p_ {2})}$ ${\ Displaystyle {\ mathcal {F}}}$ ${\ Displaystyle {\ mathcal {G}}}$ ${\ Displaystyle {\ mathcal {F}}}$

Чтобы создать AND-конструкцию, мы определяем новое семейство хэш-функций $g$ , где каждая функция $g$ построена из $k$ случайных функций из . Затем мы говорим, что для хэш-функции , тогда и только тогда, когда все для . Поскольку члены семьи выбираются независимо для любой , является -чувствительной семьей. ${\ Displaystyle {\ mathcal {G}}}$ ${\ displaystyle h_ {1}, ..., h_ {k}}$ ${\ Displaystyle {\ mathcal {F}}}$ ${\ displaystyle g \ in {\ mathcal {G}}}$ ${\ Displaystyle г (х) = г (у)}$ ${\ Displaystyle ч_ {я} (х) = ч_ {я} (у)}$ ${\ Displaystyle я = 1,2, ..., к}$ ${\ Displaystyle {\ mathcal {F}}}$ ${\ displaystyle g \ in {\ mathcal {G}}}$ ${\ Displaystyle {\ mathcal {G}}}$ ${\ displaystyle (d_ {1}, d_ {2}, p_ {1} ^ {k}, p_ {2} ^ {k})}$

Чтобы создать OR-конструкцию, мы определяем новое семейство хэш-функций $g$ , где каждая функция $g$ построена из $k$ случайных функций из . Тогда мы будем говорить , что для хэш - функции , если и только если для одного или нескольких значений $I$ . Поскольку члены любой семьи выбираются независимо , является -чувствительной семьей. ${\ Displaystyle {\ mathcal {G}}}$ ${\ displaystyle h_ {1}, ..., h_ {k}}$ ${\ Displaystyle {\ mathcal {F}}}$ ${\ displaystyle g \ in {\ mathcal {G}}}$ ${\ Displaystyle г (х) = г (у)}$ ${\ Displaystyle ч_ {я} (х) = ч_ {я} (у)}$ ${\ Displaystyle {\ mathcal {F}}}$ ${\ displaystyle g \ in {\ mathcal {G}}}$ ${\ Displaystyle {\ mathcal {G}}}$ ${\ displaystyle (d_ {1}, d_ {2}, 1- (1-p_ {1}) ^ {k}, 1- (1-p_ {2}) ^ {k})}$

Приложения

LSH был применен к нескольким проблемным областям, включая:

Обнаружение почти дубликатов
Иерархическая кластеризация
Полногеномное исследование ассоциации
Идентификация сходства изображений
- VisualRank
Идентификация сходства экспрессии генов
Идентификация звукового сходства
Поиск ближайшего соседа
Аудио отпечаток пальца
Цифровое снятие отпечатков пальцев с видео
Физическая организация данных в системах управления базами данных
Обучение полносвязных нейронных сетей

Компьютерная безопасность

Методы

Битовая выборка для расстояния Хэмминга

Один из самых простых способов создать семейство LSH - это побитовая выборка. Этот подход работает для расстояния Хэмминга по d-мерным векторам . Здесь семейство хэш-функций - это просто семейство всех проекций точек на одну из координат, т. Е. , Где - th координата . Случайная функция из просто выбирает случайный бит из входной точки. Это семейство имеет следующие параметры: , . ${\ displaystyle \ {0,1 \} ^ {d}}$ ${\ Displaystyle {\ mathcal {F}}}$ ${\ displaystyle d}$ ${\ displaystyle {\ mathcal {F}} = \ {h: \ {0,1 \} ^ {d} \ to \ {0,1 \} \ mid h (x) = x_ {i} {\ text { для некоторых}} i \ in \ {1, ..., d \} \}}$ ${\ displaystyle x_ {i}}$ ${\ displaystyle i}$ ${\ displaystyle x}$ ${\ displaystyle h}$ ${\ Displaystyle {\ mathcal {F}}}$ ${\ Displaystyle P_ {1} = 1-R / d}$ ${\ Displaystyle P_ {2} = 1-cR / d}$

Минимальные независимые перестановки

Пусть $U$ состоит из подмножеств некоторого основного множества ПЕРЕЧИСЛИМЫХ элементов $S$ и функции подобия интереса представляет Jaccard индекс $J$ . Если $π$ - перестановка индексов $S$ , пусть . Каждый возможный выбор $П$ определяет один хэш - функции $ч$ входных наборов отображения к элементам $S$ . ${\ displaystyle A \ substeq S}$ ${\ Displaystyle ч (А) = \ мин _ {а \ в А} \ {\ пи (а) \}}$

Определим семейство функций $H$ как набор всех таких функций, и пусть $D$ будет равномерным распределением . Учитывая два набора событие , которое точно соответствует событию , что минимизант $П$ над лежит внутри . Как $ч$ была выбрана случайно равномерно, и определить схему LSH для индекса Жаккара. ${\ displaystyle A, B \ substeq S}$ ${\ Displaystyle ч (А) = ч (В)}$ ${\ Displaystyle A \ чашка B}$ ${\ displaystyle A \ cap B}$ ${\ Displaystyle Pr [час (A) = час (B)] = J (A, B) \,}$ ${\ Displaystyle (Ч, D) \,}$

Поскольку симметричная группа на $n$ элементах имеет размер $n$ !, выбор действительно случайной перестановки из полной симметричной группы невозможен даже для среднего размера $n$ . Из-за этого факта, была проведена значительная работа по поиску семейства перестановок, которое "не зависит от минимума" - семейства перестановок, для которого каждый элемент области имеет равную вероятность быть минимальным при случайно выбранном $π$ . Было установлено, что минимально независимое семейство перестановок имеет по крайней мере размер , и что эта граница жесткая. ${\ displaystyle \ operatorname {lcm} (1,2, \ cdots, n) \ geq e ^ {no (n)}}$

Поскольку минимально независимые семейства слишком велики для практических приложений, вводятся два варианта понятия минимальной независимости: ограниченные минимально независимые семейства перестановок и приблизительные минимально независимые семейства. Ограниченная минимальная независимость - это свойство минимальной независимости, ограниченное некоторыми наборами мощности не более $k$ . Приближенная минимальная независимость отличается от свойства не более чем на фиксированное $ε$ .

Методы с открытым исходным кодом

Нильсимса Хаш

Nilsimsa - это алгоритм хеширования, зависящий от местности, используемый в усилиях по борьбе со спамом . Цель Nilsimsa - создать хэш-дайджест сообщения электронной почты, чтобы дайджесты двух похожих сообщений были похожи друг на друга. В статье предполагается, что Нильсимса удовлетворяет трем требованиям:

Дайджест, идентифицирующий каждое сообщение, не должен существенно отличаться от изменений, которые могут производиться автоматически.
Кодирование должно быть устойчивым к преднамеренным атакам.
Кодировка должна поддерживать чрезвычайно низкий риск ложных срабатываний.

TLSH

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

Тестирование, проведенное в статье на ряде типов файлов, показало, что хэш Nilsimsa имеет значительно более высокий уровень ложных срабатываний по сравнению с другими схемами дайджеста сходства, такими как TLSH, Ssdeep и Sdhash.

Реализация TLSH доступна как программное обеспечение с открытым исходным кодом .

Случайная проекция

Для малых углов (не слишком близких к ортогональным) это довольно хорошее приближение к .

{\ displaystyle 1 - {\ frac {\ theta} {\ pi}}}

{\ Displaystyle \ соз (\ тета)}

Метод случайной проекции LSH из-за Моисея Чарикара, называемый SimHash (также иногда называемый arccos), предназначен для аппроксимации косинусного расстояния между векторами. Основная идея этого метода состоит в том, чтобы выбрать случайную гиперплоскость (определяемую нормальным единичным вектором $r$ ) в самом начале и использовать гиперплоскость для хеширования входных векторов.

Для входного вектора $v$ и гиперплоскости, определяемой $r$ , мы положим . То есть в зависимости от того, с какой стороны лежит гиперплоскость $v$ . ${\ Displaystyle ч (v) = sign (v \ cdot r)}$ ${\ displaystyle h (v) = \ pm 1}$

Каждый возможный выбор $r$ определяет одну функцию. Пусть $H$ - множество всех таких функций, и пусть $D$ - снова равномерное распределение. Не трудно доказать , что для двух векторов , где угол между $ц$ и $об$ . тесно связан с . ${\ displaystyle u, v}$ ${\ Displaystyle Pr [час (и) = час (v)] = 1 - {\ гидроразрыва {\ theta (u, v)} {\ pi}}}$ ${\ Displaystyle \ theta (и, v)}$ ${\ displaystyle 1 - {\ frac {\ theta (u, v)} {\ pi}}}$ ${\ Displaystyle \ соз (\ тета (и, v))}$

В этом случае хеширование дает только один бит. Биты двух векторов совпадают с вероятностью, пропорциональной косинусу угла между ними.

Стабильные дистрибутивы

Хеш-функция отображает d- мерный вектор на множество целых чисел. Каждый хэш - функции в семье индексируется путем выбора случайным образом и где это д мерный вектор с элементами , выбранными независимо из распределения стабильного и является действительным числом выбраны равномерно из диапазона [0, г]. Для фиксированного значения хэш-функция имеет вид . ${\ displaystyle h _ {\ mathbf {a}, b} ({\ boldsymbol {\ upsilon}}): {\ mathcal {R}} ^ {d} \ to {\ mathcal {N}}}$ ${\ displaystyle {\ boldsymbol {\ upsilon}}}$ ${\ Displaystyle \ mathbf {а}}$ ${\ displaystyle b}$ ${\ Displaystyle \ mathbf {а}}$ ${\ displaystyle b}$ ${\ displaystyle \ mathbf {a}, b}$ ${\ displaystyle h _ {\ mathbf {a}, b}}$ ${\ displaystyle h _ {\ mathbf {a}, b} ({\ boldsymbol {\ upsilon}}) = \ left \ lfloor {\ frac {\ mathbf {a} \ cdot {\ boldsymbol {\ upsilon}} + b} {r}} \ right \ rfloor}$

Для лучшего соответствия данным были предложены другие методы построения хэш-функций. В частности, на практике хеш-функции k-средних лучше, чем хеш-функции на основе проекций, но без каких-либо теоретических гарантий.

Семантическое хеширование

Семантическое хеширование - это метод, который пытается сопоставить входные элементы с адресами, чтобы более близкие входные данные имели более высокое семантическое сходство . Хэш-коды находятся путем обучения искусственной нейронной сети или графической модели .

LSH алгоритм поиска ближайшего соседа

Одним из основных приложений LSH является обеспечение метода эффективных алгоритмов поиска ближайшего соседа . Рассмотрим семейство LSH . Алгоритм имеет два основных параметра: ширину параметра $K$ и количество хэш - таблицы $L$ . ${\ Displaystyle {\ mathcal {F}}}$

На первом шаге мы определяем новое семейство хэш-функций $g$ , где каждая функция $g$ получается конкатенацией $k$ функций из , т . Е .. Другими словами, случайная хеш-функция $g$ получается конкатенацией $k$ случайно выбранных хэш-функций из . Затем алгоритм создает $L$ хэш-таблиц, каждая из которых соответствует разной случайно выбранной хеш-функции $g$ . ${\ Displaystyle {\ mathcal {G}}}$ ${\ displaystyle h_ {1}, ..., h_ {k}}$ ${\ Displaystyle {\ mathcal {F}}}$ ${\ displaystyle g (p) = [h_ {1} (p), ..., h_ {k} (p)]}$ ${\ Displaystyle {\ mathcal {F}}}$

На этапе предварительной обработки мы хэшируем все $n$ точек из набора данных $S$ в каждую из $L$ хэш-таблиц. Учитывая, что в результирующих хэш-таблицах есть только $n$ ненулевых записей, можно уменьшить объем памяти, используемой для каждой хеш-таблицы, до использования стандартных хеш-функций . ${\ Displaystyle О (п)}$

Для заданной точки запроса $q$ алгоритм перебирает $L$ хэш-функций $g$ . Для каждого рассматриваемого $g$ он извлекает точки данных, которые хешируются в тот же сегмент, что и $q$ . Процесс останавливается, как только будет найдена точка на расстоянии от $q$ . ${\ displaystyle cR}$

При заданных параметрах $k$ и $L$ алгоритм имеет следующие гарантии работоспособности:

время предварительной обработки:, где $t$ - время вычисления функции на входной точке $p$ ; ${\ Displaystyle O (nLkt)}$ ${\ displaystyle h \ in {\ mathcal {F}}}$
пробел:, плюс место для хранения точек данных; ${\ displaystyle O (nL)}$
время запроса: ; ${\ Displaystyle O (L (kt + dnP_ {2} ^ {k}))}$
алгоритму удается найти точку на расстоянии от $q$ (если существует точка на расстоянии $R$ ) с вероятностью не менее ; ${\ displaystyle cR}$ ${\ displaystyle 1- (1-P_ {1} ^ {k}) ^ {L}}$

Для фиксированного отношения аппроксимации и вероятностей и можно установить и , где . Тогда получаются следующие гарантии производительности: ${\ displaystyle c = 1 + \ epsilon}$ ${\ displaystyle P_ {1}}$ ${\ displaystyle P_ {2}}$ ${\ Displaystyle к = \ lceil {\ журнал п \ над \ журнал 1 / P_ {2}} \ rceil}$ ${\ Displaystyle L = \ lceil P_ {1} ^ {- k} \ rceil = O (n ^ {\ rho} P_ {1} ^ {- 1})}$ ${\ displaystyle \ rho = {\ log P_ {1} \ over \ log P_ {2}}}$

время предварительной обработки: ; ${\ Displaystyle О (п ^ {1+ \ rho} P_ {1} ^ {- 1} кт)}$
пробел:, плюс место для хранения точек данных; ${\ Displaystyle О (п ^ {1+ \ rho} P_ {1} ^ {- 1})}$
время запроса: ; ${\ Displaystyle О (п ^ {\ rho} P_ {1} ^ {- 1} (kt + d))}$

Смотрите также

использованная литература

дальнейшее чтение

Самет, Х. (2006) Основы многомерных и метрических структур данных . Морган Кауфманн. ISBN 0-12-369446-9

Индик, Петр ; Мотвани, Раджив ; Рагхаван, Прабхакар; Вемпала, Сантош (1997). «Сохраняющее локальность хеширование в многомерных пространствах». Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений . СТОК '97 . С. 618–625. CiteSeerX 10.1.1.50.4927 . DOI : 10.1145 / 258533.258656 . ISBN 978-0-89791-888-6. S2CID 15693787 .
Чин, Эндрю (1994). «Сохраняющие локальность хэш-функции для параллельных вычислений общего назначения» (PDF) . Алгоритмика . 12 (2–3): 170–181. DOI : 10.1007 / BF01185209 . S2CID 18108051 .

Languages

In other projects