最近邻搜索的高效实现

Question

我正在尝试实现一个高效的“最近邻搜索”算法。我已经阅读了一些关于支持此类问题操作的数据结构的教程（例如，R树、覆盖树等），但它们都很难实现。同时，我也找不到这些数据结构的示例源代码。我会C++，并且正在尝试用这种语言解决这个问题。理想情况下，我需要链接，描述如何使用源代码实现这些数据结构。

- user466534

---

你的数据维度是多少？对于二维点数据，我建议使用Kd-tree。这个算法容易实现。对于其他类型的数据/几何结构，你可能需要考虑使用R-trees（boost 1.54支持rtree索引）。 - gvd

Answer 1

有几个快速最近邻搜索库的选择。

• ANN，基于Mount和Arya的工作。 Arya和D.M. Mount在论文中记录了这项工作。 "Approximate nearest neighbor queries in fixed dimensions"。在第4届ACM-SIAM Sympos中。离散算法，第271-280页，1993年。

• FLANN，基于Marius Muja和David G.Lowe的工作。 Marius Muja和David G.Lowe在2009年计算机视觉理论和应用国际会议（VISAPP'09）上发表了一篇论文，题为"Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration"。FLANN的代码可在github上获取。

在某些情况下，FLANN似乎更快，并且是具有坚实绑定其他语言的现代化版本，可以迅速整合更改。如果需要一个坚实经过充分测试的标准库，则ANN可能是一个不错的选择。

响应评论的编辑

这些库都有广泛的文档和示例。

ANN的示例代码可在手册中的第2.1.4节中找到。

FLANN的示例代码可在FLANN存储库examples directory中找到，例如/examples/flann_examples.c

- Andrew Walker

---

如何使用它，例如当我有(x1,y1)(x2,y2)...(xn,yn)时？ - user466534

@dato - 答案已更新，包括每个项目文档中权威示例的链接。 - Andrew Walker

我需要安装 FLANN 库吗？ - user466534

是的，你需要这样做。使用FLANN（或ANN）需要在您的包含和库路径上提供相应的文件，就像您使用任何其他非平凡的C++库一样。 - Andrew Walker

@AndrewWalker 你能否在回答中加入nanoflann？它是FLANN的一个分支，速度明显更快。这是一个仅包含头文件的C++11库，非常方便。谢谢并问候 - krjw

Answer 2

您可以尝试使用线扫描算法来查找最近的点对：http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep。

- Micromega