В информатике хеширование с учетом местоположения ( LSH ) - это алгоритмический метод, который с высокой вероятностью хэширует аналогичные входные элементы в одни и те же «корзины». [1] (Количество сегментов намного меньше, чем набор возможных входных элементов.) [1] Поскольку похожие элементы попадают в одни и те же сегменты, этот метод можно использовать для кластеризации данных и поиска ближайшего соседа . Он отличается от обычных методов хеширования тем, что конфликты хеширования максимизируются, а не минимизируются. В качестве альтернативы эту технику можно рассматривать как способ уменьшить размерностьмногомерных данных; элементы ввода с высокой размерностью могут быть уменьшены до версий с меньшей размерностью, сохраняя при этом относительные расстояния между элементами.
Алгоритмы приблизительного поиска ближайшего соседа на основе хеширования обычно используют одну из двух основных категорий методов хеширования: либо методы, не зависящие от данных, такие как хеширование с учетом местоположения (LSH); или методы, зависящие от данных, такие как хеширование с сохранением местоположения (LPH). [2] [3]
Определения
LSH семьи [1] [4] [5]определено для метрического пространства , порог и коэффициент приближения . Эта семья это семейство функций которые отображают элементы из метрического пространства в сегменты . Семейство LSH удовлетворяет следующим условиям для любых двух точек, используя функцию который выбирается равномерно случайным образом:
- если , тогда (т. е. p и q сталкиваются) с вероятностью не менее,
- если , тогда с вероятностью самое большее .
Семья интересна, когда . Такая семья называется -чувствительный .
В качестве альтернативы [6] он определен по отношению к вселенным элементам U , которые имеют сходство функции. Схема LSH - это семейство хэш-функций H в сочетании с распределением вероятностей D по функциям, таким что функциявыбранный согласно D, удовлетворяет тому свойству, что для любой .
Хеширование с сохранением местоположения
Сохраняющее локальность хеширование - это хеш-функция f, которая отображает точку или точки в многомерном координатном пространстве в скалярное значение, так что если у нас есть три точки A , B и C, такие что
Другими словами, это хеш-функции, в которых относительное расстояние между входными значениями сохраняется в относительном расстоянии между выходными хеш-значениями; входные значения, которые находятся ближе друг к другу, будут производить выходные хеш-значения, которые ближе друг к другу.
Это контрастирует с криптографическими хэш-функциями и контрольными суммами , которые предназначены для получения случайной разности выходных данных между соседними входами .
Хэши, сохраняющие локальность, связаны с кривыми заполнения пространства . [ как? ]
Усиление
Учитывая -чувствительная семья , мы можем построить новые семьи с помощью конструкции И или конструкции ИЛИ . [1]
Чтобы создать И-конструкцию, мы определяем новое семейство хэш-функций g , где каждая функция g построена из k случайных функций из . Затем мы говорим, что для хеш-функции, если и только если все для . Поскольку члены самостоятельно выбираются для любых , это -чувствительная семья.
Для создания OR-конструкции мы определяем новое семейство хэш-функций g , где каждая функция g построена из k случайных функций из . Затем мы говорим, что для хеш-функции, если и только если для одного или нескольких значений i . Поскольку члены самостоятельно выбираются для любых , это -чувствительная семья.
Приложения
LSH был применен к нескольким проблемным областям, включая:
- Обнаружение почти дубликатов [7]
- Иерархическая кластеризация [8] [9]
- Полногеномное ассоциативное исследование [10]
- Идентификация сходства изображений
- Идентификация сходства экспрессии генов [ необходима ссылка ]
- Идентификация звукового сходства
- Поиск ближайшего соседа
- Отпечаток аудио [11]
- Цифровое видео отпечатков пальцев
- Физическая организация данных в системах управления базами данных [12]
- Обучение полносвязных нейронных сетей [13] [14]
- Компьютерная безопасность [15]
Методы
Битовая выборка для расстояния Хэмминга
Один из самых простых способов создать семейство LSH - это побитовая выборка. [5] Этот подход работает для расстояния Хэмминга над d-мерными векторами.. Здесь семья хеш-функций - это просто семейство всех проекций точек на одну из координаты, т. е. , где это -я координата . Случайная функция из просто выбирает случайный бит из точки ввода. Это семейство имеет следующие параметры:, . [ требуется разъяснение ]
Минимальные независимые перестановки
Пусть U состоит из подмножеств некоторого основного множества ПЕРЕЧИСЛИМЫХ элементов S и функции подобия интереса представляет Jaccard индекс J . Если π - перестановка индексов S , для позволять . Каждый возможный выбор П определяет один хэш - функции ч входных наборов отображения к элементам S .
Определим семейство функций H как набор всех таких функций и пусть D будет равномерным распределением . Учитывая два набора событие, которое в точности соответствует тому событию, когда минимизатор π над лежит внутри . Поскольку h выбиралось равномерно случайным образом, а также определить схему LSH для индекса Жаккара.
Поскольку симметричная группа на n элементах имеет размер n !, выбор действительно случайной перестановки из полной симметричной группы невозможен даже для среднего размера n . Из-за этого факта была проведена значительная работа по поиску семейства перестановок, которое "не зависит от минимума" - семейства перестановок, для которого каждый элемент области имеет равную вероятность быть минимальным при случайно выбранном π . Было установлено, что минимально независимое семейство перестановок имеет размер не менее, [16] и что эта оценка точная. [17]
Поскольку минимально независимые семейства слишком велики для практических приложений, вводятся два варианта понятия минимальной независимости: ограниченные минимально независимые семейства перестановок и приблизительные минимально независимые семейства. Ограниченная минимальная независимость - это свойство минимальной независимости, ограниченное некоторыми наборами мощности не более k . [18] Приближенная минимальная независимость отличается от свойства не более чем на фиксированное ε . [19]
Методы с открытым исходным кодом
Нильсимса Хаш
Nilsimsa - это алгоритм хеширования, зависящий от местности, используемый в усилиях по борьбе со спамом . [20] Цель Nilsimsa - создать хэш-дайджест сообщения электронной почты, чтобы дайджесты двух похожих сообщений были похожи друг на друга. В статье предполагается, что Нильсимса удовлетворяет трем требованиям:
- Дайджест, идентифицирующий каждое сообщение, не должен существенно отличаться от изменений, которые могут производиться автоматически.
- Кодирование должно быть устойчивым к преднамеренным атакам.
- Кодировка должна поддерживать чрезвычайно низкий риск ложных срабатываний.
TLSH
TLSH - это алгоритм хеширования с учетом местоположения, разработанный для ряда приложений безопасности и цифровой криминалистики. [21] Цель TLSH - генерировать хеш-дайджесты для сообщений, чтобы небольшие расстояния между дайджестами указывали на то, что соответствующие им сообщения, вероятно, будут похожими.
Тестирование, проведенное в статье на ряде типов файлов, показало, что хэш Nilsimsa имеет значительно более высокий уровень ложных срабатываний по сравнению с другими схемами дайджеста сходства, такими как TLSH, Ssdeep и Sdhash.
Реализация TLSH доступна как программное обеспечение с открытым исходным кодом . [22]
Случайная проекция
Случайный метод проекции LSH в связи с Moses Чарикаром [6] называется SimHash (также иногда называемый агссоз [23] ) предназначен для аппроксимации расстояния косинуса между векторами. Основная идея этого метода состоит в том, чтобы выбрать случайную гиперплоскость (определяемую нормальным единичным вектором r ) в самом начале и использовать гиперплоскость для хеширования входных векторов.
Для входного вектора v и гиперплоскости, определяемой r , мы положим. Это,в зависимости от того, с какой стороны лежит гиперплоскость v .
Каждый возможный выбор r определяет одну функцию. Пусть H - множество всех таких функций, и пусть D - снова равномерное распределение. Нетрудно доказать, что для двух векторов, , где угол между u и v . тесно связан с .
В этом случае хеширование дает только один бит. Биты двух векторов совпадают с вероятностью, пропорциональной косинусу угла между ними.
Стабильные дистрибутивы
Хэш-функция [24] отображает d- мерный векторна множество целых чисел. Каждая хеш-функция в семействе индексируется путем случайного выбора. а также где является d- мерным вектором, элементы которого выбираются независимо от устойчивого распределения, и- действительное число, равномерно выбираемое из диапазона [0, r]. Для фиксированного хеш-функция дан кем-то .
Для лучшего соответствия данным были предложены другие методы построения хэш-функций. [25] В частности, хеш-функции k-средних на практике лучше, чем хеш-функции на основе проекций, но без каких-либо теоретических гарантий.
LSH алгоритм поиска ближайшего соседа
Одним из основных приложений LSH является обеспечение метода эффективных алгоритмов поиска ближайшего ближайшего соседа . Рассмотрим семейство LSH. Алгоритм имеет два основных параметра: ширину параметра K и количество хэш - таблицы L .
На первом этапе мы определяем новую семью хэш-функций g , где каждая функция g получается объединением k функций из , т.е. . Другими словами, случайная хеш-функция g получается конкатенацией k случайно выбранных хеш-функций из. Затем алгоритм создает L хэш-таблиц, каждая из которых соответствует разной случайно выбранной хеш-функции g .
На этапе предварительной обработки мы хэшируем все n точек из набора данных S в каждую из L хэш-таблиц. Учитывая, что в результирующих хэш-таблицах есть только n ненулевых записей, можно уменьшить объем памяти, используемый для каждой хеш-таблицы, дос использованием стандартных хеш-функций .
Для заданной точки запроса q алгоритм перебирает L хэш-функций g . Для каждого рассматриваемого g он извлекает точки данных, которые хешируются в ту же корзину, что и q . Процесс останавливается, как только точка на расстояниииз q находится.
При заданных параметрах k и L алгоритм имеет следующие гарантии работоспособности:
- время предварительной обработки: , где t - время вычисления функциина входной точке p ;
- космос: , плюс место для хранения точек данных;
- время запроса: ;
- алгоритму удается найти точку на расстоянии от q (если существует точка на расстоянии R ) с вероятностью не менее;
Для фиксированного отношения аппроксимации и вероятности а также , можно установить а также , где . Тогда получаются следующие гарантии производительности:
- время предварительной обработки: ;
- космос: , плюс место для хранения точек данных;
- время запроса: ;
Смотрите также
- Фильтр Блума
- Проклятие размерности
- Хеширование функций
- Преобразования, связанные с Фурье
- 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) .
- ^ а б Индик, Петр .; Мотвани, Раджив . (1998). «Приблизительные ближайшие соседи: к снятию проклятия размерности». . Материалы 30-го симпозиума по теории вычислений .
- ^ а б Чарикар, Моисей С. (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