如何通过R最近邻居求解最近邻居？

Question

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

Ë2LSH也可以用来解决近邻问题，其中， 在给定查询q的情况下，数据结构是要求报告中的点P最接近于q的 。这可以通过为R = R1，R2，...创建多个R近邻 邻居数据结构来完成。 。 。 Rt，其中Rt应该为 大于从任何查询点到其最近邻居的最大距离 。最近的邻居可以通过 查询数据结构在radiae， 停止的增加顺序，然后恢复时，第一点被

有人能改写这个好吗？我不用这个程序来找到使用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 5具有什么样的价值，太大，我们会浪费空间，时间太短，我们无法找到我们的查询！}

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