问题标签 [nearest-neighbor]

使用特征描述符 [如 SIFT、SURF] 时，Approximate Nearest Neighbor 是在图像之间进行匹配的最快方法吗？

我有一个真正的问题。

我有一个架构如下的数据库：

物品

• ID
• 描述
• 其他垃圾

标签

• ID
• 姓名

item2tag

• item_id
• tag_id
• 数数

基本上，每个项目最多被标记为 10 件事情，数量不等。items2tag中有50,000个项目和50,000个标签，大约有500,000个条目。给定一个项目，我想找到“最相似”的项目。

“最相似”是指具有最相似标签组合的项目......如果某件事“酷”是“有趣”的两倍，我想找到所有其他几乎“酷”的东西两次就像他们“有趣”一样。当然，这应该适用于 10 个标签，而不仅仅是 2 个。

有任何想法吗？

在过去的几天里，我注意到一些网站展示 了使用遗传算法的 TS 解决方案。

哪种方法会在 TSP 问题中产生更短的行程：最近邻算法还是遗传算法？

我无法想出一个有效的 SQL 查询来处理以下情况：

假设我们有一个包含两列的表

该表很大（数百万行）。每个“groupId”有不同数量的“值”——比如 100 到 50.000 之间。所有浮点值都大于或等于零，但在其他方面是无界的。

对于给定的 groupId，查询应返回按相似度递减排序的所有其他组，其中“相似”定义为两组中所有可能的 30 个值对之间的最小欧几里德距离。

相似性的定义让我很生气。我认为对于计算上面定义的相似度，朴素算法是 O(n^2)。现在我正在寻找重新定义“相似性”或有效实现上述内容的想法。我可以想象一个涉及 k 最近邻的解决方案，比如 PostGis 几何最近邻，或者可能是最大的公共子序列算法（尽管我需要后者的“模糊”实现，因为“值”几乎不会完全相等） .

我们目前正在使用 mySQL 以防万一。

干杯，

我想确定两个新闻项目内容的相似性，类似于谷歌新闻，但在某种意义上不同，我希望能够确定基本主题是什么，然后确定哪些主题是相关的。

因此，如果一篇文章是关于萨达姆侯赛因的，那么该算法可能会推荐一些关于唐纳德拉姆斯菲尔德在伊拉克的商业交易的内容。

如果你能抛出 k-最近邻之类的关键词，并稍微解释一下它们为什么起作用（如果可以的话），我会做剩下的研究并调整算法。只是寻找一个开始的地方，因为我知道那里有人以前一定尝试过类似的东西。

我正在编写一个实现 SCVT（Spherical Centroidal Voronoi Tesselation）的程序。我从分布在单位球面上的一组点开始（我可以选择随机点或等面积螺旋）。会有几百到可能 64K 点。

然后，我需要生成大约数百万个随机样本点，为每个样本找到集合中最近的点，并使用它来计算该点的“权重”。（这个权重可能必须从另一个球形集合中查找，但是对于任何给定的算法运行，该集合将保持静态。）

然后我将原始点移动到计算点，并迭代该过程，大概 10 或 20 次。这将为我提供 Voronoi 瓷砖的中心以供后续使用。

稍后我将需要找到给定点的最近邻居，以查看用户单击了哪个图块。这在上述问题中很容易解决，并且无论如何都不需要超快。我需要提高效率的部分是单位球面上数百万个最近的邻居。任何指针？

哦，我使用的是 x、y、z 坐标，但这不是一成不变的。看起来它会简化事情。我也在使用我最熟悉的 C，但也不拘泥于那个选择。:)

我考虑过对样本点使用螺旋模式，因为这至少让我找到了最后一个点的邻居作为下一次搜索的良好起点。但如果我这样做，看起来它会使任何类型的树搜索变得无用。

编辑：[对不起，我以为我对标题和标签很清楚。我可以轻松生成随机点。问题是最近邻搜索。当所有点都在单位球面上时，什么是有效的算法？]

我有一个数据库，我想使用单个查询找出按 ID 排序的上一条和下一条记录。我试图做一个工会，但这不起作用。:(

有任何想法吗？非常感谢。

我有一个维护脚本，它将一堆数据从一个数据库转储到另一个数据库。

我正在尝试获取数据

我试图用当前行的 rank2 得到的是最近的 rank2，其中 rank1 不为空。我假设 rank1 是 rank2 的有效替代品

所以，我相信我有两个问题。

1. 我认为我没有 rank2 可以在嵌套的 select 语句中使用
2. 我不知道怎么说'最接近rank2<rank2当前。

我对 Rank1 的值范围是 0-20,000，而 rank2 的范围是 0-150,000（不知道为什么这很重要）。排名之间没有有效的相关性。

Rank1 总是一个更可靠的数字，但通常是空的，所以我试图用这种类型的替换来捏造我的订单。

这里有一些示例数据用作示例

我希望能拿回 2,5,4,6,7,3,1,8,9,10 的订单。或类似的东西。基本上，当我对 rank2 有一个空值时，为最近的 rank1 获取最近的 rank2。

我不认为这是“完美的”，但比仅在 rank1 上排序要好。

这是我发送到 PostGIS 邮件列表的电子邮件中的交叉帖子

到目前为止，我在一个点和它在一条线上的投影位置之间创建一条线的努力已经很长了，但我快到了。截至昨天，在包括任何最近邻分析之前，我得到了这张图片中显示的结果：

如您所见，粉红色的每个点都连接到所有投影点，而我只想将每个粉红色 x 连接到其各自的投影。

在 IRC 上，建议我使用BostonGIS 的最近邻法。我将函数输入到 PostgreSQL 并尝试失败，如下所述。我假设我的错误是由于错误的参数类型造成的。我玩弄了它，将一些列的类型更改为 varchar，但我仍然无法让它工作。

关于我做错了什么的任何想法？关于如何解决它的任何建议？

代码：

错误

我知道我可以使用 KD-Tree 来存储点并快速迭代其中接近另一个给定点的一小部分。我想知道线条是否有类似的东西。

给定一组3D行 L （将存储在该数据结构中）和另一个“查询行”q，我希望能够快速迭代 L 中与 q“足够接近”的所有行。我打算使用的距离是两点 u 和 v 之间的最小欧几里得距离，其中 u 是第一行的某个点，v 是第二行的某个点。计算该距离不是问题（有一个涉及叉积的好技巧）。

也许你们有一个好主意或知道在哪里寻找论文、描述等......

TIA，S。