SQL 高效最近邻查询

Question

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

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

groupId : int 
value : float

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

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

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

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

干杯，

Sören

Answer 1

你能确认我的问题是对的吗？

您的表表示由 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 次。

我希望我误解了你或犯了一个错误。否则，这听起来介于真正具有挑战性和不可行之间。

我想到的事情是订购矢量组件并尝试匹配它们。如果可能的话，使用曼哈顿距离可能有助于简化解决方案。