问题标签 [nearest-neighbor]

3-d 中的一个点由 (x,y,z) 定义。任意两点 (X,Y,Z) 和 (x,y,z) 之间的距离 d 为 d= Sqrt[(Xx)^2 + (Yy)^2 + (Zz)^2]。现在一个文件中有一百万个条目，每个条目都是空间中的某个点，没有特定的顺序。给定任意点 (a,b,c) 找到离它最近的 10 个点。您将如何存储百万点以及如何从该数据结构中检索这 10 个点。

I have a database full of two-dimensional data - points on a map. Each record has a field of the geometry type. What I need to be able to do is pass a point to a stored procedure which returns the k nearest points (k would also be passed to the sproc, but that's easy). I've found a query at http://blogs.msdn.com/isaac/archive/2008/10/23/nearest-neighbors.aspx which gets the single nearest neighbour, but I can't figure how to extend it to find the k nearest neighbours.

This is the current query - T is the table, g is the geometry field, @x is the point to search around, Numbers is a table with integers 1 to n:

The inner query selects the nearest non-empty region and the outer query then selects the top result from that region; the outer query can easily be changed to (e.g.) SELECT TOP(20), but if the nearest region only contains one result, you're stuck with that.

I figure I probably need to recursively search for the first region containing k records, but without using a table variable (which would cause maintenance problems as you have to create the table structure and it's liable to change - there're lots of fields), I can't see how.

I'm currently attempting to find K Nearest Neighbor of all nodes of a balanced KD-Tree (with K=2).

My implementation is a variation of the code from the Wikipedia article and it's decently fast to find KNN of any node O(log N).

The problem lies with the fact that I need to find KNN of each node. Coming up with about O(N log N) if I iterate over each node and perform the search.

Is there a more efficient way to do this?

我有一系列食谱，每一个都有许多成分。此信息存储在连接表中。给个菜谱，我想根据成分找到类似的菜谱。我该怎么做呢？

我遇到了最近邻算法的实现，用于查找两个相似图像中某些关键点之间的匹配。关键点由 SIFT 算法生成。这些点由一个 128 维向量描述，并且在两幅图像中都有很多这样的点。

匹配算法使用最近邻搜索，并且对于一幅图像中的每个点，计算另一幅图像中对应的最近点。“接近度”由点的向量之间的最小欧几里德距离来描述。通过仅采用距离低于某个阈值的那些点对来选择最佳匹配。

然而，我遇到的实现将一个图像中关键点的所有矢量与另一图像中的矢量相乘，从而形成一个产品矩阵。然后它会找到乘积高于给定阈值的点。

这个实现给出了正确的结果，但我想知道它是如何工作的。它是使用向量之间的相关性作为度量还是这里发生了其他事情。

我正在尝试创建一个系统，该系统能够找到具有类似喜爱的电影/书籍/兴趣/等的用户，就像 last.fm 上的邻居一样。共享最多共同兴趣的用户将具有最高匹配，并将显示在用户配置文件中（5 个最佳匹配左右）。

有没有相当快速的方法来做到这一点？显而易见的解决方案是创建一个包含用户 ID 和兴趣 ID 的表，并将一个用户与所有其他用户进行比较，但这将永远在一个表上花费......比如说百万用户，每个用户有 20 个兴趣。

我认为存在一些有效的解决方案，因为 last.fm 运行良好。我更喜欢使用一些常见的 SQL 数据库，如 mySQL 或 pgSQL，但任何事情都可以。

感谢您的建议。

更新：
事实证明，最大的问题是在 SQL 数据库中找到最近的邻居，因为没有一个开源数据库支持这种搜索。
所以我的解决方案是修改 ANN 以作为服务运行并从 PHP 查询它（例如使用套接字） - 甚至数百万用户在内存中说 7 维并不是什么大问题，它运行速度快得令人难以置信。

较小数据集的另一个解决方案是这个简单的查询：

20-50 毫秒，10 万用户，每个用户平均有大约 20 个兴趣（10 000 个可能的兴趣）

感谢那些回答了我之前的问题并让我走到这一步的人。

我有一个包含大约 25,000 个向量的表，每个向量有 48 个维度，值范围为 0-255。

我正在尝试开发一种局部敏感哈希（http://en.wikipedia.org/wiki/Locality-sensitive_hashing）算法来查找近邻或最近邻点。

我目前的 LSH 功能是这样的：

在这一点上我的问题是：

答：我的代码的“normalvariate(10, 4)”部分是否有最佳值。这是内置在 random.normalvariate ( http://docs.python.org/library/random.html#random.normalvariate ) 函数中的 python，我使用它来生成“d 维向量，其条目独立于稳定分布中选择” . 从我的实验来看，这些值似乎并不重要。

B：在维基百科文章的顶部，它指出：

如果 d(p,q) <= R，则 h(p) = h(q) 的概率至少为 P1

如果 d(p,q) >= cR，则 h(p) = h(q) 概率最大为 P2

此处提到的 R 值是否也是“稳定分布”部分中提到的 R 值。（http://en.wikipedia.org/wiki/Locality-sensitive_hashing#Stable_distributions）

C：与我之前的问题（B）有关。我发现在我的 hasing 函数中使用更高的 R 值将我的向量映射到更小的散列值范围内。有没有办法优化我的 R 值。

D：一张桌子大约可以使用多少张？

我有一个使用精灵表动画的精灵。他只有 16x16，但我想把他放大到 64x64 左右，因为它的像素-y 好！

结果很糟糕，当然浏览器是抗锯齿的。：/

谢谢！

编辑：不需要 css，这是我的绘图功能。

在这里看到它有点工作（codepen）

给定二维空间中的一组点 S，提供一种算法，为该组中的每个点计算最近邻（欧几里得）。我认为它称为最近邻图，不是吗？任何现有的有效算法 (N log N)，其中 N = len(S)？

我想构建一个应用程序，根据您的位置为您提供最近的餐厅。我们将拥有一个包含与餐厅对应的所有 POI 的数据库，我们将通过您手机的 GPS 获取您的位置...

什么算法合适？我在哪里可以找到关于它的好文档？

谢谢