У меня есть около 100 миллионов числовых векторов (отпечатки Minhash), каждый вектор содержит 100 целых чисел от 0 до 65536. , и я пытаюсь выполнить быстрый поиск сходства в этой базе данных отпечатков пальцев, используя сходство Jaccard, то есть, учитывая вектор запроса (например, [1,0,30, 9, 42,...]), найдите отношение пересечения/объединения этого набора запросов к базе данных из 100 миллионов наборов.
Требование состоит в том, чтобы вернуть k «ближайших соседей» вектора запроса за ‹1 секунду (не включая время индексирования/ввода файла) на ноутбуке. Таким образом, очевидно, что требуется какая-то индексация, и вопрос заключается в том, какой подход будет наиболее эффективным.
примечания: я думал об использовании SimHash, но в этом случае на самом деле нужно знать размер пересечения наборов для идентификации сдерживание, а не чистое сходство/подобие, но Симхэш потерял бы эту информацию.
Я пробовал использовать простой метод хеширования с учетом местоположения, как описано в главе 3 Джеффри Уллмана, разделив каждый вектор на 20 "полос" или фрагментов длиной 5, преобразовав эти фрагменты в строки (например, [1, 2, 45, 2, 3] -> "124523") и используя эти строки в качестве ключей в хэш-таблице, где каждый ключ содержит "соседей-кандидатов". Но проблема в том, что это создает слишком много кандидатов для некоторых из этих фрагментов, и изменение количества полос не помогает.
