非度量空间中的最近邻居搜索

Question

我想知道在非度量空间中工作时的最近邻搜索算法吗？特别是，在这种设置中是否有任何变种的kd-tree算法，具有可证明的时间复杂度等？

Answer 1

NMSLIB提供了一个库，用于在非公制空间中执行最近邻点搜索。该Github页面提供了十几篇要阅读的论文，但并非全部适用于非度量空间。

不幸的是，关于Neaest Neighbour Search的复杂性的理论结果很少，对于非度量空间并且没有全面的经验评估。

我可以在Effective Proximity Retrieval by Ordering Permutations上看到一些理论结果，但我不确信。不过，我建议你看看。

似乎没有很多人使用k-d树作为非度量空间。他们似乎使用VP树，也使用密度等，如Near Neighbor Search in Nonmetric Spaces中所述。

直观而言，密度是一类装饰树，以类似于metric tree的方式保存数据集的点。关键差异 在于树装饰的性质;而不是有一个或几个实际值反映了每个树节点附加的三角不等式的一些边界，每个密度节点都与一个特定的分类器相关联，这里称为密度估计器。

Answer 2

可能更适合您的理论兴趣： PH-Tree与四叉树相似，但是它在存储它们之前将浮点坐标转换为非公制系统。 PH-Tree使用非度量距离函数对非度量数据执行所有查询（包括kNN查询）（您可以在其上定义自己的距离函数）。

就kNN而言，PH树与R +树等树相同，并且通常优于kd树。 对于转换和距离函数，除非可能（几乎可忽略）执行时间，否则非度量数据存储似乎对性能的负面影响很小，甚至可能是正数。

数据转换的原因来自树的固有约束：树是一个按位树，这意味着它只能存储位序列（可以看作整数）。为了在树中存储浮点数，我们简单地使用浮点数的IEEE位表示并将其解释为一个整数（这对正数工作正常，负数稍微复杂一点）。关键是，这保留了排序，即。如果浮点数f1大于f2，则int（f1）位的整数表示也总是大于int（f2）。简而言之，这种转换允许将浮点数作为整数存储，而不会损失任何精度（！）。

该转换是非度量的，因为浮点数的前导位（在符号位之后）是指数位，后面是小数位。显然，如果两个数字的指数位不同，它们的距离与由分数位差异引起的距离相比，其指数增长更快（或负指数更慢）。

为什么我们使用按位尝试？如果我们有d维，它允许一个简单的转换，以便我们可以将坐标的每个d值的第n位映射为具有d位的位串。例如，对于d = 60，我们得到一个60位的字符串。假设CPU寄存器宽度为64位，这意味着我们可以在恒定时间内执行许多与查询有关的操作，即许多操作只需要一次CPU操作，而不管我们是否有3维或60维。从这篇短文中可能很难理解发生了什么，更多细节可以在here找到。