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

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

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

Определения [ править ]

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

В качестве альтернативы ^[6] он определен по отношению к вселенным элементам $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, которая отображает точку или точки в многомерном координатном пространстве в скалярное значение, так что если у нас есть три точки A , B и C, такие что

{\ Displaystyle | AB | <| BC | \ Rightarrow | f (A) -f (B) | <| f (B) -f (C) |. \,}

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

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

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

Усиление [ править ]

Для данного -чувствительного семейства мы можем построить новые семейства с помощью конструкции И или конструкции ИЛИ . ^[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}, ..., h_ {k}}$ ${\ Displaystyle {\ mathcal {F}}}$ $g\in {\mathcal {G}}$ $g(x)=g(y)$ $h_{i}(x)=h_{i}(y)$ $i=1,2,...,k$ ${\mathcal {F}}$ $g\in {\mathcal {G}}$ ${\mathcal {G}}$ $(d_{1},d_{2},p_{1}^{k},p_{2}^{k})$

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

Приложения [ править ]

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

Обнаружение почти дубликатов ^[7]
Иерархическая кластеризация ^[8]^[9]
Полногеномное ассоциативное исследование ^[10]
Идентификация сходства изображений
- VisualRank
Идентификация сходства экспрессии генов ^{[ необходима ссылка ]}
Идентификация звукового сходства
Поиск ближайшего соседа
Отпечаток аудио ^[11]
Цифровое видео отпечатков пальцев
Физическая организация данных в системах управления базами данных ^[12]
Обучение полносвязных нейронных сетей ^[13]^[14]

Компьютерная безопасность ^[15]

Методы [ править ]

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

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

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

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

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

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

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

Методы с открытым исходным кодом [ править ]

Нильсимса Хаш [ править ]

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

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

TLSH [ править ]

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

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

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

Случайная проекция [ править ]

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

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

\cos(\theta )

Случайный метод проекции LSH в связи с Moses Чарикаром ^[6] называется SimHash (также иногда называемый агссоз ^[23] ) предназначен для аппроксимации расстояния косинуса между векторами. Основная идея этого метода состоит в том, чтобы выбрать случайную гиперплоскость (определяемую нормальным единичным вектором $r$ ) в начале и использовать гиперплоскость для хеширования входных векторов.

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

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

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

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

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

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

Алгоритм LSH для поиска ближайшего соседа [ править ]

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

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

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

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

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

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

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

См. Также [ править ]

Фильтр Блума
Проклятие размерности
Хеширование функций
Преобразования, связанные с Фурье
Geohash
Мультилинейное подпространственное обучение
Анализ главных компонентов
Случайная индексация ^[26]
Прокручивающийся хеш
Разложение по сингулярным числам
Редкая распределенная память
Вейвлет-сжатие

Ссылки [ править ]

