c++ - 带有符号指标的 KNN 搜索

Question

我正在寻找一个 C++ 库，它允许使用平方伪范数有效地找到点集中一个点的 k 最近邻居：

我的第三个坐标在其平方范数中可能有也可能没有减号。或者，我可以考虑一个 4D 空间，其中第三个组件始终具有正号，而第四个组件始终具有负号。

ANN 库的文档表明它可以使用任何“Minkowski”度量。上面的度量是 Minkowski 度量的定义（在Wolfram Mathworld的意义上，但不是 ANN 的意义上）。然而，ANN 似乎很灵活，似乎只需要一个“+”和“-”运算符（ANN 文档，第 14 页），但它们不是按组件定义的，而是全局定义的。

有没有人概括过人工神经网络来处理这种情况？是微不足道的吗？它不会搞砸 kd-tree 吗？是否存在另一个图书馆？

谢谢！

Answer 1

范数 x ² +y ² -z ²违反了使用 kd-tree 的搜索通常基于的一些假设。其中一个假设是“邻域”（“靠近”）是一些“局部”属性，即给定一个点 P，所有点 Q 的dist(P,Q) < r坐标都在 P 的坐标周围的有限范围内。因此，沿着它们的坐标分割点集可以利用坐标进行有效搜索。但是对于上述范数，即使对于dist([0,0,0],Q) = 0没有有限框的点 Q 也可以给出；这些点位于一个无限圆锥上。仍然应该可以设计一种利用“锥形”结构的有效搜索算法 - 但 kd-tree 将不起作用。