MinHash

В информатике и анализе данных , MinHash (или мин-накрест независимые перестановки н.п. чувствительного хеширования схема) представляет собой метод для быстрой оценки , как аналогичные два множества. Схема была изобретена Андреем Бродером ( 1997 ), ^[1] и первоначально использовалась в поисковой системе AltaVista для обнаружения повторяющихся веб-страниц и исключения их из результатов поиска. ^[2] Он также применялся в крупномасштабных задачах кластеризации , таких как кластеризация документов по схожести их наборов слов. ^[1]

Сходство Жаккарда и минимальные хеш-значения [ править ]

Коэффициент подобия Жаккара - часто используемый индикатор сходства между двумя наборами. Пусть $U$ - множество, а $A$ и $B$ - подмножества $U$ , тогда индекс Жаккара определяется как отношение количества элементов их пересечения и количества элементов их объединения :

{\ Displaystyle J (A, B) = {{| A \ cap B |} \ над {| A \ cup B |}}.}

Это значение равно 0, когда два набора не пересекаются , 1, когда они равны, и строго между 0 и 1 в противном случае. Два набора более похожи (то есть имеют относительно больше общих членов), когда их индекс Жаккара ближе к 1. Цель MinHash - быстро оценить $J (A, B)$ без явного вычисления пересечения и объединения.

Пусть $h$ - хэш-функция, которая отображает элементы $U$ в различные целые числа, пусть $perm$ - случайная перестановка элементов множества $U$ , и для любого множества $S$ определим $h min (S)$ как минимальный член $S$ относительно to $h \circ perm$ - то есть член $x$ группы $S$ с минимальным значением $h (perm (x))$ . (В случаях, когда предполагается, что используемая хеш-функция имеет псевдослучайные свойства, случайная перестановка использоваться не будет.)

Теперь, применяя $h min$ как к $A, так$ и к $B$ , и предполагая отсутствие хэш-коллизий, мы видим, что значения равны ( $h min (A) = h min (B)$ ) тогда и только тогда, когда среди всех элементов , элемент с минимальное значение хеш-функции лежит на пересечении . Вероятность того, что это правда, и есть индекс Жаккара, поэтому: ${\ Displaystyle A \ чашка B}$ ${\ displaystyle A \ cap B}$

Pr [h min (A) = h min (B)] = J (A, B),

То есть вероятность того, что $h min (A) = h min (B)$ истинно, равна подобию $J (A, B)$ , предполагая получение $химической завивки$ из равномерного распределения. Другими словами, если $г$ является случайной величиной , которая является одной , когда $ч мин ( ) = ч мин (Б)$ и ноль в противном случае, то $г$ является несмещенной оценкой из $J (А, Б)$ . $r$ имеет слишком большую дисперсию, чтобы быть полезной оценкой подобия Жаккара само по себе, потому чтовсегда равно нулю или единице. Идея схемы MinHash состоит в том, чтобы уменьшить эту дисперсию путем усреднения нескольких переменных, созданных таким же образом. ${\ displaystyle r}$

Алгоритм [ править ]

Вариант со множеством хеш-функций [ править ]

Простейшая версия схемы minhash использует $k$ различных хэш-функций, где $k$ - фиксированный целочисленный параметр, и представляет каждый набор $S$ посредством $k$ значений $h min (S)$ для этих $k$ функций.

Чтобы оценить $J (A, B)$ с использованием этой версии схемы, пусть $y$ будет количеством хеш-функций, для которых $h min (A) = h min (B)$ , и используйте $y / k$ в качестве оценки. Эта оценка представляет собой среднее значение $k$ различных 0-1 случайных величин, каждая из которых равна единице, когда $h min (A) = h min (B),$ и нулю в противном случае, и каждая из которых является несмещенной оценкой $J (А, Б)$ . Следовательно, их среднее значение также является несмещенной оценкой, и по стандартному отклонению для сумм от 0 до 1 случайных величин его ожидаемая ошибка составляет $O (1 / \sqrt k)$ . ^[3]

