假设我们有一个包含两列的表
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次.
我希望我误解了你或犯了错误.否则,这听起来真的很有挑战性,也不可行.
我想到的是对矢量组件进行排序并尝试匹配它们.使用曼哈顿距离 – 如果可能 – 可能有助于简化解决方案.