^ a b c d Раджараман, А .; Ульман, Дж. (2010). «Майнинг массивных наборов данных, глава 3» .
^ Чжао, Кан; Лу, Хунтао; Мэй, Цзиньчэн (2014). «Хеширование с сохранением местоположения» . С. 2874–2880.
^ Цай, И-Сюань; Ян, Мин-Сюань (октябрь 2014 г.). «Хеширование с сохранением местоположения». 2014 Международная конференция IEEE по обработке изображений (ICIP) . С. 2988–2992. DOI : 10,1109 / ICIP.2014.7025604 . ISBN 978-1-4799-5751-4. ISSN 1522-4880 . S2CID 8024458 .
^ Gionis, A .; Indyk, P .; Мотвани, Р. (1999). «Поиск сходства в больших размерах с помощью хеширования» . Труды 25-й конференции по очень большим базам данных (VLDB) .
^ a b Индык, Петр .; Мотвани, Раджив . (1998). «Приблизительные ближайшие соседи: к снятию проклятия размерности». . Материалы 30-го симпозиума по теории вычислений .
^ a b Charikar, Моисей С. (2002). «Методы оценки подобия из алгоритмов округления». Материалы 34-го ежегодного симпозиума ACM по теории вычислений . С. 380–388. CiteSeerX 10.1.1.147.4064 . DOI : 10.1145 / 509907.509965 .
^ Das, Abhinandan S .; и другие. (2007), "Новости персонализацию Google: масштабируемая онлайн совместная фильтрация", Труды 16 - й Международной конференции по World Wide Web : 271, DOI : 10,1145 / 1242572,1242610 , ISBN 9781595936547, S2CID 207163129.
^ Кога, Хисаши; Тецуо Исибаши; Toshinori Watanabe (2007), "Fast агломерационных иерархической кластеризация алгоритм , использующий нас.пункт-Sensitive хеширования", знания и информационные системы , 12 (1): 25-53, DOI : 10.1007 / s10115-006-0027-5 , S2CID 4613827 .
^ Кочез, Майкл; Моу, Хао (2015), «Twister Tries: приблизительная иерархическая агломеративная кластеризация для среднего расстояния в линейное время», Материалы SIGMOD '15 International Conference on Management of Data 2015 ACM SIGMOD : 505–517, doi : 10.1145 / 2723372.2751521 , ISBN 9781450327589, S2CID 14414777.
^ Бринза, Думитру; и другие. (2010), "Обнаружение БЫСТРОГО генно-генных взаимодействий в исследованиях ассоциации генома", биоинформатики , 26 (22): 2856-2862, DOI : 10,1093 / биоинформатики / btq529 , ПМК 3493125 , PMID 20871107
^ dejavu - Аудио отпечатки пальцев и распознавание в Python , 2018-12-19
^ Алуч, Гюнеш; Озсу, М. Тамер; Daudjee, Khuzaima (2018), "Строительство самостоятельной кластеризацию баз данных RDF с использованием перестраиваемой LSH", VLDB Journal , 28 (2): 173-195, DOI : 10.1007 / s00778-018-0530-9 , S2CID 53695535
^ Чен, Бейди; Медини, Тарун; Фарвелл, Джеймс; Гобриэль, Самех; Тай, Чарли; Шривастава, Аншумали (29 февраля 2020 г.). «СЛАЙД: в защиту интеллектуальных алгоритмов вместо аппаратного ускорения для крупномасштабных систем глубокого обучения». arXiv : 1903.03129 [ cs.DC ].
^ Чен, Бейди; Лю, Цзычан; Пэн, Бинхуэй; Сюй, Чжаочжуо; Ли, Джонатан Линджи; Дао, Три; Песня, Чжао; Шривастава, Аншумали; Ре, Кристофер (2021 г.), «MONGOOSE: обучаемая структура LSH для эффективного обучения нейронной сети» , Международная конференция по обучению репрезентации
↑ Оливер, Джонатан; Ченг, Чун; Чен, Yanggui (2013), "ТЛШ - местность чувствительного хэш" , четвёртая Киберпреступность и Trustworthy Computing семинар , DOI : 10,1109 / CTC.2013.9 , ISBN 978-1-4799-3076-0
^ Бродер, Аризона ; Чарикар, М .; Frieze, AM ; Митценмахер М. (1998). «Минимальные независимые перестановки» . Материалы тридцатого ежегодного симпозиума ACM по теории вычислений . С. 327–336. CiteSeerX 10.1.1.409.9220 . DOI : 10.1145 / 276698.276781 . Проверено 14 ноября 2007 .
^ Takei, Y .; Ито, Т .; Шинозаки, Т. "Оптимальное построение точно минимально независимых перестановок". Технический отчет COMP98-62, IEICE, 1998 .
^ Matoušek , J .; Стоякович, М. (2002). «Об ограниченной миниатюрной независимости перестановок» . Препринт . Проверено 14 ноября 2007 .
^ Сакс, М .; Srinivasan, A .; Чжоу, S .; Цукерман, Д. (2000). «Наборы с низким расхождением дают приблизительные по минимуму независимые семейства перестановок» . Письма об обработке информации . 73 (1–2): 29–32. CiteSeerX 10.1.1.20.8264 . DOI : 10.1016 / S0020-0190 (99) 00163-5 . Проверено 14 ноября 2007 .
^ Дамиани; и другие. (2004). «Методика обнаружения спама на основе открытого дайджеста» (PDF) . Проверено 1 сентября 2013 .
^ Оливер; и другие. (2013). «TLSH - хеш, чувствительный к местности» . 4-й семинар по киберпреступности и надежным вычислениям . Проверено 6 апреля 2015 .
^ "ТЛШ" . Проверено 10 апреля 2014 .
^ Александр Андони; Индык, П. (2008). «Почти оптимальные алгоритмы хеширования для приближенного ближайшего соседа в больших размерностях». Коммуникации ACM . 51 (1): 117–122. CiteSeerX 10.1.1.226.6905 . DOI : 10.1145 / 1327452.1327494 . S2CID 6468963 .
^ Датар, М .; Immorlica, N .; Indyk, P .; Миррокни, VS (2004). «Схема хеширования с учетом местоположения на основе p-стабильных распределений» . Материалы симпозиума по вычислительной геометрии .
^ Pauleve, L .; Jegou, H .; Амсалег, Л. (2010). «Хеширование с учетом местоположения: сравнение типов хэш-функций и механизмов запросов» . Письма о распознавании образов . 31 (11): 1348–1358. DOI : 10.1016 / j.patrec.2010.04.004 .
↑ Горман, Джеймс и Джеймс Р. Карран. «Масштабирование дистрибутивного сходства с большими корпусами». Материалы 21-й Международной конференции по компьютерной лингвистике и 44-го ежегодного собрания Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики, 2006.

