How to suggest friends to an user like Facebook does

Hi, I need to implement a feature which is basically similar to facebook’s suggestion feature. So I need a list of people based on number of friends in common. Example:

  • A is friends with B, C, D, E, F.
  • B, C, and D are friends with X
  • E, F are friends with Y

So in this case I need a list that would contain X, Y. And X must be before Y in the list, because X has 3 friends in common with A, while Y has 2 friends in common with A.

The problem is that we need a way to generate this list for any logged in user, in a system that has hundreds of users. So my question is how to generate this list efficiently.

I’m using Redis to store user’s friends. So in the example above, A’s friends’ IDs are stored in a set. But I may use any kind of database you suggest to solve this problem.

Thanks