c++ - 如何通过R-最近邻求解最近邻？

Question

引用 E2LSH 手册（关于这个特定库并不重要，这句话对于一般的 NN 问题应该是正确的）：

E 2LSH 也可用于解决最近邻问题，其中，给定查询 q，数据结构需要报告 P 中最接近 q 的点。这可以通过创建几个 R 近邻数据结构来完成，对于 R = R1, R2, 。. . Rt ，其中 Rt 应大于从任何查询点到其最近邻居的最大距离。然后可以通过按半径的递增顺序查询数据结构来恢复最近的邻居，只要找到第一个点就停止

有人可以改写吗？我没有这个程序来使用 R 近邻方法找到最近的邻居。

Answer 1

我将提供一个示例，它应该可以解决问题。假设我们的数据集只包含一个点，p并且到达一个查询点，q. 让我们假设^*p和的距离q是 3,9。

现在，通过使用 E2LSH ^$，我可以创建一个解决 R 近邻问题的数据结构，即它会回答位于半径 R 内的是（并获取我的点）。如果不存在这样的点，它将回答不。

假设我选择构建 5 个这种数据结构，从 R = 1 到 5。在我们看来，这就是我们迄今为止所做的：

所以现在请记住，d(p, q) = 3,9，因此我们期望询问由 R = 4 构建的数据结构并为我们找到查询点q。

现在假设我们不知道 d(p, q)，所以我们从我们选择的最小半径开始搜索，即 1。所以，我们问，我们数据集中的半径（等于 1）有什么东西吗？不！

从 R = 2? 不！从 R = 3? 不！从 R = 4？是的，就是这样q！所以现在我们完成了。4 是您在问题中提到的 R _{t 。}

---

*_{这是一个强有力的假设，E2LSH不得不让用户输入参数 R，因为通常我们不知道 R 应该有什么值，太大会浪费空间和时间，太小我们不会找到我们的查询！}

$_{我听说现在有比 E2LSH 更现代的东西，在Ilya Razenshteyn的主页上。}