Хранение и индексация двоичных строк в базе данных

Двоичная строка, как здесь определено, представляет собой «массив» битов фиксированного размера. Я называю их строками, поскольку в них нет порядка (сортировка / индексация, поскольку числа не имеют значения), каждый бит не зависит от других. Каждая такая строка имеет длину N бит, причем N исчисляется сотнями.

Мне нужно сохранить эти строки и задать новый запрос двоичной строки для ближайшего соседа, используя расстояние Хэмминга в качестве метрики расстояния.
Существуют специализированные структуры данных (метрические деревья) для поиска на основе метрик (VP-деревья, cover-tree, M-tree), но мне нужно использовать обычную базу данных (в моем случае MongoDB).

Есть ли какая-то функция индексации, которая может быть применена к двоичным строкам, которая может помочь БД получить доступ только к подмножеству записей перед выполнением однозначного сопоставления расстояния Хэмминга? В качестве альтернативы, как можно было бы реализовать такой поиск на основе Хэмминга в стандартной БД?


database binary indexing algorithm hamming-distance
person Adi Shavit    schedule 06.07.2011    source источник
comment
Я называю их строками, потому что в них нет порядка - строки имеют порядок - в частности, лексикографический.   -  person Nick Johnson    schedule 07.07.2011
comment
Конечно, обычно последовательности битов называются числами или, если быть точным, целыми числами, которые имеют естественный порядок.   -  person Adi Shavit    schedule 07.07.2011

Ответы (2)


arrow_upward
3
arrow_downward

Расстояние Хэмминга является метрикой, поэтому оно удовлетворяет неравенству треугольника. Для каждой цепочки битов в базе данных вы можете сохранить расстояние до некоторой заранее определенной постоянной цепочки битов. Затем вы можете использовать неравенство треугольника для фильтрации битовых строк в базе данных.

Итак, скажем

C <- some constant bitstring
S <- bitstring you're trying to find the best match for
B <- a bitstring in the database
distS <- hamming_dist(S,C)
distB <- hamming_dist(B,C)

Таким образом, для каждого B вы должны сохранить соответствующий distB.

Тогда нижняя граница для hamming(B,S) будет abs(distB-distS). И верхняя граница будет distB+distS.

Вы можете отбросить все B, чтобы нижняя граница была выше, чем нижняя верхняя граница.

Я не уверен на 100% относительно оптимального варианта выбора C. Я думаю, вы хотели бы, чтобы это была битовая строка, которая находится близко к «центру» вашего метрического пространства битовых строк.

person tskuzzy    schedule 06.07.2011
comment
Это эквивалентно хранению Bk-дерева только с корневым узлом. Это немного поможет, но оставит много места для поиска. Вы можете сохранить расстояние до нескольких строк (как bk-дерево FHFQ), но для этого потребуется запрос с несколькими неравенствами, которые нельзя эффективно оценить по одномерному индексу. - person Nick Johnson; 07.07.2011
comment
@tskuzzy: Спасибо, именно то, что я хотел. Просто чтобы прояснить ответ: пусть minDistB будет наименьшим distB из B в базе данных, затем отбросьте все B, так что: abs (distB-distS) ›distS + minDistB. - person Adi Shavit; 07.07.2011
comment
@Nick Johnson: Вы правы (спасибо за ссылку на сообщение BK-Tree). Действительно, очевидным расширением было бы индексирование нескольких таких C, разбросанных по пространству и индексация базы данных несколькими B, по одному на C. - person Adi Shavit; 07.07.2011
comment
@ Ади Верно. Однако невозможно эффективно удовлетворить запрос с множественными неравенствами по отношению к одномерному индексу, поэтому экономия будет не такой большой, как использование реальной древовидной структуры для хранения данных. - person Nick Johnson; 08.07.2011

arrow_upward
2
arrow_downward

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

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

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

person Nick Johnson    schedule 07.07.2011