ClueWeb 09

ClueWeb is a wonderful Web dataset available for the research community. I

• 1,040,809,705 web pages, in 10 languages
• 5 TB, compressed. (25 TB, uncompressed.)
• Unique URLs: 4,780,950,903 (325 GB uncompressed, 105 GB compressed)
• Total Outlinks: 7,944,351,835 (71 GB uncompressed, 24 GB compressed)
  

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;
   

Number puzzle

I was not able to solve it: if an integer n has just 3 factors, how many factors has n^2. Today I learned something new.

A lillte puzzle with balls

Little interview puzzle: A container is filled up with balls. Each ball has a value. Red = 7, Yellow = 5, Green = 2, Blue 2. Some balls are removed from the container and the product of their value is 147,000. How many red balls have been removed?

Lycos from 13 billions (2001) to 36 millions (2010)

Lycos has been sold once again, from 13 billions back in 2001 down to 36 millions in 2010. Lycos was probably the first search engine ever. I started playing with search engines back in 1994, with `pursuit` the CMU open source code, later on evolved into the Lycos code.

Technology was really good at that time, but people belived that "You cannot make money with search" or "Search is nothing, Portal is the future". Later on this became "You cannot compete with Google, you need to make something different".

Forecast: Facebook will surpass Yahoo during next month

Solution to the Facebook programming puzzle of "mutual likes"

Disclaimer, you need to create your own Facebook working access_token and replace it in the below urls

