5

我正在尝试为最近邻搜索问题实现一种有效的算法。

我读过一些数据结构的教程，这些数据结构支持这类问题的操作（例如，R-tree，cover tree等），但它们都很难实现。

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

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

4

2 回答 2

14

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

  • ANN，它基于 Mount 和 Arya 的工作。这项工作记录在 S. Arya 和 DM Mount 的论文中。“固定维度的近似最近邻查询”。在过程中。第四届 ACM-SIAM 研讨会。离散算法，第 271-280 页，1993 年。

  • FLANN，基于 Marius Muja & Co. 的工作。 Marius Muja 和 David G. Lowe 有一篇论文，“Fast Approximate Nearest Neighbors with Automatic Algorithm Configuration”，在计算机视觉理论与应用国际会议（VISAPP' 09), 2009. FLANN 的代码在github上可用

FLANN 在某些情况下似乎更快，并且是更现代的代码版本，具有对许多其他语言的可靠绑定，可以快速合并更改。如果您想要一个经过充分测试的可靠标准库，ANN 可能是一个不错的选择。

编辑以回应评论

这两个库都有大量的文档和示例。

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

FLANN 存储库示例目录中提供了 FLANN 的示例代码，例如 /examples/flann_examples.c

于 2012-04-06T09:01:54.547 回答
2

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

于 2012-04-06T09:57:01.167 回答