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

Question

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

E 2LSH can be also used to solve the nearest neighbor problem, where, given the query q, the data structure is required the report the point in P that is closest to q. This can be done by creating several R-near neighbor data structures, for R = R1, R2, . . . Rt , where Rt should be greater than the maximum distance from any query point to its nearest neighbor. The nearest neighbor can be then recovered by querying the data structures in the increasing order of the radiae, stopping whenever the first point is found

有人可以改一下吗？我没有使用 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。那么，我们问，Radius 中是否有任何东西（等于 1）来自我们的数据集？没有！

从 R = 2？不！ 从 R = 3?不！ 从 R = 4?是的，那就是 q！所以现在我们完成了。 4 是你在问题中提到的 R_t。

---

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

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