Tuesday, August 24, 2010

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;

1 comment:

  1. LinkedIn has been solving a similar real-time personalized relevance ranking problem for a few years. They order search results by distance in your social graph.

    ReplyDelete