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

Question

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

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

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

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

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

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

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

Answer 1

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

Вы можете разделить область поиска на несколько сегментов , где в каждом блоке есть ключ блока , а ключи в блоке - это ключи, которые больше похожи на этот блок. ключ, чем любой другой ключ ведра. Чтобы создать ключи корзины, вы можете случайным образом сгенерировать 64-битные ключи и отбросить любые, которые слишком близки к любому ранее созданному ключу корзины, или разработать алгоритм, который генерирует ключи, которые достаточно различны. Чтобы найти ближайший ключ к тестовому ключу, сначала найдите ближайший ключ корзины, а затем протестируйте каждый ключ в корзине. (На самом деле, возможно, но маловероятно, чтобы ближайший ключ был в другом сегменте - вам нужно найти ближайший ключ, или очень близкий ключ был бы достаточно хорош?)

Answer 2

Если бы данные не были такими разреженными, график с ключами в качестве вершин и ребер, связывающих «соседние» (расстояние Хэмминга = 1), вероятно, был бы очень эффективным по времени. Хотя пространство было бы очень большим, поэтому в вашем случае я не думаю, что это будет достойный компромисс.

Answer 3

Ну, вы можете вставить все соседние ключи вместе с оригинальным ключом. Это будет означать, что вы сохраняете (64 k) в разы больше данных для k разных битов, и для этого потребуется заранее выбрать k заранее. Несмотря на то, что вы всегда можете расширить k с помощью грубой силы, запрашивая соседей, это автоматически запросит соседей ваших соседей, которых вы вставили. Это также дает вам компромисс между временем и пространством: например, если вы принимаете 64-кратное увеличение данных и 64-кратное замедление, вы можете получить два бита расстояния.