algorithm - 检索相似条目的最快(实际)存储实现是什么？

Question

我读到了 BK-trees (Burkhard-Keller-Trees) 几个月前，据说这是一种保存您想通过距离度量再次读取的内容的好方法。因此，在每种情况下，您都希望通过相似性检索某些内容。

然而，这些 BK 树对我来说似乎并不快。当我尝试一个实现并做了一些输出时，一旦我允许更长的距离，它就必须在树中大量移动(我用 levenshtein 验证了它并允许最多 6 次编辑)。

最快的实现方式(如果只是关于速度的话)当然是将从每个条目到每个条目的距离存储在一个表中并直接查找它们，但这开销太大。

因此我在标题中添加了realistic。 需要更多的内存是可以的，但是实现应该仍然是现实的和可用的(我对这些技术的了解还不够多，无法说明什么是现实，但我想还是有一些界限的)。

有没有比 BK 树更快的东西可用，或者 BK 真的是山顶(还)吗？

场景

我没有真正的用例，但场景如下:我有 1 个 mio 条目，它们彼此之间有一定距离(由距离函数定义)。现在我得到一个条目并且想知道:

• 哪 5 个条目与给定条目最匹配
• 哪些其他条目(与数量无关)低于或等于给定阈值

数据库无关紧要。

我想最终最好的算法会匹配两者？

Answer 1

另一个基于树的最近邻指标是 http://en.wikipedia.org/wiki/Cover_tree .号称实用，而且http://www.cs.waikato.ac.nz/ml/weka/捡起来了，果然如此。然而，最近邻似乎很难用树或其他任何东西准确地做到，因为有许多关于近似最近邻的提议，我认为如果不难的话，这会很愚蠢。我可以在 http://people.csail.mit.edu/indyk/edit.ps 看到一个编辑距离.

进行近似最近邻搜索的另一种方法是希望最近邻具有恰好出现在您的查询字符串中的连续字符部分。然后对于数据库中的所有字符串，将它们分成所有连续的 k 长子字符串，并构建一个可以使用精确匹配的表。然后，对于您的查询字符串，考虑所有 k 长的连续子字符串，对这些子字符串进行精确匹配，并计算您通过精确搜索 k 长子字符串从数据库中找到的所有字符串的编辑距离。