How to compute similarity between users given their ratings?

I'm going to use a hypothetical Netflix as an example. Let's pretend they have 1,000,000 users and allow users to rate shows from 1 to 5 stars, and there are 500 shows total. Let's also say the users don't have to rate each show, but most will get pretty close to rating all of them.

The objective is to be able to sort these users by similarity in postgres, such that any arbitrary user will be able to query for and paginate through the users most similar to them, ordered by this similarity.

I suppose I would either want to use the Euclidean distance or the Manhattan distance (faster due to no square root?) to compute this similarity number.

The problem is that this query is very expensive. If there are 1,000,000 users, to sort by similarity, you have to compare your 500 answers against all the other 999,999 users. That's around 999,999 * 500 = 499,999,500 calculations.

I've been trying to find a good way to solve this, but am not having much luck, because I don't have a math background in the slightest, and the articles about the various techniques are very overwhelming to try and understand.

At first I found out about random projection, but it looks like it may not conserve distance/similarity when reducing the dimensions. Someone else also recommended principal component analysis, but I'm not sure how I would do that, or whether or not the 2 dimensional result would contain enough entropy considering the initial vector had 500 dimensions.

I've also toyed with the idea of just saving all NxN pairs, but the resulting database table would require terabytes of data for 1,000,000 users. Not impossible, but the real problem comes in when you have to update 1,000,000 rows when the user changes their rating on something. At that point the insertion speed is too slow to be worth the selection speed being instantaneous.

Does anyone have any ideas or insight? Is this problem just intractable?

• This is called clustering. It requires quite a bit of mathematics. So dive in, or don't bother. You can't expect to get this stuff without knowing the math, Oct 29, 2019 at 22:25
• I'm willing to put the work in, I just need to know exactly what I need to study. Oct 29, 2019 at 22:26
• Do you know linear algebra? Statistics? Basic probability? Oct 29, 2019 at 22:26
• Just the very basics in each. One college class for each. Oct 29, 2019 at 22:27
• If that's what you want, I don't think this is the right place to ask the question. I think you'll get a pretty good understanding of the tools you can use by reading up on k nearest neighbors. I don't think we can do much more than that for you. Oct 29, 2019 at 22:32