title: How to find similar users using their interests
body: <p>I am trying to create a system which would be able to find users with similar favourite movies/books/interests/etc., much like neighbours on last.fm. Users sharing the most mutual interests would have the highest match and would be displayed in user profiles (5 best matches or so).</p>
  
  <p>Is there <strong>any reasonably fast way</strong> to do this? The obvious solution would be to create a table with user ids and interest ids and compare a user with all the other users, but that would take forever on a table with ... say million users each having 20 interests.</p>
  
  <p>I assume some efficient solution exists, since last.fm is working quite well. I would prefer using some common SQL database like mySQL or pgSQL, but anything would do.</p>
  
  <p>Thanks for your suggestions.</p>
  
  <hr>
  
  <p>UPDATE:<br>
  As it turns out, the biggest problem is finding nearest neighbours in SQL databases, as none of the open-source ones supports this kind of search.<br>
  So my solution would be to modify ANN to run as a service and query it from PHP (using sockets for instance) - having even millions of users with say 7 dimensions in memory is not so much of a big deal and it runs unbelievably fast.</p>
  
  <p>Another solution for smaller datasets is this simple query:</p>
  
  <pre><code>SELECT b.user_id, COUNT(1) AS mutual_interests
  FROM `users_interests` a JOIN `users_interests` b ON (a.interest_id = b.interest_id)
  WHERE a.user_id = 5 AND b.user_id != 5
  GROUP BY b.user_id ORDER BY mutual_interests DESC, b.user_id ASC
  </code></pre>
  
  <p>20-50ms with 100K users each having ~20 interests (of 10 000 possible interests) on average</p>