Как мне найти k-ближайшие значения в n-мерном пространстве?

Question

Я читал о kd-деревьях, но они неэффективны, когда размерность пространства высока. У меня есть база данных значений, и я хочу найти значения, которые находятся в пределах определенного расстояния Хемминга запроса. Например, база данных представляет собой список 32-битных чисел, и я хочу найти все числа, которые отличаются от значения запроса менее чем на 3 бита.

Я где-то слышал о деревьях MultiVariate Partition, но не смог найти хорошую ссылку. Я знаю, что min-Hash дает хорошее приближение, лучше как, но я хотел бы получить точный ответ.

Answer 1

Расстояние Хемминга тесно связано с расстоянием Левенштейна и аналогично алгоритмам, используемым для исправления орфографии.

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

Если словарь состоит из двоичных слов, хранящихся в двоичном коде, со строгим расстоянием Хэмминга, вот простой псевдокод:

walk(trie, word, i, hit, budget){
  if (budget < 0 || i > word.length) return;
  if (trie==NULL){
    if (i==word.length) print hit;
    return;
  }
  hit[i] = 0;
  walk(trie.subtrie[0], word, i+1, hit, (word[i]==0 ? budget : budget-1));
  hit[i] = 1;
  walk(trie.subtrie[1], word, i+1, hit, (word[i]==1 ? budget : budget-1));
}

main(){
  for (int budget = 0; ; budget++){
    walk(trie, word, 0, hit, budget);
    /* quit if enough hits have been printed */
  }
}

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

Затем вы делаете это многократно с бюджетами, начинающимися с нуля и постепенно увеличивающимися, пока не распечатаете нужные результаты. Поскольку каждая прогулка охватывает намного меньше узлов, чем последующая прогулка, не повредит, что вы делаете несколько прогулок. Если k исправлено, вы можете просто начать с этого как ваш бюджет.