Следовательно, для любой константы $ε> 0$ существует константа $k = O (1 / ε 2)$ такая, что ожидаемая ошибка оценки не $превосходит ε$ . Например, для оценки $J (A, B)$ с ожидаемой ошибкой, меньшей или равной 0,05, потребуется 400 хешей .

Вариант с единственной хеш-функцией [ править ]

Вычисление нескольких хеш-функций может быть дорогостоящим в вычислительном отношении, но связанная версия схемы MinHash позволяет избежать этого штрафа, используя только одну хеш-функцию и использует ее для выбора нескольких значений из каждого набора, а не для выбора только одного минимального значения для каждой хеш-функции. Пусть $h$ - хэш-функция, а $k$ - фиксированное целое число. Если $S$ - это любой набор из $k$ или более значений в области $h$ , определите $h (k) (S)$ как подмножество из $k$ членов $S,$ которые имеют наименьшие значения $h$ . Это подмножество $h (k) (S)$ используется в качествесигнатурыдля множества $S$ , и сходство любых двух множеств оценивается путем сравнения их сигнатур.

В частности, пусть A и B - любые два набора. Тогда $X = h (k) (h (k) (A) \cup h (k) (B)) = h (k) (A \cup B)$ является набором из k элементов $A \cup B$ , и если h является случайная функция, то с равной вероятностью будет выбрано любое подмножество из k элементов; то есть $X$ являетсяпростая случайная выборка из $\cup$ $B$ . Подмножество $Y$ $=$ $X$ $\cap$ $H$ $($ $K$ $)$ $($ $) \cap$ $ч$ $($ $к$ $)$ $($ $Б$ $)$ представляет собой набор членов $X$ , которые принадлежат к пересечению $\cap$ $B$ . Следовательно, | $Y$ | / $k$ - несмещенная оценка $J$ $($ $A$ $,$ $B$ $)$ . Разница между этим оценщиком и оценщиком, созданным несколькими хеш-функциями, состоит в том, что $X$ всегда имеет ровно $k$ членов, тогда как несколько хеш-функций могут привести к меньшему количеству выбранных элементов из-за возможности того, что две разные хеш-функции могут иметь одинаковые минимумы. Однако, когда $k$ мало по сравнению с размерами наборов, эта разница незначительна.

По стандартным границам Чернова для выборки без замены, эта оценка имеет ожидаемую ошибку $O (1 / \sqrt k)$ , что соответствует производительности схемы множественных хеш-функций.

Анализ времени [ править ]

Оценщик $| Y | / k$ может быть вычислено за время $O (k)$ из двух сигнатур данных наборов в любом варианте схемы. Следовательно, когда $ε$ и $k$ являются постоянными, время для вычисления оценки подобия по сигнатурам также остается постоянным. Сигнатура каждого набора может быть вычислена за линейное время по размеру набора, поэтому, когда необходимо оценить много попарных сходств, этот метод может привести к значительной экономии времени выполнения по сравнению с выполнением полного сравнения элементов каждого набора. . В частности, для заданного размера $n$ вариант с множеством хешей занимает $O (n k)$ время. Вариант с одним хешем обычно быстрее, требуя времени $O (n)$ для поддержания очереди с минимальными значениями хеширования, предполагая, что $n >> k$ . ^[1]

Добавление весов [ править ]

Были разработаны различные методы введения весов в вычисление MinHash. Самый простой расширяет его до целых весов. ^[4] Расширьте нашу хеш-функцию $h,$ чтобы она принимала как член набора, так и целое число, а затем сгенерируйте несколько хешей для каждого элемента в соответствии с его весом. Если элемент $i$ встречается $n$ раз, сгенерируйте хеши . Запустите исходный алгоритм на этом расширенном наборе хешей. Это дает взвешенный индекс Жаккара как вероятность столкновения. ${\ Displaystyle час (я, 1), час (я, 2), \ ldots, час (я, п)}$

${\ Displaystyle J _ {\ mathcal {W}} (x, y) = {\ frac {\ sum _ {i} \ min (x_ {i}, y_ {i})} {\ sum _ {i} \ max (x_ {i}, y_ {i})}}}$

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

