Bus*_*icK 7 sql nearest-neighbor
我无法提出有效的SQL查询来处理以下情况:
假设我们有一个包含两列的表
groupId : int
value : float
桌子很大(几百万行).每个"groupId"有不同数量的"值" - 比如介于100和50.000之间.所有浮点值都大于或等于零,但在其他方面无限制.
对于给定的groupId,查询应返回通过降低相似性排序的所有其他组,其中"相似"被定义为两组中所有可能的30对值之间的最小欧几里德距离.
相似性的定义是杀死我的原因.我认为,对于如上定义的计算相似性,naiive算法是O(n ^ 2).现在我正在寻找重新定义"相似性"或上述有效实现的想法.我可以想象一个涉及k-最近邻居的解决方案,比如PostGis几何最近邻居或者可能是最大的常见子序列算法(虽然我需要后者的"模糊"实现,因为"值"几乎不会完全相等) .
我们目前正在使用mySQL以防万一.
干杯,
Sören
您能确认我的问题是否正确吗？
您的表表示由 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! 的距离！/（米 - 30）！每个向量的投影。因此，对于 100 维（您的下限），向量有 2.65*10^32 可能的投影。这需要计算投影之间大约 7*10^64 的距离，并找到最小值来找到两个向量的距离。然后重复这个n次。
我希望我误解了你或者犯了一个错误。否则，这听起来确实具有挑战性，但又不可行。
我想到的是对向量分量进行排序并尝试匹配它们。如果可能的话，使用曼哈顿距离可能有助于简化解决方案。