最近邻搜索的高效实现

Question

我试图实现一个有效的算法，最近邻搜索问题。

我读过关于一些数据结构的教程，这些结构支持此类问题的操作(例如R树、覆盖树等)，但它们都很难实现。

此外，我也找不到这些数据结构的示例源代码。我知道C++和我正试图用这种语言来解决这个问题。

理想情况下，我需要描述如何使用源代码实现这些数据结构的链接。

Answer 1

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

Answer 2

快速近邻搜索库有几种很好的选择。

• 安，这是基于山和亚雅的工作。这一工作记录在S.Arya和D.M.Mount的一篇论文中。“固定维度中的近似最近邻查询”。在进程中。第四届ACM-SIAM交流会。离散算法，第271-280页，1993年。
• 弗兰，基于Marius & Co.的工作，在2009年计算机视觉理论与应用国际会议(VISAPP'09)上发表了一篇由Marius和DavidG.Lowe撰写的论文，“具有自动算法配置的快速近似近邻”。FLANN的代码可在github上使用。

在某些情况下，FLANN似乎更快，而且它是一个更现代的代码版本，它为许多其他语言提供了坚实的绑定，可以快速地结合变化。如果你想要一个可靠的、经过良好测试的标准库，安可能是个不错的选择。

编辑回应评论

这两个库都有丰富的文档和示例。

ANN的示例代码可在手册中获得，见2.1.4节。

FLANN的示例代码可在FLANN存储库示例目录中获得，例如/examples/flann_examples.c