代码之家 › 专栏 › 技术社区 › black666

适用于n*(n-1)/2算法的MySQL体系结构

scalability architecture database-design mysql

black666 · 技术社区 · 12 年前

我目前正在开发一个网站,用户可以根据属性(年龄、身高、城镇、教育程度等)搜索其他用户。我现在想在用户档案之间实现某种评级。基于两个给定简档之间的相似性,通过其自己的算法来计算评级。例如,用户A与用户B的“匹配评级”分别为85和79。B和C的评分为94,依此类推。。。。

用户应该能够搜索某些属性并通过评级过滤结果。

由于不同的配置文件的评分不同,也取决于进行搜索的用户,我不能简单地在用户表中添加一个字段并使用ORDER BY。到目前为止,我提出了两个解决方案:

我的第一个解决方案是有一个夜间批处理作业,它计算每个可能的用户组合的评级,并将其存储在一个单独的表中(user1,user2,rating)。然后,我可以将此表与用户表连接起来,并根据评级对结果进行排序。做了一些数学运算后,我发现这个解决方案不能很好地扩展。

根据公式n*(n-1)/2,10个用户有45种可能的组合。对于1.000个用户,我突然不得不在我的评分表中插入499.500个评分组合。
第二个解决方案是让MySQL保持原样,只在我的应用程序中动态计算评级。这也不能很好地扩展。比方说,搜索应该只向UI返回100个结果(最高评级在顶部)。如果我有10000个用户,并且我想按评级对居住在纽约的每个用户进行搜索,我必须将居住在纽约市的每个用户加载到我的应用程序中(比如3.000),应用算法,然后只将前100名返回给用户。通过这种方式,我从DB中加载了2.900个无用的用户对象,并在算法上浪费了CPU,而从来没有做过任何事情。

有什么想法吗?我可以在我的MySQL数据库或web应用程序中设计这个,这样用户就可以与其他所有用户进行个人评级,使系统扩展到数千个用户之外?

3 回复 | 直到 12 年前

LSerni 12 年前

如果你必须将每个用户与其他用户进行匹配,那么无论你做什么,算法都是O(N^2)。

如果你可以利用某种一维的“度量”,那么你可以尝试将每个用户与一个单一的合成值相关联。但这很尴尬,而且可能是不可能的。

但您可以做的是注意哪些用户需要改变在他们的配置文件中(每当匹配所基于的任何参数发生变化时)。此时,您可以仅为这些用户批量重新计算表,从而在O(N)中工作:如果您有10000个用户,而只有10个需要重新计算,则必须检查100000条记录,而不是100000000条。

其他策略是只对更有可能被比较的记录运行主算法:在你的例子中,“同一个城市”。或者在更新记录时(但这需要存储(user_1,user_2,ranking,last_calculated),只重新计算那些排名高、非常旧或从未计算过的记录。排名最低的比赛不太可能发生太大变化,以至于在短时间内排名靠前。

更新

该问题也适用于O(N^2) 存储空间 。

如何减少这个空间?我想我可以看到两种方法。一个是不在匹配表中输入一些信息完全。“匹配”功能越有意义,它就越僵硬和陡峭;有一万场“好比赛”意味着匹配意义不大。因此,当User1更改一些关键数据时,我们仍然需要重新计算lotsa,以防它将User1的一些“no”匹配带回“maybe”区域。但我们会为每个用户保留一个较小的活动匹配集团。

存储量仍将呈二次方增长,但增长幅度较小。

另一种策略是 重新计算 匹配,然后我们需要开发一些方法来快速选择哪些用户可能具有良好的匹配(从而限制JOIN检索的行数),以及一些快速计算匹配的方法;这可能需要以某种方式将User1和User2之间的匹配重写为DataUser1、DataUser2的子集的非常简单的函数(可能使用辅助列)。

挑战将是利用MySQL的功能,并将一些计算卸载到MySQL引擎。

为此,您可能会在输入时(因此在O(k)中)将一些数据“映射”到空间信息或字符串,并使用Levenstein距离。

单个用户的存储会增长,但它会线性增长,而不是二次增长,MySQL SPATIAL 索引非常有效。

Ian Clelland 12 年前

如果搜索应该只返回前100个最佳匹配,那么为什么不直接存储这些呢?听起来你无论如何都不想搜索结果的底端,所以不要计算它们。

这样,您的存储空间只有o(n),而不是o(n^2),更新也应该是。如果有人真的想看到超过前100的匹配(而你想让他们),那么你可以选择在这一点上实时运行查询。

Gordon Linoff 12 年前

我同意@Iserni所说的一切。

如果你有一个网络应用程序,用户需要“登录”,那么你可能有机会在那时创建该用户的排名,并将其存储在一个临时表(或现有表中的行)中。

如果计算所需的所有数据都能放入内存,那么这将在合理的时间内(几秒钟)起作用。然后,数据库引擎应该进行完整的表扫描并创建所有评级。

对于一个用户登录来说,这应该工作得相当好。对于两个用户来说,这是可以通过的。但是,如果你有十几个用户在一秒钟内登录,它就不会很好地扩展。

不过,从根本上讲,你的评级并不符合要求。你必须将所有用户与所有用户进行比较才能得到结果。无论是批量(夜间)还是实时(当有人有查询时)都不会改变问题的性质。它将使用大量的计算资源,并且多个用户同时提出请求将是一个瓶颈。