Дальнейшее чтение [ править ]

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

Индик, Петр ; Мотвани, Раджив ; Рагхаван, Прабхакар; Вемпала, Сантош (1997). «Сохраняющее локальность хеширование в многомерных пространствах». Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений . С. 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 .

Внешние ссылки [ править ]

Домашняя страница Алекса Андони LSH
LSHKIT: библиотека хеширования с учетом местоположения C ++
Библиотека Python для локального хеширования, которая опционально поддерживает сохранение через redis.
Панель инструментов поиска крупномасштабных изображений Caltech : набор инструментов Matlab, реализующий несколько хэш-функций LSH, в дополнение к алгоритмам поиска Kd-Trees, Hierarchical K-Means и Inverted File.
Слэш: библиотека 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

[MOMD-1] Раджараман, А .; Ульман, Дж. (2010). «Майнинг массивных наборов данных, глава 3» .

[2] Чжао, Кан; Лу, Хунтао; Мэй, Цзиньчэн (2014). «Хеширование с сохранением местоположения» . С. 2874–2880.

[3] Цай, И-Сюань; Ян, Мин-Сюань (октябрь 2014 г.). «Хеширование с сохранением местоположения». 2014 Международная конференция IEEE по обработке изображений (ICIP) . С. 2988–2992. DOI : 10,1109 / ICIP.2014.7025604 . ISBN 978-1-4799-5751-4. ISSN 1522-4880 . S2CID 8024458 .

[GIM1999-4] Gionis, A .; Indyk, P .; Мотвани, Р. (1999). «Поиск сходства в больших размерах с помощью хеширования» . Труды 25-й конференции по очень большим базам данных (VLDB) .

[IndykMotwani98-5] Индык, Петр .; Мотвани, Раджив . (1998). «Приблизительные ближайшие соседи: к снятию проклятия размерности». . Материалы 30-го симпозиума по теории вычислений .

[Charikar2002-6] Charikar, Моисей С. (2002). «Методы оценки подобия из алгоритмов округления». Материалы 34-го ежегодного симпозиума ACM по теории вычислений . С. 380–388. CiteSeerX 10.1.1.147.4064 . DOI : 10.1145 / 509907.509965 .

[7] Das, Abhinandan S .; и другие. (2007), "Новости персонализацию Google: масштабируемая онлайн совместная фильтрация", Труды 16 - й Международной конференции по World Wide Web : 271, DOI : 10,1145 / 1242572,1242610 , ISBN 9781595936547, S2CID 207163129.

[8] Кога, Хисаши; Тецуо Исибаши; Toshinori Watanabe (2007), "Fast агломерационных иерархической кластеризация алгоритм , использующий нас.пункт-Sensitive хеширования", знания и информационные системы , 12 (1): 25-53, DOI : 10.1007 / s10115-006-0027-5 , S2CID 4613827 .

[9] Кочез, Майкл; Моу, Хао (2015), «Twister Tries: приблизительная иерархическая агломеративная кластеризация для среднего расстояния в линейное время», Материалы SIGMOD '15 International Conference on Management of Data 2015 ACM SIGMOD : 505–517, doi : 10.1145 / 2723372.2751521 , ISBN 9781450327589, S2CID 14414777.

[10] Бринза, Думитру; и другие. (2010), "Обнаружение БЫСТРОГО генно-генных взаимодействий в исследованиях ассоциации генома", биоинформатики , 26 (22): 2856-2862, DOI : 10,1093 / биоинформатики / btq529 , ПМК 3493125 , PMID 20871107

