Finding all users that have common/mutual friends

Hi,

I am building a facebook app - most of my 'simple user' data (name,
address, email, as well as other app specific data) is stored in a
MySQL table. The application make a heavy use of facebook graph
API(friendships, events etc.). I am considering to user Redis to cache
the graph data I get from facebook.

My main 2 use cases are:
1) Search for people that have common friends/events/etc. with me. As
part of the search the list of users is going to be filtered using
other search criteria that are stored in the MySQL table. For example:
All the users that have common friends with me and live in New York.
2) Display the common friends/events/etc. that I have with each
user.

Problem 2 is easy to solve using Redis. I just store a list of friends
for each users, and intersect the 2 sets to find common friends.

Problem 1 is much harder, I can either:
A) First apply the other search criteria using the MySQL table (all
people that live in New York) to create a subset of users.Then find
the mutual friends that  I have with each users. Even if I manage to
somehow keep the subset of users relevantly small (say 1000), it is
still going to take way too long.

B) Pre-calculate the number of common friends for each pair of users.
This is clearly the fastest approach and would also allow me to use
the number of common friends/events/etc in my sort criteria (solr).
But is it going to require a ridiculous amount of space - O(n^2) where
n = #users.

Does anybody have any advice on how to approach the problem?

Regards,
Eugene