有趣的问题。我在这一领域的经验有限，但由于Levenshtein距离满足三角形不等式，我认为必须有一种方法来计算到原点的某种绝对距离，以便在不与整个数据库中的所有条目进行直接比较的情况下找到彼此邻近的字符串。
在第26页，他讨论了基于kd树和其他树的相似性度量，但得出结论：However, general metric spaces do not provide the geometry required by
those techniques. For a general metric space with no other
assumptions, it is necessary distance-based to use a distance-based
approach that indexes points solely on the basis of their distance
from each other. Burkhard and Keller [35] offered one of the first
such index structures, now known as a BK-tree for their initials, in
1973. In a BK-tree, the metric is assumed to have a few discrete return values, each internal node contains a vantage point, and the
subtrees correspond to the different values of the metric.
关于BK树如何工作的博客文章可以找到here。
在论文中，Skala继续描述这个问题的其他解决方案，包括VP-trees树和GH树。第六章分析了基于Levenshtein编辑距离的距离。他还提出了一些其他有趣的弦距离度量。
