问题标签 [approximate-nn-searching]

使用特征描述符 [如 SIFT、SURF] 时，Approximate Nearest Neighbor 是在图像之间进行匹配的最快方法吗？

我有一个在 100 维空间中有 500,000 个点的数据库，我想找到最接近的 2 个点。我该怎么做？

更新：空间是欧几里得，对不起。并感谢所有的答案。顺便说一句，这不是家庭作业。

我正在我的 Rails 应用程序中实现用户搜索功能。如果用户输入拼写错误，我希望应用程序建议正确的拼写。ruby中有没有这个插件。这可以在sql中完成吗？

问候， 潘卡伊

我想创建一个 STL 映射来查找一个项目是否足够接近 3 维空间中的另一个项目。到目前为止，我的“小于函子”运行良好，粘贴到以下链接。

现在这个问题还不是“最近邻”问题。相反，这是一个“在一定距离内是否有邻居”的问题。

我的示例仅显示一个维度。为了清楚起见，我跳过了 Y/Z 尺寸。

到目前为止我的尝试：

在极少数情况下，我的意思是——非常罕见——当位置重叠时，地图找不到匹配的条目。

仍然使用 STL 容器，我可以做些什么来更好地实现这一点？

我正在编写一段代码，该代码执行与 128 维描述符的特征匹配。

图像的所有描述符都存储在 std::vector 中，其中 InterestPoint 包含一个成员 *double desc，它是描述符向量。

现在我想在 Flann 矩阵中使用这个结构来稍后进行近似最近邻特征匹配，我将其初始化为：

我现在如何用来自 ip1 向量的每个元素的 *double desc 成员填充这个 flann::Matrix ？这是我尝试过的：

编译但没有成功。flann 提供了一种访问 flann::Matrix 每一行的方法，使用运算符 []，因此 Matrix 类是行主要的。

提前致谢，

这个问题解释了我要解决的问题： Finding the single nearest neighbor using a Prefix tree in O(1)?

我的问题是关于该问题页面中提出的解决方案部分。在那一节中提到，我们通过从节点开始遍历树来从每个前缀树中找到最近的邻居。查找前缀树中是否存在键很简单，但得到最相似的键我根本不明白。如何做到这一点？

我希望有人可以向我解释这一点，如果不是以图形方式（这是首选），那么至少有一些细节。

编辑：

这是论文的代码。它是用 python 编写的，不幸的是我以前从未使用过 python。如果有人熟悉 python 并且可以查找代码以查看他们如何使用前缀树找到最近的邻居。https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/nearest_neighbor_lsh.py

https://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/classes.py

维基百科中关于 kd-trees 在内部节点中存储点的链接。我必须执行 NN 查询，我认为（这里是新手），我理解这个概念。

但是，据说我从 Computational Geometry Algorithms and Applications（De Berg、Cheong、Van Kreveld 和 Overmars），第 5.2 节，第 99 页研究 Kd 树。我可以看到的主要区别是 Overmars 将拆分数据放在内部节点和叶子中数据集的实际点。例如，在 2D 中，内部节点将保存分割线。

另一方面，维基百科似乎将点存储在内部节点和叶子中（而 Overmars 仅在叶子上）。

在这种情况下，我们如何执行最近邻搜索？此外，为什么会有这种差异？

从课程的幻灯片中，我发现了这些：

给定 R^D 中的集合 P 和查询点 q，它的 NN 是 P 中的点 p_0，其中：

类似地，在近似因子 1 > ε > 0 的情况下，ε-NN 为 p_0，因此：

（我想知道为什么 ε 不能达到 1）。

我们构建了一个 KD-tree，然后我们使用这个算法搜索 NN： 就我的想法和测试而言，这是正确的。

我应该如何修改上述算法，以执行近似最近邻搜索 (ANNS)？

我的想法是将当前最佳值（在叶子中的更新部分）乘以 ε，并保持算法的其余部分不变。但是，我不确定这是否正确。有人可以解释吗？

PS - 我了解搜索 NN 的工作原理。

请注意，我在计算机科学网站上问过，但我什么也没得到！

我有 2 组：A 和 B。两组都包含相同数量的高维点。如何为 Set B 中的每个点找到 Set A 中的最近邻居？

我考虑过使用 Voronoi 图，但似乎（根据维基百科）它不适合高于 2 的尺寸。

有人可以向我建议一种方法吗？

I have read few sources on VP-tree for similarity knn. No one wrote about adding an element to exists tree, which is required for maintenance. Explanation of adding element will be just great.