I am not 100% positive, and I don't work for FB, but it is my understanding that FB doesn't need to look at your cache to determine who you may know. There are several factors to consider in determining if someone may know someone that FB uses. The weight of each factor combined determines the likelihood of the individuals knowing each other. Some of those factors are in no particular order:
1. Mutual friends
1a. If Friend X talks to Person Y a lot, and you a friends with Friend X and you talk to Friend X lot via liking and commenting on FB, there is a higher chance of you knowing Person Y. Compared to if you are just friends with Friend X and don't really communicate with them.
2. Education - did you go to the same school or are you friends with people that went to the same schools.
3. Community - do you live in the same community, city, state.
4. Work - have you worked together or for the same company. Are you friends with people that work with him or her.
5. Are you in a photo, or same album, posted to FB with this individual. For example, if Friend X creates an album and uploads 100 photos to that album. If you are in some of the photos with Friend X and Person Y is in some of the photos with Friend X there may be a good chance you know each other.
6. Did you choose to share your contacts with FB such as using Gmail or Yahoo email?
