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

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

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

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

Определения

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

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

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

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

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

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

В качестве альтернативы [8] можно определить семейство LSH на множестве элементов U, снабженном функцией подобия . В этом случае схема LSH представляет собой семейство хэш-функций H, связанных с распределением вероятностей D по H таким образом, что функция, выбранная в соответствии с D, удовлетворяет для каждого . ϕ : У × У → [ 0 , 1 ] {\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] ( г 1 , г 2 , п 1 , п 2 ) {\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}}} час 1 , … , час к {\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)} я = 1 , 2 , … , к {\displaystyle i=1,2,\ldots ,k} Ф {\displaystyle {\mathcal {F}}} г ∈ Г {\displaystyle g\in {\mathcal {G}}} Г {\displaystyle {\mathcal {G}}} ( г 1 , г 2 , п 1 к , п 2 к ) {\displaystyle (d_{1},d_{2},p_{1}^{k},p_{2}^{k})}

Чтобы создать OR-конструкцию, мы определяем новое семейство хэш-функций g , где каждая функция g строится из k случайных функций из . Затем мы говорим, что для хэш-функции , тогда и только тогда, когда для одного или нескольких значений i . Поскольку члены выбираются независимо для любого , является -чувствительным семейством. Г {\displaystyle {\mathcal {G}}} час 1 , … , час к {\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}}} ( г 1 , г 2 , 1 − ( 1 − п 1 ) к , 1 − ( 1 − п 2 ) к ) {\displaystyle (d_{1},d_{2},1-(1-p_{1})^{k},1-(1-p_{2})^{k})}

Приложения

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

Методы

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

Один из самых простых способов построения семейства LSH — это побитовая выборка. [7] Этот подход работает для расстояния Хэмминга по d -мерным векторам . Здесь семейство хеш-функций — это просто семейство всех проекций точек на одну из координат, т. е. , где — ая координата . Случайная функция из просто выбирает случайный бит из входной точки. Это семейство имеет следующие параметры: , . То есть любые два вектора с расстоянием Хэмминга не более сталкиваются под случайным с вероятностью не менее . Любые с расстоянием Хэмминга не менее сталкиваются с вероятностью не более . { 0 , 1 } г {\displaystyle \{0,1\}^{d}} Ф {\displaystyle {\mathcal {F}}} г {\displaystyle д} Ф = { час : { 0 , 1 } г → { 0 , 1 } ∣ час ( х ) = х я  для некоторых  я ∈ { 1 , … , г } } {\displaystyle {\mathcal {F}}=\{h\colon \{0,1\}^{d}\to \{0,1\}\mid h(x)=x_{i}{\text{ для некоторых }}i\in \{1,\ldots ,d\}\}} х я {\displaystyle x_{i}} я {\displaystyle я} х {\displaystyle x} час {\displaystyle ч} Ф {\displaystyle {\mathcal {F}}} П 1 = 1 − Р / г {\displaystyle P_{1}=1-R/d} П 2 = 1 − с Р / г {\displaystyle P_{2}=1-cR/d} х , у {\displaystyle x,y} Р {\displaystyle R} час {\displaystyle ч} П 1 {\displaystyle P_{1}} х , у {\displaystyle x,y} с Р {\displaystyle cR} П 2 {\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\чашка B} А ∩ Б {\displaystyle A\cap B} П г [ час ( А ) = час ( Б ) ] = Дж. ( А , Б ) {\displaystyle Pr[h(A)=h(B)]=J(A,B)\,} ( ЧАС , Д ) {\displaystyle (H,D)\,}

Поскольку симметрическая группа на n элементах имеет размер n !, выбор действительно случайной перестановки из полной симметрической группы невозможен даже для среднего размера n . Из-за этого факта была проделана значительная работа по поиску семейства перестановок, которое является «независимым относительно минимума» — семейства перестановок, для которого каждый элемент домена имеет равную вероятность быть минимальным при случайно выбранном π . Было установлено, что независимое относительно минимума семейство перестановок имеет по крайней мере размер , [19] и что эта граница является жесткой. [20] lcm ⁡ { 1 , 2 , … , n } ≥ e n − o ( n ) {\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]

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

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

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

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

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

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

P r [ h ( u ) = h ( v ) ] = 1 − θ ( u , v ) π . {\displaystyle Pr[h(u)=h(v)]=1-{\frac {\theta (u,v)}{\pi }}.}

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

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

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

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

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

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

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

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

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

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

Улучшения

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

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

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

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

Ссылки

  1. ^ abcd Раджараман, А.; Ульман, Дж. (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. ^ ab Chin, Andrew (1991). Проблемы сложности в параллельных вычислениях общего назначения (DPhil). Оксфордский университет. С. 87–95.
  5. ^ ab 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. ^ ab Indyk, Piotr .; Motwani, Rajeev . (1998). «Приближенные ближайшие соседи: на пути к устранению проклятия размерности». Труды 30-го симпозиума по теории вычислений .
  8. ^ abcd Чарикар, Мозес С. (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. ^ ab Оливер, Джонатан; Ченг, Чун; Чен, Янгуй (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. p 1 − 1 {\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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Locality-sensitive_hashing&oldid=1230930313"