如何设置，以找到类似的模式快？

Question

(这是没有家庭作业而没有工作的问题。这只是我的个人兴趣的占领和完全虚构的。但我感兴趣的一个良好的算法或数据结构。)

让我们假设，我要运行一个约会网站。和我的 特殊的功能 就是单身了 配合电影的味道.(为什么不呢？)

在这种情况下，我将需要一种方式来存储的电影的评价对于各个用户。(迄今为止没有问题。) 我会需要一个数据结构，以找到最合适的用户。两个之间的距离口味的模式会之间的平均距离的所有评级，这两个用户。

例

movies   A B C D E F G H I J K L M ...
user Xm  9 5   1   1   5
user Ym      4 6 1         8
user Zf  9   6 4           7

距离(X,Z)=平均(abs(9-9)+abs(1-4))=1.5

距离(Y、Z)=平均(abs(4-6)+abs(6-4)+abs(8-7))=1.666

所以先生X的符合略更好的夫人Z，比先生Y。

我喜欢解决方案，...

• ...不需要很多操作上的数据库
• ...不需要处理大量数据
• ...跑得快
• ...提供最好的匹配
• 好吧，也许我会考虑很好的近似值。

试着记住，这也应当工作与成千上万的可能的电影，用户率只有大约20-50的电影，以及成千上万的用户。

(因为这是一个心理难题，而不是一个真正的问题，工作arrounds是不是真的帮助。)

这将是你的搜索算法或数据结构？

Answer 1

听起来很像 Netflix奖 挑战，更具体地说第一半的最受欢迎的方法。可能实现的是什么你想要做的许多和各种各样的。他们都不是非常有效的，并L1度量并不是特别好的选择为可靠的相关性。

Answer 2

看起来就像你正在寻找 最近的邻居 在影片的空间。和你的距离函数是的 L1指标.你也许可以使用 空间索引 某种。也许你可以使用技术从 合作过滤.

Answer 3

CREATE TABLE data (user INTEGER, movie INTEGER, rate INTEGER);

SELECT  other.user, AVG(ABS(d1.rate - d2.rate)) AS distance
FROM    data me, data other
WHERE   me.user = :user
    AND other.user <> me.user
    AND other.movie = me.movie
GROUP BY
    other.user
ORDER BY
    distance

复杂性将O(n^1.5))，而不是O(n²)，因为会有 n 比较 sqrt(n) 电影(平均水平的电影充满了一起的每一对)。