A very interesting talk about Social Graphs

Facebook has probably the largest Social Graph out of there. In a social graph you have Friends of Friends relationships (FoF) and Object of Friends (OoF) relations. All those relations are used to perform a form of social ranking at search time which is personalized according to the interest of your own social community.

This turns out to be a nice graph problem, where you need to efficiently compute a prefix search on the huge social graph, with 4x10^8 nodes and 7.7x10^10 edges in FoF and 10^9 nodes and 10^10 edges in OoF.

Four options have been explored:

1. a classical trie which is very expensive for pointer memory consumption;
2. a sorted vector searched with range queries and binary search which doesn't scale and it is expensive in terms of dynamic insertion;
3. brute force search;
4. a version bloom filtered architecture, which optimizes brute force search;