SQL高效最近邻查询
我想不出一个有效的SQL查询来处理以下情况：
假设我们有一个包含两列的表
groupId : int
value : float这个表很大(几百万行)。每个"groupId“都有不同数量的”值“--比如在100%到50.000之间。所有浮点值都大于或等于零，但在其他情况下是无界的。
对于给定的groupId，查询应返回按相似度递减排序的所有其他组，其中“相似”定义为两组中所有可能的30个值对之间的最小欧几里得距离。
这种相似性的定义让我很难受。我认为对于上面定义的相似度计算，朴素算法是O(n^2)。现在，我正在寻找重新定义“相似性”或有效实现上述内容的想法。我可以想象一种涉及k近邻的解决方案，比如PostGis几何近邻，或者可能是一个最大的公共子序列算法(尽管我需要后者的“模糊”实现，因为“值”很难完全相等)。
我们目前在mySQL上，以防万一。
干杯,
Sören回答 4
Stack Overflow用户
发布于 2009-04-06 19:14:23
你能证实我答对了吗？
您的表表示由groupId标识的向量。每个向量都有一个介于100和50,000之间的维度，但维度上没有定义顺序。也就是说，表中的向量实际上是等价类的代表。
现在，您将两个等价类的相似性定义为等价类的任意两个表示到前30维的子空间的投影的最小欧几里得距离。
投影到二维的示例：
A = <1, 2, 3, 4>
B = <5, 6, 7, 8, 9, 10>A表示向量的下列等价类。
<1, 2, 3, 4> <2, 1, 2, 3> <3, 1, 2, 4> <4, 1, 2, 3>
<1, 2, 4, 4> <2, 1, 3, 2> <3, 1, 4, 2> <4, 1, 3, 2>
<1, 3, 2, 4> <2, 3, 1, 4> <3, 2, 1, 4> <4, 2, 1, 3>
<1, 3, 4, 2> <2, 3, 4, 1> <3, 2, 4, 1> <4, 2, 3, 1>
<1, 4, 2, 2> <2, 4, 1, 3> <3, 4, 1, 2> <4, 3, 1, 2>
<1, 4, 3, 2> <2, 4, 3, 1> <3, 4, 2, 1> <4, 3, 2, 1>这个等价类的所有代表到前两个维度的投影产生。
<1, 2> <1, 3> <1, 4>
<2, 1> <2, 3> <2, 4>
<3, 1> <3, 2> <3, 4>
<4, 1> <4, 2> <4, 3>B表示具有720个元素的等价类。到前两个维度的投影产生30个元素。
< 5, 6> < 5, 7> < 5, 8> < 5, 9> < 5, 10>
< 6, 5> < 6, 7> < 6, 8> < 6, 9> < 6, 10>
< 7, 5> < 7, 6> < 7, 8> < 7, 9> < 7, 10>
< 8, 5> < 8, 6> < 8, 7> < 8, 9> < 8, 10>
< 9, 5> < 9, 6> < 9, 7> < 9, 8> < 9, 10>
<10, 5> <10, 6> <10, 7> <10, 8> <10, 9>所以A和B的距离是8的平方根，因为这是两个向量到投影的最小距离。例如<3，4>和<5，6>产生这个距离。
那么，我对这个问题的理解是正确的吗？
对于每个具有m个分量的n个向量，一个非常朴素的算法必须计算(n - 1)个距离。对于每个距离，算法将计算m！/ (m - 30)的距离！每个向量的投影。因此，对于100维(你的下限)，一个向量有2.65*10^32个可能的投影。这需要计算投影之间大约7*10^64的距离，并找到最小值来找到两个向量的距离。然后重复n次。
我希望我误解了你的意思或者弄错了。否则，这听起来真的很有挑战性，也不可行。
我考虑的是对向量分量进行排序并尝试匹配它们。如果可能的话，使用曼哈顿距离可能有助于简化解决方案。
Stack Overflow用户
发布于 2009-04-07 01:47:45
以下是一些很好的近似值：
您可以计算每组的质心，然后根据每组质心的距离进行比较。
另一种方法是散列每一行的坐标，散列到相同位置的行被认为是相似的，因此两组相似性被更新。
一些更多的信息将会有所帮助，例如：
信息是否不断更新?如果是，更新时间间隔是多少。它有多新?它需要多精确？
Stack Overflow用户
发布于 2009-04-07 02:21:39
简单的版本应该是这样的：(不是通过查询分析器运行)
select groupid, min(distance) as mindist
from
(select other.groupid as groupid,
min(abs(other.value - us.value)) as distance
from g us
join g other on other.groupid != us.groupid
where us.groupid = ?)
order by mindist
group by groupid然后，为了利用索引：
select groupid, min(abs(value - usvalue)) as mindist
from
(select other.groupid as groupid,
max(other.value) as value,
us.value as usvalue
from g us
join g other on other.groupid != us.groupid and other.value <= us.value
where us.groupid = ?
union
select other.groupid as groupid,
min(other.value) as value,
us.value as usvalue
from g us
join g other on other.groupid != us.groupid and other.value >= us.value
where us.groupid = ?)
order by mindist
group by groupid这将有望允许mysql使用索引来快速找到连接上最近的邻居。
这里面可能有错误，但希望这条思路能有所帮助。
https://stackoverflow.com/questions/720773
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号