Другое семейство расширений использует экспоненциально распределенные хэши. Равномерно случайный хеш от 0 до 1 может быть преобразован в экспоненциальное распределение путем инверсии CDF . Этот метод использует множество прекрасных свойств минимума набора экспоненциальных переменных .

$H(x)={\underset {i}{\operatorname {arg\,min} }}{\frac {-\log(h(i))}{x_{i}}}$

Это дает в качестве вероятности столкновения индекс Жаккара вероятности ^[7]

$J_{\mathcal {P}}(x,y)=\sum _{x_{i}\neq 0,y_{i}\neq 0}{\frac {1}{\sum _{j}\max \left({\frac {x_{j}}{x_{i}}},{\frac {y_{j}}{y_{i}}}\right)}}$

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

Для реализации схемы MinHash , как описано выше, нужно хэш - функции $ч$ , чтобы определить случайную перестановку на $п$ элементы, где $п$ есть общее число различных элементов в объединении всех наборов для сравнения. Но ведь их $нет!$ различных перестановок, потребуется $Ω (n log n)$ бит только для указания действительно случайной перестановки, недопустимо большого числа даже для умеренных значений $n$ . Из-за этого по аналогии с теорией универсального хеширования, была проделана значительная работа по поиску семейства перестановок, которое "не зависит от минимума", что означает, что для любого подмножества домена любой элемент с равной вероятностью будет минимальным. Было установлено, что минимально независимое семейство перестановок должно включать не менее

\operatorname {lcm} (1,2,\cdots ,n)\geq e^{n-o(n)}

различные перестановки, и, следовательно, для определения одной перестановки требуется $Ω (n)$ бит, что все еще недопустимо велико. ^[2]

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

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

Оригинальные приложения для MinHash включали кластеризацию и устранение почти дубликатов среди веб-документов, представленных в виде наборов слов, встречающихся в этих документах. ^[1]^[2]^[10] Подобные методы также использовались для кластеризации и почти полного исключения дубликатов для других типов данных, таких как изображения: в случае данных изображения изображение может быть представлено как набор меньших фрагментов изображений. вырезаны из него, или как наборы более сложных описаний функций изображения. ^[11]

В горнодобывающей промышленности данных , Коэн и др. (2001) использовали MinHash как инструмент для изучения правил ассоциации . Учитывая базу данных, в которой каждая запись имеет несколько атрибутов (рассматриваемая как матрица 0–1 со строкой для каждой записи и столбцом для каждого атрибута), они используют аппроксимации на основе MinHash к индексу Жаккарда для определения подходящих пар атрибутов, которые часто совпадают. возникают, а затем вычисляют точное значение индекса только для этих пар, чтобы определить те, частота совместного появления которых ниже заданного строгого порога. ^[12]

Алгоритм MinHash был адаптирован для биоинформатики, где проблема сравнения последовательностей геномов имеет те же теоретические основания, что и сравнение документов в сети. Инструменты на основе MinHash ^[13]^[14] позволяют быстро сравнивать данные секвенирования всего генома с эталонными геномами (около 3 минут для сравнения одного генома с 90000 эталонными геномами в RefSeq ) и подходят для видообразования и, возможно, ограниченной степени микробной подтип. Также существуют приложения для метагеномики ^[13] и использования алгоритмов, полученных из MinHash, для выравнивания генома и сборки генома. ^[15] Точные средние значения идентичности нуклеотидов (ANI) могут быть сгенерированы очень эффективно с помощью алгоритмов на основе MinHash.^[16]

Другое использование [ править ]

