computational-geometry - 如何找到 n 维空间中的 k 最近值？

Question

我读过关于 kd-trees 的文章，但是当空间的维度很高时它们效率低下。我有一个值数据库，我想找到查询的某个汉明距离内的值。例如，数据库是一个 32 位数字的列表，我想找到与查询值相差小于 3 位的所有数字。

我在某处听说过 MultiVariate Partition 树，但找不到好的参考。我知道 min-Hash 给出了一个很好的近似值，更好，但我想要一个准确的答案。

Answer 1

汉明距离与levenshtein distance密切相关，类似于用于拼写校正的算法。

一种有效的方法是trie中的分支定界搜索。它需要的时间在距离上是指数的，对于近距离，直到字典大小是线性的。

如果字典是存储在二进制树中的二进制词，具有严格的汉明距离，这里是一个简单的伪代码：

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 */
  }
}

这个想法是你遍历整个 trie，跟踪当前 trie 节点和原始单词之间的距离。您可以通过预算可以容忍多少距离来修剪搜索。这是有效的，因为随着您深入树丛，距离永远不会减少。

然后您重复执行此操作，预算从零开始并逐步增加，直到您打印出您想要的命中。由于每次步行所覆盖的节点比随后的步行要少得多，因此进行多次步行并没有什么坏处。如果k是固定的，您可以简单地将其作为您的预算。