LSH не объединяет ни целые документы, ни отдельные минхэши. Скорее, он объединяет «полосы» минхэшей.
LSH — это средство как для уменьшения количества хэшей, хранящихся на документ, так и для уменьшения количества попаданий, найденных при использовании этих хэшей для поиска похожих документов. Это достигается путем объединения нескольких минхэшей в один хэш. Так, например, вместо того, чтобы хранить 200 минихэшей в документе, вы можете объединить их в группы по четыре, чтобы получить 50 хэшей, зависящих от местоположения.
Хеш для каждой полосы вычисляется из составляющих ее минхэшей с использованием дешевой хэш-функции, такой как FNV-1a. При этом теряется часть информации, поэтому говорят, что LSH уменьшает размерность данных. Полученный хэш и есть ведро.
Таким образом, ведро для каждой группы минхэшей в документе рассчитывается без знания каких-либо других групп или любых других документов.
Использовать хэши LSH для поиска похожих документов очень просто: допустим, вы хотите найти документы, похожие на документ А. Сначала сгенерируйте (например) 50 хэшей LSH для документа А. Затем посмотрите в своем хеш-словаре все другие документы, которые используют один или несколько таких хэшей. Чем больше общих хэшей они используют, тем выше предполагаемое сходство жаккардов (хотя это не линейная зависимость, как при использовании простых минхэшей).
Чем меньше общих хэшей сохраняется для каждого документа, тем больше ошибка в расчетном сходстве жаккара и тем выше вероятность пропуска похожих документов.
Вот хорошее объяснение LSH.
person
Ben Whitmore
schedule
09.07.2019