Схема MinHash может рассматриваться как пример хеширования с учетом местоположения , набора методов использования хеш-функций для сопоставления больших наборов объектов с меньшими значениями хеш-функции таким образом, что, когда два объекта находятся на небольшом расстоянии друг от друга, их хеш-значения, вероятно, будут одинаковыми. В этом случае подпись набора может рассматриваться как его хеш-значение. Для определения расстояния Хэмминга между наборами и косинусного расстояния между векторами существуют другие методы хеширования, чувствительные к локальности ; Хеширование с учетом местоположения имеет важные приложения в алгоритмах поиска ближайшего соседа . ^[17] Для больших распределенных систем, в частности MapReduce.существуют модифицированные версии MinHash, помогающие вычислять сходства независимо от размерности точки. ^[18]

Оценка и тесты [ править ]

Крупномасштабная оценка была проведена Google в 2006 году ^[19] для сравнения производительности алгоритмов Minhash и SimHash ^[20] . В 2007 году Google сообщил об использовании Simhash для обнаружения дубликатов при сканировании Интернета ^[21] и об использовании Minhash и LSH для персонализации новостей Google . ^[22]

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

Фильтр Блума
SimHash
шинглинг
Граф-мин эскиз

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

^ a b c d Бродер, Андрей З. (1997), "О сходстве и содержании документов", Сжатие и сложность последовательностей: Материалы, Позитано, Амальфитанское побережье, Салерно, Италия, 11-13 июня 1997 г. (PDF) , IEEE , стр 21-29,. CiteSeerX 10.1.1.24.779 , DOI : 10,1109 / SEQUEN.1997.666900 , ISBN 978-0-8186-8132-5, архивировано из оригинального (PDF) 31 января 2015 г. , архивировано 18 января 2014 г..
^ a b c Бродер, Андрей З .; Чарикар, Моисей; Frieze, Алан М .; Митценмахер, Майкл (1998), "Минимальные независимые перестановки", Proc. Тридцатые ACM симпозиум по теории вычислений (STOC '98) , Нью - Йорк, Нью - Йорк, США: Ассоциации вычислительной техники ., Стр 327-336, CiteSeerX 10.1.1.409.9220 , DOI : 10,1145 / 276698,276781 , ISBN 978-0897919623.
^ Vassilvitskii Сергей (2011), Coms 6998-12: Работа с массивными данных (конспектов, Колумбийский университет) (PDF) , Архивировано из оригинального (PDF) на 2018-10-24 .
^ Чум, Ондрей; Филбин, Джеймс; Зиссерман, Эндрю (2008), «Обнаружение почти повторяющихся изображений: минимальный хэш и tf-idf взвешивание». (PDF) , BMVC , 810 : 812–815.
^ Шривастава, Аншумали (2016), «Точное взвешенное минимальное хеширование за постоянное время», arXiv : 1602.08393 [ cs.DS ]
↑ Иоффе, Сергей (2010), «Улучшенная последовательная выборка, взвешенный minhash и создание эскизов l1» (PDF) , Data Mining (ICDM), 2010 IEEE Международная конференция : 246–255, CiteSeerX 10.1.1.227.9749 , doi : 10.1109 /ICDM.2010.80 , ISBN 978-1-4244-9131-5
^ Моултон, Райан; Цзян, Юньцзян (2018 г.), «Максимально согласованная выборка и индекс распределения вероятностей Жаккара», Международная конференция IEEE по интеллектуальному анализу данных (ICDM) 2018 г. , стр. 347–356, arXiv : 1809.04052 , doi : 10.1109 / ICDM.2018.00050 , ISBN 978-1-5386-9159-5
^ Матушек, Иржи ; Stojaković, Милош (2003), "О запретной мин-накрест независимости перестановок", Случайные структуры и алгоритмы , 23 (4): 397-408, CiteSeerX 10.1.1.400.6757 , DOI : 10.1002 / rsa.10101 .
^ Сакс, М .; Srinivasan, A .; Чжоу, S .; Цукерман, Д. (2000), «Множества с низким расхождением дают приблизительные по минимуму независимые семейства перестановок», Information Processing Letters , 73 (1-2): 29-32, CiteSeerX 10.1.1.20.8264 , doi : 10.1016 / S0020- 0190 (99) 00163-5 .
^ Манассе, Марк (2012). Об эффективном определении ближайших соседей: подковы, ручные гранаты, поиск в Интернете и другие ситуации, когда близко достаточно близко . Морган и Клейпул. п. 72. ISBN 9781608450886.
^ Чум, Ондржей; Филбин, Джеймс; Айсард, Майкл; Зиссерман, Эндрю (2007), «Масштабируемое обнаружение почти идентичных изображений и кадров », Труды 6-й Международной конференции ACM по поиску изображений и видео (CIVR'07) , стр. 549–556, doi : 10.1145 / 1282280.1282359 , ISBN 9781595937339; Чум, Ондржей; Филбин, Джеймс; Зиссерман, Эндрю (2008), «Обнаружение почти повторяющихся изображений: min-hash и tf-idf-взвешивание», Труды Британской конференции по машинному зрению (PDF) , 3 , стр. 4 .
^ Коэн, Э .; Датар, М .; Fujiwara, S .; Gionis, A .; Indyk, P .; Мотвани, Р .; Ullman, JD ; Ян К. (2001), «Поиск интересных ассоциаций без поддержки сокращения», IEEE Transactions on Knowledge and Data Engineering , 13 (1): 64–78, CiteSeerX 10.1.1.192.7385 , doi : 10.1109 / 69.908981 .
^ а б Ондов, Брайан Д .; Treangen, Todd J .; Мельстед, Палл; Мэллони, Адам Б.; Бергман, Николас Х .; Корень, Сергей; Филлиппи, Адам М. (2016-06-20). «Mash: быстрая оценка расстояния между геномами и метагеномами с использованием MinHash» . Геномная биология . 17 (1): 132. DOI : 10.1186 / s13059-016-0997-x . ISSN 1474-760X . PMC 4915045 . PMID 27323842 .
^ «Добро пожаловать в sourmash! - документация sourmash 1.0» . sourmash.readthedocs.io . Проверено 13 ноября 2017 .
^ Берлин, Константин; Корень, Сергей; Чин, Чен-Шань; Дрейк, Джеймс П.; Ландолин, Джейн М; Филлиппи, Адам М (25 мая 2015 г.). «Сборка больших геномов с помощью секвенирования одной молекулы и хеширования с учетом локализации». Природа Биотехнологии . 33 (6): 623–630. DOI : 10.1038 / nbt.3238 . ISSN 1546-1696 . PMID 26006009 .
^ Джайн, Чираг; Rodriguez-R, Luis M .; Филлиппи, Адам М .; Konstantinidis, Konstantinos T .; Алуру, Шринивас (декабрь 2018 г.). «Высокопроизводительный ANI-анализ 90K геномов прокариот выявляет четкие границы между видами» . Nature Communications . 9 (1): 5114. DOI : 10.1038 / s41467-018-07641-9 .
^ Андони, Александр; Indyk, Piotr (2008), "Почти оптимальные алгоритмы хеширования для приблизительного ближайшего соседа в больших измерениях", Коммуникации ACM , 51 (1): 117–122, CiteSeerX 10.1.1.226.6905 , doi : 10.1145 / 1327452.1327494 .
^ Заде, Реза; Гоэль, Ашиш (2012), «Вычисление подобия, не зависящее от размерности », arXiv : 1206.2082 [ cs.DS ].
^ Хенцингер, Моника (2006), «Поиск почти дублирующихся веб-страниц: крупномасштабная оценка алгоритмов», Труды 29-й ежегодной международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска , стр. 284 , DOI : 10.1145 / 1148170.1148222 , ISBN 978-1595933690.
^ Чарикар, Моисей С. (2002), "Методы оценки подобия на основе алгоритмов округления", Труды 34-го ежегодного симпозиума ACM по теории вычислений , стр. 380, DOI : 10,1145 / 509907,509965 , ISBN 978-1581134957.
^ Гермит Сингх, Manku; Джайн, Арвинд; Дас Сарма, Аниш (2007), «Обнаружение почти дубликатов для сканирования Интернета», Труды 16-й Международной конференции по всемирной паутине (PDF) , стр. 141, DOI : 10,1145 / 1242572,1242592 , ISBN 9781595936547.
^ Das, Abhinandan S .; Датар, Маюр; Гарг, Ашутош; Раджарам, Шьям; и другие. (2007), «Персонализация новостей Google: масштабируемая совместная фильтрация в Интернете», Труды 16-й Международной конференции по всемирной паутине , стр. 271, DOI : 10,1145 / 1242572,1242610 , ISBN 9781595936547.

[b97-1] Бродер, Андрей З. (1997), "О сходстве и содержании документов", Сжатие и сложность последовательностей: Материалы, Позитано, Амальфитанское побережье, Салерно, Италия, 11-13 июня 1997 г. (PDF) , IEEE , стр 21-29,. CiteSeerX 10.1.1.24.779 , DOI : 10,1109 / SEQUEN.1997.666900 , ISBN 978-0-8186-8132-5, архивировано из оригинального (PDF) 31 января 2015 г. , архивировано 18 января 2014 г..

[bcfm-2] Бродер, Андрей З .; Чарикар, Моисей; Frieze, Алан М .; Митценмахер, Майкл (1998), "Минимальные независимые перестановки", Proc. Тридцатые ACM симпозиум по теории вычислений (STOC '98) , Нью - Йорк, Нью - Йорк, США: Ассоциации вычислительной техники ., Стр 327-336, CiteSeerX 10.1.1.409.9220 , DOI : 10,1145 / 276698,276781 , ISBN 978-0897919623.

[3] Vassilvitskii Сергей (2011), Coms 6998-12: Работа с массивными данных (конспектов, Колумбийский университет) (PDF) , Архивировано из оригинального (PDF) на 2018-10-24 .

[4] Чум, Ондрей; Филбин, Джеймс; Зиссерман, Эндрю (2008), «Обнаружение почти повторяющихся изображений: минимальный хэш и tf-idf взвешивание». (PDF) , BMVC , 810 : 812–815.

[5] Шривастава, Аншумали (2016), «Точное взвешенное минимальное хеширование за постоянное время», arXiv : 1602.08393 [ cs.DS ]

[6] Иоффе, Сергей (2010), «Улучшенная последовательная выборка, взвешенный minhash и создание эскизов l1» (PDF) , Data Mining (ICDM), 2010 IEEE Международная конференция : 246–255, CiteSeerX 10.1.1.227.9749 , doi : 10.1109 /ICDM.2010.80 , ISBN 978-1-4244-9131-5

[7] Моултон, Райан; Цзян, Юньцзян (2018 г.), «Максимально согласованная выборка и индекс распределения вероятностей Жаккара», Международная конференция IEEE по интеллектуальному анализу данных (ICDM) 2018 г. , стр. 347–356, arXiv : 1809.04052 , doi : 10.1109 / ICDM.2018.00050 , ISBN 978-1-5386-9159-5

[8] Матушек, Иржи ; Stojaković, Милош (2003), "О запретной мин-накрест независимости перестановок", Случайные структуры и алгоритмы , 23 (4): 397-408, CiteSeerX 10.1.1.400.6757 , DOI : 10.1002 / rsa.10101 .

[9] Сакс, М .; Srinivasan, A .; Чжоу, S .; Цукерман, Д. (2000), «Множества с низким расхождением дают приблизительные по минимуму независимые семейства перестановок», Information Processing Letters , 73 (1-2): 29-32, CiteSeerX 10.1.1.20.8264 , doi : 10.1016 / S0020- 0190 (99) 00163-5 .

[10] Манассе, Марк (2012). Об эффективном определении ближайших соседей: подковы, ручные гранаты, поиск в Интернете и другие ситуации, когда близко достаточно близко . Морган и Клейпул. п. 72. ISBN 9781608450886.

[11] Чум, Ондржей; Филбин, Джеймс; Айсард, Майкл; Зиссерман, Эндрю (2007), «Масштабируемое обнаружение почти идентичных изображений и кадров », Труды 6-й Международной конференции ACM по поиску изображений и видео (CIVR'07) , стр. 549–556, doi : 10.1145 / 1282280.1282359 , ISBN 9781595937339; Чум, Ондржей; Филбин, Джеймс; Зиссерман, Эндрю (2008), «Обнаружение почти повторяющихся изображений: min-hash и tf-idf-взвешивание», Труды Британской конференции по машинному зрению (PDF) , 3 , стр. 4 .

[12] Коэн, Э .; Датар, М .; Fujiwara, S .; Gionis, A .; Indyk, P .; Мотвани, Р .; Ullman, JD ; Ян К. (2001), «Поиск интересных ассоциаций без поддержки сокращения», IEEE Transactions on Knowledge and Data Engineering , 13 (1): 64–78, CiteSeerX 10.1.1.192.7385 , doi : 10.1109 / 69.908981 .

[:0-13] а б Ондов, Брайан Д .; Treangen, Todd J .; Мельстед, Палл; Мэллони, Адам Б.; Бергман, Николас Х .; Корень, Сергей; Филлиппи, Адам М. (2016-06-20). «Mash: быстрая оценка расстояния между геномами и метагеномами с использованием MinHash» . Геномная биология . 17 (1): 132. DOI : 10.1186 / s13059-016-0997-x . ISSN 1474-760X . PMC 4915045 . PMID 27323842 .

[14] «Добро пожаловать в sourmash! - документация sourmash 1.0» . sourmash.readthedocs.io . Проверено 13 ноября 2017 .

[15] Берлин, Константин; Корень, Сергей; Чин, Чен-Шань; Дрейк, Джеймс П.; Ландолин, Джейн М; Филлиппи, Адам М (25 мая 2015 г.). «Сборка больших геномов с помощью секвенирования одной молекулы и хеширования с учетом локализации». Природа Биотехнологии . 33 (6): 623–630. DOI : 10.1038 / nbt.3238 . ISSN 1546-1696 . PMID 26006009 .

[16] Джайн, Чираг; Rodriguez-R, Luis M .; Филлиппи, Адам М .; Konstantinidis, Konstantinos T .; Алуру, Шринивас (декабрь 2018 г.). «Высокопроизводительный ANI-анализ 90K геномов прокариот выявляет четкие границы между видами» . Nature Communications . 9 (1): 5114. DOI : 10.1038 / s41467-018-07641-9 .

[17] Андони, Александр; Indyk, Piotr (2008), "Почти оптимальные алгоритмы хеширования для приблизительного ближайшего соседа в больших измерениях", Коммуникации ACM , 51 (1): 117–122, CiteSeerX 10.1.1.226.6905 , doi : 10.1145 / 1327452.1327494 .

[18] Заде, Реза; Гоэль, Ашиш (2012), «Вычисление подобия, не зависящее от размерности », arXiv : 1206.2082 [ cs.DS ].

[19] Хенцингер, Моника (2006), «Поиск почти дублирующихся веб-страниц: крупномасштабная оценка алгоритмов», Труды 29-й ежегодной международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска , стр. 284 , DOI : 10.1145 / 1148170.1148222 , ISBN 978-1595933690.

[20] Чарикар, Моисей С. (2002), "Методы оценки подобия на основе алгоритмов округления", Труды 34-го ежегодного симпозиума ACM по теории вычислений , стр. 380, DOI : 10,1145 / 509907,509965 , ISBN 978-1581134957.

[21] Гермит Сингх, Manku; Джайн, Арвинд; Дас Сарма, Аниш (2007), «Обнаружение почти дубликатов для сканирования Интернета», Труды 16-й Международной конференции по всемирной паутине (PDF) , стр. 141, DOI : 10,1145 / 1242572,1242592 , ISBN 9781595936547.

[22] Das, Abhinandan S .; Датар, Маюр; Гарг, Ашутош; Раджарам, Шьям; и другие. (2007), «Персонализация новостей Google: масштабируемая совместная фильтрация в Интернете», Труды 16-й Международной конференции по всемирной паутине , стр. 271, DOI : 10,1145 / 1242572,1242610 , ISBN 9781595936547.

[1]