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

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

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

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

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

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

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

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

A xor B

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

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

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

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

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

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

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

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

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

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

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

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

Эти статьи включают ссылки на другие исследования, которые могут оказаться полезными, например, M-Trees .

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

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

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

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

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 по мере продвижения, поскольку после первых нескольких попыток вы '