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,4>    <2,1,3>    <3,4>    <4,3>
<1,4,2>    <3,2>    <4,2>
<1,4>    <3,2>    <2,1>    <3,1>    <4,1>
<1,1>

这个等价类的所有代表对前两个维度的投影产生.

<1,2>    <1,3>    <1,4>
<2,1>    <2,3>    <2,4>
<3,4>
<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次.

我希望我误解了你或犯了错误.否则,这听起来真的很有挑战性,也不可行.

我想到的是对矢量组件进行排序并尝试匹配它们.使用曼哈顿距离 – 如果可能 – 可能有助于简化解决方案.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!