7

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

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

groupId : int 
value : float

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

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

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

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

干杯，

Sören
4

4 回答 4

4

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

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

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

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

于 2009-04-06T19:14:22.740 回答
1

Here are some nice approximations:

You could calculate the center of mass of each group and then compare based on the distance of each groups center of mass.

Another way you could do it is by hash the coordinates of each row and rows that hash to the same location are considered similar and thus the two groups similarity are updated.

Some more information would be helpful such as:

Is the information constantly being updated and if so at what interval. How up to date and how accurate does it need to be?

于 2009-04-07T01:47:44.747 回答
0

天真的版本是这样的：（不通过查询分析器运行）

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 使用索引来快速找到连接上的最近邻居。

这可能存在错误，但希望这种思路会有所帮助。

于 2009-04-07T02:21:38.533 回答
0

所有浮点值都大于或等于零，但在其他方面是无界的。

如果您想在浮点数上执行 KNN，请使用btree_gistPostgreSQL 模块并创建GIST索引。

此外，对于具有自然距离度量的数据类型，btree_gist 定义了一个距离运算符<->，并为使用此运算符的最近邻搜索提供GiST 索引支持。为 int2、int4、int8、 float4、float8、timestamp with time zone、timestamp without time zone、time without time zone、date、interval、oid 和 money提供了距离运算符。

float8是double precision。

于 2018-08-08T05:24:55.510 回答