问题标签 [nearest-neighbor]

假设我有一个巨大的（几百万）n 个向量列表，给定一个新向量，我需要从集合中找到一个非常接近的向量，但它不需要是最接近的。（Nearest Neighbor 找到最近的并在 n 时间内运行）

有哪些算法可以以准确性为代价快速逼近最近邻？

编辑：因为它可能会有所帮助，我应该提到数据在大多数情况下都非常平滑，随机维度中出现尖峰的可能性很小。

我有一个 n 维点的集合，我想找到最接近的 2 个。我能想到的最好的二维是：

这使

但这对于大型阵列来说太慢了。我可以对其应用什么样的优化？

有关的：

两个不同 Numpy 数组中的点之间的欧几里德距离，不在

我正在实现一个 KD-tree 来将地图点聚类成组。我一直在使用Wikipedia 的 KD-tree 文章作为参考。搜索返回正确的最近邻点，但它比我预期的要慢。这是我的代码：

我的问题是我对“一个简单的比较，看看搜索点和当前节点的分裂坐标之间的差异是否小于搜索点到当前最佳位置的距离（整体坐标） ”的解释是否正确。我将其解释为：

if (fabs(point.coordinate.latitude - self.location.coordinate.latitude) < best.distToPoint)

和

if (fabs(point.coordinate.longitude - self.location.coordinate.longitude) < best.distToPoint)

分别。也欢迎任何其他建议。

谢谢。

我正在编写一种方法，该方法将点数组作为输入，并为数组中的每个点找到与其自身最近的点。我目前正在以蛮力的方式执行此操作（检查每个点与其他点）。我当前的实施没有对数组进行排序，但我可以使用 CompareByX 方法按 px 值对其进行排序。我正在检查算法的运行时间，如果 n 值很大，它会变得非常耗时。我对这个主题不是很了解，并且对不同类型的数据结构知之甚少，任何简单的帮助都会很棒！

我目前的代码是：

例如，我有一个坐标：

我想在 OSM DB 中找到最近的节点

在此示例中，节点 906459460

http://www.openstreetmap.org/api/0.6/node/906459460

然后我想知道哪些方式是其中的一部分

在这个例子中

http://www.openstreetmap.org/api/0.6/way/78456451

http://www.openstreetmap.org/api/0.6/way/76966153

http://www.openstreetmap.org/api/0.6/way/76965957

如何使用 API？谢谢

我正在使用 OpenCL 来查找两组 3D 点之间的最近邻居。

最近邻：对于数据集中的每个点（x，y，z），我必须找到模型中最近的一个。平方距离 = (Ax-Bx)^2 + (Ay-By)^2 + (Az-Bz)^2

这是我到目前为止所做的：

代码似乎可以工作，但我确信它可以被优化。我想知道如何利用本地内存使其变得更好。

谢谢

PS 我知道还有其他（更好的）方法可以找到最近的邻居，比如 kd-tree，但现在我想做简单的方法。

我需要使用最近邻调整大小而不是当前使用的双三次方式来渲染图像。我目前使用以下内容：

这适用于 IE 和 Firefox，但不适用于 Chrome 和 Safari。是否有任何 webkit 替代品或任何其他方式来实现这种效果？

我有一个递归函数（在树上），我需要让它在没有递归的情况下工作，并将树表示为隐式数据结构（数组）。

这是功能：

我正在使用此属性将树表示为数组：

这就是我所做的：

现在最后一步是摆脱递归，但我找不到方法，有什么提示吗？谢谢

我正在尝试构建一个程序来获取到具有选定 ID 的点的 k 最近邻点。我需要在不使用任何空间定位器功能（如 sdo_geometry 或 nn）的情况下执行此操作。

基本上我在oracle中有一个ID，Data_X，Data_Y的表。假设我的表中有 10 个条目，并且我需要与虚构点 target_x、target_y 最接近的 3 个点。

我们需要用我给定的虚构点计算表中每个点的欧几里得距离。我只是不知道 pl/sql 中的算法会返回最近的邻居 ID。

不知何故，下面的放大精灵图像在 Internet Explorer 9 中没有显示为清晰的最近邻像素完美。在 FF 中完美像素完美/清晰。

然而，在 IE 中，它似乎变得双三次平滑，在这种情况下我不想要。知道这个 CSS 有什么问题吗？