如何通过R最近邻居解决最近邻居? [英] How to solve nearest neighbor through the R-nearest neighbor?
问题描述
引用E2LSH手册(关于此特定库并不重要，对于一般的NN问题，此引用应该是正确的):
Citing the E2LSH manual (it's not important that's about this specific library, this quote should be true for NN problem in general):
E 2LSH也可以用于解决最邻近问题，其中， 给定查询q，需要数据结构来报告要点 在P中最接近q.这可以通过创建多个R-earn来完成 相邻数据结构，对于R = R1，R2，... . . Rt，Rt应该在哪里 大于从任何查询点到其查询点的最大距离 最近的邻居.然后可以通过恢复最近的邻居 以半径递增的顺序查询数据结构， 找到第一个点就停止
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-near邻居方法找到最近邻居的步骤.
Could someone rephrase this please? I don't this procedure to find the nearest neighbor using the R-near neighbor approach.
推荐答案
我将提供一个示例，该示例应将其清除.假设我们的数据集仅由一个点p组成，并且一个查询点到达q.假设 * p与q的距离为3.9.
I will provide an example, which should clear things up. Assume that our dataset consists of only one point, p and a query point arrives, q. Let's assume* that the distance of p and q is 3,9.
现在，通过使用E2LSH $ ，我可以创建一个解决R最近邻问题的数据结构，即它将回答位于半径R内的是(并为我取点)如果不存在这样的问题，它将回答否.
Now, by using E2LSH$, I can create a data structure that solves the R-nearest neighbor problem, i.e. it will answer yes (and fetch me the point) that lies inside a radius R. If no such point exists, it will answer no.
让我们选择从R = 1到5来构建5种这种数据结构.在我们看来，这是我们到目前为止所做的:
Let's say that I choose to build 5 data structures of that kind, starting from R = 1 to 5. In our mind, this is what we have done so far:
现在请记住，d(p，q)= 3,9，因此我们希望询问使用R = 4构建的数据结构，并为我们找到查询点q.
So now remember, that d(p, q) = 3,9, thus we expect to ask the data structure that is built with R = 4 and find for us the query point q.
现在，让我们假设我们不知道d(p，q)，因此我们从选择的最小半径开始搜索，即1.所以，我们问，从我们的半径中是否有任何东西(等于1)数据集?不！
Now let's pretend that we do not know d(p, q), so we start searching from the smallest Radius we have picked, that's 1. So, we ask, is there anything in Radius (equal to 1) from our dataset? No!
从R = 2开始?不！
从R = 3开始?不！
从R = 4开始?是的，这就是q！现在我们完成了. 4是您在问题中提到的R t .
From R = 2? No!
From R = 3? No!
From R = 4? Yes, and that's q! So now we are done. 4 is the Rt you mention in your question.
* 这是一个很强的假设，E2LSH 会遭受的困扰，因为不得不让用户输入该参数R，因为通常我们不知道R应该具有什么值，太大了，我们会浪费时间和空间，太小了，我们找不到查询！
* That's a strong assumption and E2LSH suffers for having to put the user to input that parameter R, since usually we do not know what value should R have, too big and we will waste space and time, too small and we won't find our query!
$ 我听说现在在 Ilya Razenshteyn 的主页中，有一些比E2LSH更现代的东西.
$ I heard there is something more modern than E2LSH now, in Ilya Razenshteyn's homepage.
这篇关于如何通过R最近邻居解决最近邻居?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
