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

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

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

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

Определения

Конечная семья ${\mathcal {F}}$ функций $h\colon M\to S$ определяется как семейство LSH для

• метрическое пространство ${\mathcal {M}}=(M,d)$,
• порог $r>0$,
• коэффициент аппроксимации $c>1$,
• и вероятности $p_{1}>p_{2}$

если оно удовлетворяет следующему условию. Для любых двух точек $a,b\in M$ и хеш-функция $h$ выбираются равномерно случайным образом из ${\mathcal {F}}$:

• Если $d(a,b)\leq r$, затем $h(a)=h(b)$ (т.е. a и b сталкиваются) с вероятностью не менее $p_{1}$,
• Если $d(a,b)\geq cr$, затем $h(a)=h(b)$ с вероятностью не более $p_{2}$.

Такая семья ${\mathcal {F}}$ называется $(r,cr,p_{1},p_{2})$-чувствительный.

LSH по мере сходства

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

Усиление

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

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

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

Приложения

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

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

Методы

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

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

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

Основная статья: МинХэш

Предположим, что состоит из подмножеств некоторого основного множества перечислимых элементов S , а интересующей функцией сходства является индекс Жаккара J. U Если π — перестановка индексов S , для $A\subseteq S$ позволять $h(A)=\min _{a\in A}\{\pi (a)\}$. Каждый возможный выбор π определяет одну хэш-функцию h, отображающую входные наборы в элементы S .

Определим семейство функций H как набор всех таких функций и пусть D будет равномерным распределением . Учитывая два набора $A,B\subseteq S$ событие, которое $h(A)=h(B)$ точно соответствует событию, когда минимизатор π по $A\cup B$ лежит внутри $A\cap B$. Поскольку h был выбран равномерно случайным образом, $Pr[h(A)=h(B)]=J(A,B)\,$ и $(H,D)\,$ определить схему LSH для индекса Жаккара.

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

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

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

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

Основная статья: Нильсимса Хэш

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

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

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

ТЛШ

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

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

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

Основная статья: Случайная проекция

${\frac {\theta (u,v)}{\pi }}$ пропорционально $1-\cos(\theta (u,v))$ на интервале [0, $\pi$]

Метод случайной проекции LSH Моисея Чарикара. называется SimHash (также иногда называемый arccos ) использует приближение косинусного расстояния между векторами. Этот метод использовался для аппроксимации NP-полной задачи максимального разреза .

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

Учитывая входной вектор v и гиперплоскость, определенную r , мы позволяем $h(v)=\operatorname {sgn}(v\cdot r)$. То есть, $h(v)=\pm 1$ в зависимости от того, с какой стороны лежит гиперплоскость v . Таким образом, каждый возможный выбор случайной гиперплоскости r можно интерпретировать как хеш-функцию. $h(v)$.

Для двух векторов u,v с углом $\theta (u,v)$ между ними, можно показать, что

$Pr[h(u)=h(v)]=1-{\frac {\theta (u,v)}{\pi }}.$

Поскольку соотношение между ${\frac {\theta (u,v)}{\pi }}$ и $1-\cos(\theta (u,v))$ составляет не менее 0,87856, когда $\theta (u,v)\in [0,\pi ]$, вероятность того, что два вектора окажутся по одну сторону от случайной гиперплоскости, примерно пропорциональна косинусному расстоянию между ними.

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

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

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

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

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

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

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

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

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

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

Учитывая параметры k и L , алгоритм имеет следующие гарантии производительности:

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

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

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

Улучшения

Когда t велико, можно сократить время хэширования с $O(n^{\rho })$.Это было показано и что дало

• время запроса: $O(t\log ^{2}(1/P_{2})/P_{1}+n^{\rho }(d+1/P_{1}))$;
• космос: $O(n^{1+\rho }/P_{1}+\log ^{2}(1/P_{2})/P_{1})$;

Иногда бывает так, что фактор $1/P_{1}$ может быть очень большим.Это происходит, например, с данными о сходстве Жаккара , где даже самый похожий сосед часто имеет довольно низкое сходство Жаккара с запросом.В было показано, как сократить время запроса до $O(n^{\rho }/P_{1}^{1-\rho })$ (не включая затраты на хеширование) и, аналогично, использование пространства.

См. также

• Фильтр Блума – структура данных для приблизительного членства в наборе
• Проклятие размерности . Трудности, возникающие при анализе данных со многими аспектами («измерениями»).
• Хеширование объектов — векторизация объектов с использованием хэш-функции.
• Преобразования, связанные с Фурье
• Geohash - геокодирование, являющееся общественным достоянием, изобретенное в 2008 году.
• Многолинейное обучение подпространству – подход к уменьшению размерности
• Анализ главных компонентов . Метод анализа данных.
• Случайная индексация
• Скользящий хеш – тип хеш-функции.
• Разложение по сингулярным значениям – Матричное разложение
• Разреженная распределенная память - Математическая модель памяти.
• Вейвлет-сжатие — математический метод, используемый для сжатия и анализа данных. Страницы с краткими описаниями целей перенаправления.

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

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

Внешние ссылки

• Домашняя страница LSH Алекса Андони
• LSHKIT: библиотека хеширования C++ с учетом локальных особенностей
• Библиотека Python с учетом локальности хэширования, которая дополнительно поддерживает сохранение через Redis.
• Набор инструментов для поиска крупномасштабных изображений Калифорнийского технологического института : набор инструментов Matlab, реализующий несколько хеш-функций LSH, в дополнение к Kd-деревьям, иерархическим K-средним и алгоритмам поиска инвертированных файлов.
• Slash: библиотека C++ LSH, реализующая сферический LSH, авторы: Терасава К., Танака Ю.
• LSHBOX: набор инструментов C++ с открытым исходным кодом для локально-зависимого хеширования для крупномасштабного поиска изображений, также поддерживает Python и MATLAB.
• SRS: C++ реализация в памяти экономичного алгоритма обработки запросов к ближайшему соседу, основанного на p-стабильной случайной проекции
• TLSH с открытым исходным кодом на Github
• Порт JavaScript для TLSH (Trend Micro Locality Sensitive Hashing), входящий в состав модуля node.js.
• Java-порт TLSH (Trend Micro Locality Sensitive Hashing), входящий в состав пакета maven.