1

There are thousands (or tens of thousands) of possible movie titles. New user enters my website and selects hundreds of titles that he likes.

The only single goal of my website is to output the list of other users that liked exact same titles, but with only very minor differences - say, only 1-5 titles between users are different.

The solution I see is straightforward - take input from new user, iterate over every row in database to compare it with every other user, output the result.

But I want to solve it with millions (or tens of millions) of users in mind - and the straightforward solution of course doesn't scale well at all.

I feel like maybe my lack of formal education with algorithms/data structures is limiting my thinking here - how could I implement a more efficient solution?

Note that I don't want to categorize users in vague buckets that have common interests - I want to match exact titles between users as precisely as possible - so it's not your usual common recommendation system, I guess.

  • 2
    1) Your matrix is too sparse. Even if your users are inputting hundreds of movies, the number of entries with 97% or higher overlap is going to be zero 2) Worry about the solution for millions of users when you have a hundred thousand users. – Philip Kendall Jul 12 at 17:02
  • It's unclear to me what the problem is here. In a typical database, titles and users are going to be encoded as numbers. Once that occurs, what remains is just a set theory problem. – Robert Harvey Jul 12 at 19:15
  • Ok, assuming you don't need an instantaneous answer to your query, have a look at a map-reduce solution like Hadoop. – Robert Harvey Jul 13 at 1:14
1

Any algorithm that requires you to compare each set to every other set is doomed to failure. It's an O(n2) problem.

The classic way around this is either minhash + LSH, or, if you only wish to detect near-identical sets of titles, simhash.

Both approaches reduce it down to an O(n.log(n)) problem. Both are statistically based: they are not guaranteed to find every similar pair above your chosen similarity threshold (though with minhash you can lower the threshold to increase the chance of finding highly similar pairs, then do further comparisons to strip out the pairs you don't want).

Minhash + LSH is relatively simple. Broadly speaking, it generates a set of, say, 50 hashes per user, and looks in a hash dictionary to see which of them are shared with which other users. Users that share more than, say, 40 hashes will have quite similar title sets. In your case, with tens of millions of users and a relatively small universe of possible features (movie titles), you should certainly not use minhash without LSH. Here's a good explanation of it.

Simhash is more complex to understand and implement, but it is faster and typically requires a less storage. With simhash you'd generate only one hash per user, and the hashes are generated in such a way that small changes in the set of movie titles will result in only a few bits (if any) changing in the hash. The resulting hashes are then stored in various permutations in a set of tables cleverly organised so that very similar hashes (with small Hamming distance) will always be found in close proximity in at least one of these tables. Simhash has strict limits on how many bits difference can be detected: typically it is as low as 2, 3 or 4 bits difference in a 64-bit hash, depending on how the permuted tables are set up. So only very similar sets of movie titles will be detected.

Generating the simhashes themselves is pretty simple. Effectively you hash each of the user's movie titles to a (say) 64 bit hash using something like FNV-1a, then do a kind of bitwise average of all those hashes (see this explanation). The tricky part is solving the Hamming distance problem, without which simhashes aren't much use. Here's the paper explaining solving the Hamming distance problem. I couldn't find a clearer explanation online.

2

What comes to mind is Levenshtein distance algorithm. It computes the number of changes (insertions, deletions or substitutions) needed to transform one array into another. It is used in general to compare strings (not just to know if a string is equal or not to another one, but how close a string is to another), but can be adapted for virtually any array (in your case, this would be an array of numbers).

Benefits:

  • The algorithm is very popular and used a lot, which means that you probably don't have to write any code: just grab a library implementing Levenshtein distance in your language and use it.

  • A distance is exactly what you are looking for; in other words, there would be a threshold that you'll define which would determine whether two arrays are close enough to befriend two users, or not.

Example:

  • User 1 favorite movies are [3, 6, 7, 9].
  • User 2 favorites are [1, 3, 6, 8].

Levenshtein distance would be 3 (adding one, replacing seven by six, removing nine).

  • Can you elaborate on "list of numbers"? Binary "likes and dislikes" from a list of movie titles is not an obvious transformation unless it's a string of ones and zeros. – candied_orange Jul 12 at 18:45
  • I'm not sure that the OP's problem is getting exact matches from inexact titles. – Robert Harvey Jul 12 at 19:14
  • @candied_orange: I added an example which should make it all explicit. Just like strings are simply arrays of characters, the favorites of a user are just arrays of numbers, every number being an identifier of a given movie. I suppose that the example also answers Robert's comment as well. – Arseni Mourzenko Jul 12 at 19:36
  • @ArseniMourzenko looks like your numbers are ID's. So long as the strings of IDs are sorted this should work. Robert's comment seems to be about fixing typos. I was assuming users selecting from a list of exact titles. – candied_orange Jul 12 at 21:45
  • Unfortunately, this approach requires comparing every user's set of titles against every other user's set. With 10 million users, that would require nearly 50 trillion comparisons. It's a non-starter. Also, Levenstein distance is for comparing sequences in which order is important. Movie titles are not an ordered sequence. A far simpler measure of "distance" between two sets of movies is simply to count how many titles are not shared, or for a "similarity" measure, calculate Jaccard similarity (size of intersection / size of union). Minhash and simhash both approximate Jaccard similarity. – Ben Whitmore Jul 31 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.