• These are your friends [ https://graph.facebook.com/me/friends?access_token= ]

{
"data": [
  {
     "name": "",
     "id": "31913"
  },
  {

• This is what you like [ https://graph.facebook.com/me/friends?access_token= ]
  

{
"data": [
   {
      "name": "Information theory",
      "category": "Field of study",
      "id": "107921045903425",
      "created_time": "2010-08-20T17:47:47+0000"
   },
   {
      "name": "Data modeling",
      "category": "Interest",
      "id": "107298675966720",
      "created_time": "2010-08-20T17:47:18+0000"
   },
   {
      "name": "Statistical inference",
      "category": "Interest",
      "id": "108195032537847",
      "created_time": "2010-08-20T17:46:49+0000"
   },

• This is what my friend Tony likes [ https://graph.facebook.com/1452108295/likes?access_token=]
  

{
"data": [
   {
      "name": "BB King",
      "category": "Musicians",
      "id": "43780515976",
      "created_time": "2010-07-20T19:57:00+0000"
   },
   {
      "name": "Luciano Moggi",
      "category": "Public_figures_other",
      "id": "56461948713",
      "created_time": "2010-07-09T08:12:34+0000"
   },
   {
      "name": "Bing Jobs Europe",
      "category": "Technology",
      "id": "132723843410879",
      "created_time": "2010-06-30T15:13:13+0000"
   },
   {
      "name": "10 Worst Tattoo Spelling Mistakes EVER!!!",
      "category": "Public figure",
      "id": "133641006660295",
      "created_time": "2010-06-27T12:02:37+0000"
   },

Therefore the solution is to enumerate all your friends, get their ids, get what they likes and intersect with what you like.

Since the puzzle requires to "The problem is to find the friend who shares the most number of items with you", you can simply store all your "like ids" and then, for each friend, count how many likes ids you have in common. You just need to store the current maximum, and the correspondent friend id.

Facebook opened an office in seattle, with a puzzle

Disclaimer. I don't like many puzzles, unless there is some math or algorithm intuition behind them. So, Facebook is going to Seattle and they have a puzzle. Here it is. 

Let's see: 

The first occurrence of 'e' comes before 1 occurrence of 's'.
The first occurrence of 'i' comes before 1 occurrence of 'n'.
The first occurrence of 'i' comes before 1 occurrence of 'i'.
The first occurrence of 'n' comes before 2 occurrences of 'e'.
The first occurrence of 'e' comes before 1 occurrence of 'e'.
The first occurrence of 'i' comes before 1 occurrence of 'v'.
The first occurrence of 'n' comes before 1 occurrence of 'i'.
The first occurrence of 'n' comes before 1 occurrence of 'v'.
The first occurrence of 'i' comes before 1 occurrence of 's'.
The first occurrence of 't' comes before 1 occurrence of 's'.
The first occurrence of 'v' comes before 1 occurrence of 's'.
The first occurrence of 'v' comes before 2 occurrences of 'e'.
The first occurrence of 't' comes before 2 occurrences of 'e'.
The first occurrence of 'i' comes before 2 occurrences of 'e'.
The first occurrence of 'v' comes before 1 occurrence of 't'.
The first occurrence of 'n' comes before 1 occurrence of 't'.
The first occurrence of 'v' comes before 1 occurrence of 'i'.
The first occurrence of 'i' comes before 1 occurrence of 't'.
The first occurrence of 'n' comes before 1 occurrence of 's'

• What is the dictionary of distinct letters? This is given by the symbols used for the above rules. Therefore: i, n, e, v, t, s, 
• Are there repetitions? yes, "2 occurrences of e" and "2 occurrences of i". So the letters are D={i, n, e, v, t, s, e, i} and the string has length 7 because all the rules are given
• So the solution is an anagram of D which respects the rules

I am too lazy to test all the rules, let's test the solution directly 

http://www.facebook.com/seattle/invitees/

MemCached @ Facebook

Interesting talk about MemCached usage at Facebook. Optimizations are about using UPD, tuning memory allocation, and synchronizing different datacenters. Interestingly enough the memory allocation problem is similar to the one seen for vectors allocation in STL.

An interesting post about hacking culture

Apparently hacking culture is seen as a value by a lot of people.

• What happened to Yahoo?

An hidden gem: Peter Norvig (Google) talks at Facebook about machine learning

Don't be surprised. I work @ Microsoft and I am pointing out this hidden gem. A public talk that Peter Norvig gave at Facebook about machine learning. Peter Norvig is the Director of Research at Google and his talk is about different problems including segmentation, spelling, building n-grams on web scale, Google set (kind of related words) and machine translation.

It seems to me that the lesson suggested is to build "simple probabilistic models" applied to a lot of data, rather then to adopt complex models working on small datasets.

Off-Topic: Real Virtuality

Puzzle: Slicing a pizza in 3 parts

This is a nice puzzle when you are with your friends and you eat a pizza. There are two guys and a pizza. How can you cut the pizza so that everyone is happy about the slice received? This is pretty easy for 2 guys, but how about 3 guys and , more generally, n guys?

Facebook UI Front-end technologies

I am not a UI expert, but I do enjoyed this FB presentation about how to optimize UIs. At the end is a matter of reducing communications, re-use common patterns, event delegations and be as much lazy as possible. Surprisingly enough you should also care about making things easy but not so easy...

Yahoo changes its API

Yahoo! announced its search changes:

"On October 1, 2010, we will close the SearchMonkey developer tool, gallery, and app preferences"

"The Yahoo! Site Explorer team is planning tighter integration between Site Explorer and Bing Webmaster Center to make the transition as smooth as possible for webmasters"

"Several search-related web services will continue to be supported, but strictly through YQL. These include the Yahoo! Term Extraction Web Service, Related Suggestion, and Spelling Suggestion. Other non-BOSS search APIs such as Web Search, Image Search, News Search and Site Explorer APIs will shut down with no further support in YQL"

"Search remains critical to Yahoo! and we’re happy to announce that we will continue to offer the BOSS program (Build your Own Search Service). In the not too distant future, BOSS will provide web and image search results from Microsoft along with other search-related services and content from Yahoo!, such as news"

A DryadLINQ Tool Kit for Information Retrieval

Some of the tools used in Microsoft for information retrieval

Haystack the Facebook Fileserver

Haystack is the Facebook fileserver for photos. Instead of using costly NFS operations (as they did in the past) they adopted a simple log based file where the typical operation is an append to an already open file. Obviously they have a separate index structure, and many cache server in front of the system.

This is a typical solution when you have a lot of new objects inserted in the system (and a limited amount of delete operation). If you have many delete, you probably should consider something like the COSS (Cyclic Object Storage System) developed for Squid.

Esemble of Classifiers (part I)

Ensemble of Classifiers is a powerful machine learning technique where several (weak) classifiers are combined to obtain a more powerful classifier.

In this code skeleton, a generic Classifier class is defined which takes a generic input T1 type as input and classifies (transforms) into a generic type T2 (the categories). The generic classifier is then specialized into a weak classifier class with T1 = vector [integer] and T2 = bool. The weak classifier has some random noise which is used to generate mistakes.

A collection of weak classifiers will be then combined into an ensembles of classifiers, in the next days.

Jennifer ;-)

Jennifer!

China goes search mode

Xinhua, China Mobile to establish internet search engine joint venture.

"Called "Search Engine New Media International Communications Co.," the joint venture will focus on creating a leading search engine while actively developing other businesses, including the internet, print media and advertising, said Zhou Xisheng, vice president of Xinhua, at a signing ceremony.

"Search engines, which have powerful information integration abilities, play an increasingly important role in disseminating information and influencing public opinion," he said."