[11] vu - Аудио отпечатки пальцев и распознавание в Python , 2018-12-19

[12] Алуч, Гюнеш; Озсу, М. Тамер; Daudjee, Khuzaima (2018), "Строительство самостоятельной кластеризацию баз данных RDF с использованием перестраиваемой LSH", VLDB Journal , 28 (2): 173-195, DOI : 10.1007 / s00778-018-0530-9 , S2CID 53695535

[13] Чен, Бейди; Медини, Тарун; Фарвелл, Джеймс; Гобриэль, Самех; Тай, Чарли; Шривастава, Аншумали (29 февраля 2020 г.). «СЛАЙД: в защиту интеллектуальных алгоритмов вместо аппаратного ускорения для крупномасштабных систем глубокого обучения». arXiv : 1903.03129 [ cs.DC ].

[14] Чен, Бейди; Лю, Цзычан; Пэн, Бинхуэй; Сюй, Чжаочжуо; Ли, Джонатан Линджи; Дао, Три; Песня, Чжао; Шривастава, Аншумали; Ре, Кристофер (2021 г.), «MONGOOSE: обучаемая структура LSH для эффективного обучения нейронной сети» , Международная конференция по обучению репрезентации

[15] Оливер, Джонатан; Ченг, Чун; Чен, Yanggui (2013), "ТЛШ - местность чувствительного хэш" , четвёртая Киберпреступность и Trustworthy Computing семинар , DOI : 10,1109 / CTC.2013.9 , ISBN 978-1-4799-3076-0

[Broder1998-16] Бродер, Аризона ; Чарикар, М .; Frieze, AM ; Митценмахер М. (1998). «Минимальные независимые перестановки» . Материалы тридцатого ежегодного симпозиума ACM по теории вычислений . С. 327–336. CiteSeerX 10.1.1.409.9220 . DOI : 10.1145 / 276698.276781 . Проверено 14 ноября 2007 .

[17] Takei, Y .; Ито, Т .; Шинозаки, Т. "Оптимальное построение точно минимально независимых перестановок". Технический отчет COMP98-62, IEICE, 1998 .

[Matousek2002-18] Matoušek , J .; Стоякович, М. (2002). «Об ограниченной миниатюрной независимости перестановок» . Препринт . Проверено 14 ноября 2007 .

[Saks2000-19] Сакс, М .; Srinivasan, A .; Чжоу, S .; Цукерман, Д. (2000). «Наборы с низким расхождением дают приблизительные по минимуму независимые семейства перестановок» . Письма об обработке информации . 73 (1–2): 29–32. CiteSeerX 10.1.1.20.8264 . DOI : 10.1016 / S0020-0190 (99) 00163-5 . Проверено 14 ноября 2007 .

[20] Дамиани; и другие. (2004). «Методика обнаружения спама на основе открытого дайджеста» (PDF) . Проверено 1 сентября 2013 .

[21] Оливер; и другие. (2013). «TLSH - хеш, чувствительный к местности» . 4-й семинар по киберпреступности и надежным вычислениям . Проверено 6 апреля 2015 .

[22] "ТЛШ" . Проверено 10 апреля 2014 .

[Andoni2008-23] Александр Андони; Индык, П. (2008). «Почти оптимальные алгоритмы хеширования для приближенного ближайшего соседа в больших размерностях». Коммуникации ACM . 51 (1): 117–122. CiteSeerX 10.1.1.226.6905 . DOI : 10.1145 / 1327452.1327494 . S2CID 6468963 .

[DIIM04-24] Датар, М .; Immorlica, N .; Indyk, P .; Миррокни, VS (2004). «Схема хеширования с учетом местоположения на основе p-стабильных распределений» . Материалы симпозиума по вычислительной геометрии .

[PJA10-25] Pauleve, L .; Jegou, H .; Амсалег, Л. (2010). «Хеширование с учетом местоположения: сравнение типов хэш-функций и механизмов запросов» . Письма о распознавании образов . 31 (11): 1348–1358. DOI : 10.1016 / j.patrec.2010.04.004 .

[26] Горман, Джеймс и Джеймс Р. Карран. «Масштабирование дистрибутивного сходства с большими корпусами». Материалы 21-й Международной конференции по компьютерной лингвистике и 44-го ежегодного собрания Ассоциации компьютерной лингвистики. Ассоциация компьютерной лингвистики, 2006.

[1]