Хеширование, чувствительное к местоположению

Алгоритмическая техника с использованием хеширования

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

Приблизительные алгоритмы поиска ближайшего соседа на основе хеширования обычно используют одну из двух основных категорий методов хеширования: либо независимые от данных методы, такие как локально-чувствительное хеширование (LSH); либо зависимые от данных методы, такие как локально-сохраняющее хеширование (LPH). ^{[2] [3]}

Хеширование с сохранением локальности изначально было разработано как способ облегчения конвейеризации данных в реализациях массивно-параллельных алгоритмов, которые используют рандомизированную маршрутизацию и универсальное хеширование для снижения конкуренции за память и перегрузки сети . ^{[4] [5]}

Определения

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

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

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

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

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

LSH относительно меры подобия

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

Усиление

Учитывая -чувствительное семейство , мы можем построить новые семейства либо с помощью конструкции AND, либо с помощью конструкции OR . ^[1] ${\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},\ldots ,h_{k}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle g\in {\mathcal {G}}}$ ${\displaystyle g(x)=g(y)}$ ${\displaystyle h_{i}(x)=h_{i}(y)}$ ${\displaystyle i=1,2,\ldots ,k}$ ${\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},\ldots ,h_{k}}$ ${\displaystyle {\mathcal {F}}}$ ${\displaystyle g\in {\mathcal {G}}}$ ${\displaystyle g(x)=g(y)}$ ${\displaystyle h_{i}(x)=h_{i}(y)}$ ${\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 применялся к нескольким проблемным областям, включая:

• Обнаружение почти дубликатов ^[9]
• Иерархическая кластеризация ^{[10] [11]}
• Исследование ассоциаций по всему геному ^[12]
• Идентификация сходства изображений
  • VisualRank
• Идентификация сходства экспрессии генов ^{[ необходима ссылка ]}
• Идентификация аудио-сходства
• Поиск ближайшего соседа
• Аудио отпечаток пальца ^[13]
• Цифровая видео-отпечатка пальцев
• Организация общей памяти в параллельных вычислениях ^{[4] [5]}
• Физическая организация данных в системах управления базами данных ^[14]
• Обучение полностью связанных нейронных сетей ^{[15] [16]}
• Компьютерная безопасность ^[17]
• Машинное обучение ^[18]

Методы

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

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

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

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

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

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

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

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

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

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

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

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

ТЛШ

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

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

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

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

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

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

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

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

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

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

Стабильные распределения

Функция хэширования ^[28] отображает d -мерный вектор на множество целых чисел. Каждая функция хэширования в семействе индексируется выбором случайного и , где — d -мерный вектор с элементами, выбранными независимо из устойчивого распределения , и — действительное число, выбранное равномерно из диапазона [0,r]. Для фиксированного хэш-функция задается как . ${\displaystyle h_{\mathbf {a} ,b}({\boldsymbol {\upsilon }}):{\mathcal {R}}^{d}\to {\mathcal {N}}}$ ${\displaystyle {\boldsymbol {\upsilon }}}$ ${\displaystyle \mathbf {a} }$ ${\displaystyle b}$ ${\displaystyle \mathbf {a} }$ ${\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 }$

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

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

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

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

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

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

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

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

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

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

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

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

Улучшения

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

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

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

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

• Фильтр Блума  – Структура данных для приблизительного членства в наборе
• Проклятие размерности  – трудности, возникающие при анализе данных со многими аспектами («измерениями»).
• Хеширование признаков  – векторизация признаков с использованием хеш-функции
• Преобразования, связанные с Фурье
• Geohash  – общественное геокодирование, изобретенное в 2008 году.
• Мультилинейное подпространственное обучение  – подход к снижению размерности
• Анализ главных компонент  – Метод анализа данных
• Случайная индексация ^[34]
• Rolling hash  – Тип хеш-функции
• Разложение сингулярных чисел  – Матричное разложение
• Разреженная распределенная память  – Математическая модель памяти
• Вейвлет-сжатие  – математический метод, используемый для сжатия и анализа данных.Pages displaying short descriptions of redirect targets

Ссылки

1. Раджараман, А.; Ульман, Дж. (2010). «Майнинг массивных наборов данных, Гл. 3».
2. Чжао, Кан; Лу, Хонгтао; Мэй, Цзиньчэн (2014). Хеширование с сохранением локальности. Конференция AAAI по искусственному интеллекту. Том 28. С. 2874–2880.
3. Цай, И-Сюань; Ян, Мин-Сюань (октябрь 2014 г.). «Хеширование с сохранением локальности». Международная конференция IEEE по обработке изображений (ICIP) , 2014 г. стр. 2988–2992. дои : 10.1109/ICIP.2014.7025604. ISBN 978-1-4799-5751-4. ISSN  1522-4880. S2CID  8024458.
4. Chin, Andrew (1991). Проблемы сложности в параллельных вычислениях общего назначения (DPhil). Оксфордский университет. С. 87–95.
5. Chin, Andrew (1994). "Хеш-функции, сохраняющие локальность, для параллельных вычислений общего назначения" (PDF) . Algorithmica . 12 (2–3): 170–181. doi :10.1007/BF01185209. S2CID  18108051.
6. Gionis, A.; Indyk, P .; Motwani, R. (1999). «Поиск сходства в больших измерениях с помощью хеширования». Труды 25-й конференции по очень большим базам данных (VLDB) .
7. Indyk, Piotr .; Motwani, Rajeev . (1998). «Приближенные ближайшие соседи: на пути к устранению проклятия размерности». Труды 30-го симпозиума по теории вычислений .
8. Чарикар, Мозес С. (2002). «Методы оценки сходства на основе алгоритмов округления». Труды 34-го ежегодного симпозиума ACM по теории вычислений . стр. 380–388. CiteSeerX 10.1.1.147.4064 . doi :10.1145/509907.509965. ISBN  1-58113-495-9.
9. Дас, Абхинандан С. и др. (2007), «Персонализация новостей Google: масштабируемая совместная онлайн-фильтрация», Труды 16-й международной конференции по Всемирной паутине , стр. 271–280, doi :10.1145/1242572.1242610, ISBN 9781595936547, S2CID  207163129.
10. Кога, Хисаши; Тетсуо Ишибаши; Тошинори Ватанабэ (2007), «Быстрый агломеративный иерархический алгоритм кластеризации с использованием локально-чувствительного хеширования», Системы знаний и информации , 12 (1): 25–53, doi :10.1007/s10115-006-0027-5, S2CID  4613827.
11. Кочез, Майкл; Моу, Хао (2015), «Twister Tries», Труды Международной конференции ACM SIGMOD 2015 года по управлению данными (PDF) , стр. 505–517, doi :10.1145/2723372.2751521, ISBN 9781450327589, S2CID  14414777.
12. Бринза, Думитру и др. (2010), «БЫСТРОЕ обнаружение взаимодействий генов в исследованиях ассоциаций на уровне генома», Биоинформатика , 26 (22): 2856–2862, doi :10.1093/bioinformatics/btq529, PMC 3493125 , PMID  20871107 
13. dejavu - Аудиоотпечатки и распознавание в Python, 2018-12-19
14. Алуч, Гюнеш; Озсу, М. Тамер; Даудджи, Хузайма (2018), «Создание самокластеризующихся баз данных RDF с использованием Tunable-LSH», The VLDB Journal , 28 (2): 173–195, doi :10.1007/s00778-018-0530-9, S2CID  53695535
15. Чен, Бейди; Медини, Тарун; Фарвелл, Джеймс; Гобриэль, Самех; Тай, Чарли; Шривастава, Аншумали (29.02.2020). «СЛАЙД: В защиту интеллектуальных алгоритмов по сравнению с аппаратным ускорением для крупномасштабных систем глубокого обучения». arXiv : 1903.03129 [cs.DC].
16. Чен, Бэйди; Лю, Цзычан; Пэн, Бинхуэй; Сюй, Чжаочжуо; Ли, Джонатан Линцзе; Дао, Три; Сун, Чжао; Шривастава, Аншумали; Ре, Кристофер (2021), «MONGOOSE: обучаемая структура LSH для эффективного обучения нейронных сетей», Международная конференция по представлению обучения
17. Оливер, Джонатан; Ченг, Чун; Чен, Янгуй (2013). TLSH — хэш, чувствительный к местоположению. 4-й семинар по киберпреступности и надежным вычислениям . стр. 7–13. doi :10.1109/CTC.2013.9. ISBN 978-1-4799-3076-0.
18. Fanaee-T, Hadi (2024), Естественное обучение , arXiv : 2404.05903
19. Бродер, AZ ; Чарикар, М. ; Фриз, AM ; Митценмахер, М. (1998). "Независимые перестановки с минимальным значением". Труды тридцатого ежегодного симпозиума ACM по теории вычислений . стр. 327–336. CiteSeerX 10.1.1.409.9220 . doi :10.1145/276698.276781 . Получено 14.11.2007 . 
20. Такеи, Ю.; Ито, Т.; Шинозаки, Т. «Оптимальное построение точно минимальных независимых перестановок». Технический отчет COMP98-62, IEICE, 1998 .
21. Matoušek , J.; Stojakovic, M. (2002). "Об ограниченной минимальной независимости перестановок". Препринт . Получено 14.11.2007 .
22. Saks, M. ; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000). «Наборы с низким расхождением дают приближенные независимые семейства перестановок с минимальным масштабом». Information Processing Letters . 73 (1–2): 29–32. CiteSeerX 10.1.1.20.8264 . doi :10.1016/S0020-0190(99)00163-5 . Получено 14.11.2007 . 
23. Дамиани и др. (2004). «Открытый дайджест-метод обнаружения спама» (PDF) . Получено 01.09.2013 .
24. Оливер и др. (2013). «TLSH — локальный чувствительный хэш». 4-й семинар по киберпреступности и надежным вычислениям . Получено 04.06.2015 .
25. "TLSH". GitHub . Получено 2014-04-10 .
26. Александр Андони; Индик, П. (2008). «Почти оптимальные алгоритмы хеширования для приближенного ближайшего соседа в больших размерностях». Сообщения ACM . 51 (1): 117–122. CiteSeerX 10.1.1.226.6905 . doi :10.1145/1327452.1327494. S2CID  6468963. 
27. Goemans, Michel X.; Williamson, David P. (1995). «Улучшенные алгоритмы аппроксимации для задач максимального разреза и выполнимости с использованием полуопределенного программирования». Журнал ACM . 42 (6). Ассоциация вычислительной техники (ACM): 1115–1145. doi : 10.1145/227683.227684 . ISSN  0004-5411. S2CID  15794408.
28. Datar, M.; Immorlica, N .; Indyk, P .; Mirrokni, VS (2004). «Локально-чувствительная схема хеширования на основе p-устойчивых распределений». Труды симпозиума по вычислительной геометрии .
29. Pauleve, L.; Jegou, H.; Amsaleg, L. (2010). «Локальное чувствительное хеширование: сравнение типов хеш-функций и механизмов запросов». Pattern Recognition Letters . 31 (11): 1348–1358. Bibcode :2010PaReL..31.1348P. doi :10.1016/j.patrec.2010.04.004. S2CID  2666044.
30. Салахутдинов, Руслан; Хинтон, Джеффри (2008). «Семантическое хеширование». Международный журнал приближенного рассуждения . 50 (7): 969–978. doi : 10.1016/j.ijar.2008.11.006 .
31. Дальгаард, Сорен, Матиас Бек Тейс Кнудсен и Миккель Торуп. «Быстрое создание эскизов по подобию». 58-й ежегодный симпозиум IEEE по основам информатики (FOCS), 2017 г. ИИЭР, 2017.
32. Кристиани, Тобиас. «Быстрые локально-чувствительные хеш-фреймворки для приблизительного поиска ближайшего соседа». Международная конференция по поиску сходства и приложениям. Springer, Cham, 2019.
33. Ахле, Томас Дибдаль. «О проблеме локально-чувствительного хеширования». Международная конференция по поиску сходства и его применению. Springer, Cham, 2020. ${\displaystyle p_{1}^{-1}}$
34. Горман, Джеймс и Джеймс Р. Карран. «Масштабирование распределительного сходства для больших корпусов». Труды 21-й Международной конференции по компьютерной лингвистике и 44-го ежегодного собрания Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики, 2006.

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

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

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

• Домашняя страница LSH Алекса Андони
• LSHKIT: библиотека хеширования, чувствительная к локальности C++
• Библиотека хеширования с учетом локальности Python, которая опционально поддерживает сохранение через Redis
• Caltech Large Scale Image Search Toolbox: набор инструментов Matlab, реализующий несколько хэш-функций LSH, а также алгоритмы поиска Kd-деревьев, иерархических K-средних и инвертированных файлов.
• Slash: библиотека C++ LSH, реализующая сферический LSH, авторы Terasawa, K., Tanaka, Y.
• 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