Поиск ближайшего соседа битовой строки

Question

У меня есть сотни тысяч разреженных битовых строк длиной 32 бит.

Я хотел бы сделать поиск ближайшего соседа на них, и производительность поиска критическая. Я читал разные алгоритмы, но они, похоже, нацелены на текстовые строки, а не на двоичные строки. Я думаю, что либо локально чувствительное хэширование, либо спектральное хеширование кажутся хорошими кандидатами, или я мог бы рассмотреть сжатие. Будет ли кто-нибудь из них работать хорошо для моей проблемы с битовой строкой? Будем очень благодарны за любое руководство или руководство.

Answer 1

Вот быстрый и простой способ, , а затем вариант с лучшей производительностью за счет большей памяти.

В: массив Uint X [], например. 1M 32-битные слова
Требуются: функция near(Uint q) -> J с малым методом hammingdist(q, X[j])
: бинарный поиск q в отсортированном X, затем линейный поиск блока вокруг этого.
псевдокод:

def near(q, X, Blocksize=100): 
    preprocess: sort X 
    Uint* p = binsearch(q, X) # match q in leading bits 
    linear-search Blocksize words around p 
    return the hamming-nearest of these. 

Это быстро - Binary search 1M слова + ближайший hammingdist в блоке размером 100 занимает < 10 мкс на моем Mac РРС. (Это очень кэш-зависимых — ваш пробег будет отличаться.)

Как близко ли это прийти к поиску истинного ближайший X [J]? Я могу только экспериментировать, не могу выполнить математику:
для 1M случайных запросов в 1M случайных словах, Ближайшее совпадение на среднем расстоянии 4-5 бит, против 3 прочь для истинного ближайшего (линейное сканирование все 1M):

near32 N 1048576 Nquery 1048576 Blocksize 100 
binary search, then nearest +- 50 
7 usec 
distance distribution: 0 4481 38137 185212 443211 337321 39979 235 0 

near32 N 1048576 Nquery 100 Blocksize 1048576 
linear scan all 1048576 
38701 usec 
distance distribution: 0 0 7 58 35 0 

Запуск данных с помощью размера блока, скажем, 50 и 100 , чтобы увидеть, как спичечные расстояния падение.

---

Чтобы получить еще ближе, за счет удвоенной памяти,
сделать копию Xswap из X с верхними/нижними полусловами местами, и вернуть лучшее из

near(q, X, Blocksize) 
near(swap q, Xswap, Blocksize) 

С большим количеством памяти, можно использовать еще много бит-перетасованных копий X, например 32 оборота.
Я понятия не имею, как производительность меняется с Nshuffle и Blocksize — вопрос для теоретиков ЛСН.

---

(Добавлено): Для почти спичечных битовых строк говорят 320 бит, 10 слов, сделать 10 массивов указателей, отсортированные на слово 0, слово 1 ... и поиска блоков с binsearch, как описано выше:

nearest(query word 0, Sortedarray0, 100) -> min Hammingdist e.g. 42 of 320 
nearest(query word 1, Sortedarray1, 100) -> min Hammingdist 37 
nearest(query word 2, Sortedarray2, 100) -> min Hammingdist 50 
... 
-> e.g. the 37. 

Это, конечно, пропустить около-матчей, где нет ни одного слова не близко, , но это очень просто, и сортировать и binsearch являются невероятно быстро. Массивы указателей занимают столько же места, сколько бит данных. 100 слов, 3200 бит будут работать точно так же.
Но: это работает, только если имеется примерно одинаковое количество 0 бит и 1 бит, не 99% 0 бит.

Answer 2

Я только что наткнулся на бумагу, которая решает эту проблему.

Randomized algorithms and NLP: using locality sensitive hash function for high speed noun clustering (Ravichandran и др 2005)

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

Фактически это реализовано в https://github.com/soundcloud/cosine-lsh-join-spark, где я его нашел.