Структура данных для поиска близлежащих ключей с похожими значениями

Question

У меня есть некоторые данные, до миллиона или миллиардов записей, каждая из которых представлена ​​битовым полем, около 64 бит на ключ. Биты независимы, вы можете представить их в основном как случайные биты.

Если у меня есть тестовый ключ, и я хочу найти все значения в моих данных с одним и тем же ключом, хеш-таблица очень легко выведет их в O (1).

Какой алгоритм / структура данных будет эффективно находить все записи, наиболее похожие на ключ запроса? Здесь подобное означает, что большинство битов идентичны, но допустимо, чтобы минимальное число было неправильным. Это традиционно измеряется расстоянием Хэмминга. , которое просто подсчитывает количество несовпадающих битов.

Есть два способа сделать этот запрос, один из них может быть задан частотой несоответствия, например «дать мне список всех существующих ключей, которые имеют менее 6 бит, которые отличаются от моего запроса» или просто наилучшими совпадениями, например « дайте мне список из 10000 ключей, у которых наименьшее количество битов отличается от моего запроса. "

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

Проблема может быть решена простым тестированием методом грубой силы для хеш-таблицы на малое количество различных битов. Например, если мы хотим найти все ключи, которые отличаются на один бит от нашего запроса, мы можем перечислить все 64 возможных ключа и протестировать их все. Но это быстро взрывается, если мы хотим разрешить два бита разницы, то нам придется исследовать 64 * 63 = 4032 раза. Это становится экспоненциально хуже для больших количеств битов.

Так есть ли другая структура данных или стратегия, которая делает такой запрос более эффективным? База данных / структура может быть предварительно обработана столько, сколько вам нужно, это скорость запроса, которая должна быть оптимизирована.

Answer 1

То, что вы хотите, это BK-Tree . Это дерево, которое идеально подходит для индексации метрических пространств (ваша проблема одна), и поддерживает запросы как ближайшего соседа, так и расстояния. Я написал статью об этом некоторое время назад.

BK-деревья обычно описываются со ссылкой на текст и с использованием расстояния Левенштейна для построения дерева, но написать его в терминах двоичных строк и расстояния Хэмминга просто.

Answer 2

Создайте двоичное дерево (в частности, trie ), представляющее каждый ключ в вашем начальном наборе следующим образом: Корневой узел - это пустое слово, перемещение по дереву влево, добавление 0 и перемещение справа внизу добавляется 1. В дереве будет только столько листьев, сколько в вашем стартовом наборе есть элементы, поэтому размер должен оставаться управляемым.

Теперь вы можете выполнить рекурсивный обход этого дерева, допуская не более n «отклонений» от ключа запроса в каждой рекурсивной строке выполнения, пока не найдете все узлы в начальном наборе, которые находятся в пределах этого числа отклонения.

Answer 3

Это звучит как хорошая подгонка для S-Tree, которое похоже на иерархически инвертированный файл. Хорошие ресурсы по этой теме включают следующие статьи:

Иерархический индекс растровых изображений: эффективный и масштабируемый метод индексации для заданных значений атрибутов.

Усовершенствованные методы построения дерева подписей (2000)

Цитата из первого:

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

В этих статьях содержатся ссылки на другие исследования, которые могут оказаться полезными, например, M-Trees .

Answer 4

База данных / структура может быть предварительно обработано как сколько угодно

Ну ... ЕСЛИ это правда. Тогда все, что вам нужно, это матрица сходства ваших расстояний Хэмминга. Сделайте матрицу разреженной, обрезая большие расстояния. Это не становится быстрее и не так уж сильно бьет по памяти.

Answer 5

«Почти оптимальные алгоритмы хеширования для приближенного ближайшего соседа в больших измерениях» , начиная с 2008 года, кажется лучшим результатом на тот момент. Я не буду пытаться подвести итог, так как я прочитал это больше года назад, и это волосатое. Это со страницы хеширования, чувствительного к локальности , вместе с реализацией более ранней версии схемы. Для более общих указаний, прочитайте поиск ближайшего соседа .

Этот вопрос задавался ранее: Самый быстрый способ найти наиболее похожую строку для ввода?

Answer 6

Я бы пошел с инвертированным индексом , как поисковая система. У вас в основном есть фиксированный словарный запас из 64 слов. Затем сходство измеряется расстоянием Хэмминга, а не косинусным сходством, которое бы хотела использовать поисковая система. Построение индекса будет медленным, но вы должны иметь возможность запрашивать его с нормальной скоростью поисковых систем.

Книга Введение в поиск информации охватывает эффективное построение, хранение, сжатие и запрос инвертированных индексов.

Answer 7

Если вы в порядке вероятностного выполнения, я думаю, что есть хороший способ решить вопрос 2. Я предполагаю, что у вас есть 2 ^ 30 данных и cutoff, и вы хотите найти все точки в пределах cutoff расстояния от test.

One_Try()
    1. Generate randomly a 20-bit subset S of 64 bits
    2. Ask for a list of elements that agree with test on S (about 2^10 elements)
    3. Sort that list by Hamming distance from test 
    4. Discard the part of list after cutoff

Вы повторяете One_Try столько, сколько вам нужно при объединении списков. Чем больше у вас попыток, тем больше очков вы найдете. Например, если x находится в пределах 5 битов, вы найдете его за одну попытку с вероятностью (2/3) ^ 5 = 13%. Поэтому, если вы повторите 100 попыток, вы найдете почти 10 ^ {- 6} таких x. Провел на форуме: 100*(1000*log 1000).

Основным преимуществом этого является то, что вы можете выводить ответы на вопрос 2 по ходу работы, поскольку после первых нескольких попыток вы наверняка найдете все на расстоянии не более 3 бит и т. Д.

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

Answer 8

Предполагая, что вам нужно посетить каждую строку, чтобы проверить ее значение (или если вы индексируете битовое поле, а затем каждую запись индекса), тогда вы можете довольно эффективно написать реальный тест, используя

A xor B

Чтобы найти разностные биты, затем подсчитайте результат, используя методику, подобную this .

Это эффективно дает вам расстояние Хэмминга.

Поскольку это может компилировать до десятка инструкций за тест, это может выполняться довольно быстро.

Answer 9

• Структуры данных для больших наборов описаны здесь: Обнаружение почти дубликатов для веб-сканирования или
• в памяти: Джуди-массивы на sourceforge.net

Answer 10

Если у вас все в порядке с рандомизированным алгоритмом (в данном случае Монте-Карло), вы можете использовать minhash