Facebook Graph Search and problems with synthetic suggestions

I spent sometime playing with the suggestions mined by Facebook for their recent Graph Search. It seems to me that many of them are synthetic e.g. they are generated by mining the friends's graph and not the queries past queries submitted by users.

This approach seems to create many nonsensical suggestions. In this example, I was searching {hotels in new york city close} and the top suggestions are "hotels in new york city close to London", which is clearly a no sense. It seems to me that they are using some kind of frequent itemset algorithm and they notice that I have many friends in London, hence the  synthetically generated nonsensical suggestion. As you see, Bing suggestions are not suffering this problem and correct locations are shown.

Another example: I am an Italian guy and for me Milan is in Italy (btw, this Milan is way more popular on the Web that the one in Tennessee). Plus, none of those Milan cities are near to London. Web suggestions are nailing the correct location "il duomo" is central area in Milan, Italy.

Here there is another example of nonsensical suggestion. I assume that there are no Google employees who work for Microsoft at the same time. However, both the companies are quite popular in my social network hence the synthetic suggestion.

Now, let's consider another class of defects. There are queries which are not directly answered and the proposed suggestions are quite unrelated. In this example, I was searching for {actors who won the oscar} and Facebook graph search suggestions are clearly unrelated since I am not interested in "actors who like Oscar wilde"

Here there is another example of unrelated suggestion. I am searching {visit the taja} and this is not related to   "People named 'taja' who work at Visit Holland". In this case the semantic of the query is quite not understood.

If you try to replicate my examples, please note that you could get a different set of suggestions because those are generated by using your personal friend graph. However, it would be easy to generate similar situations once you understand the pattern.

See also my past postings:

http://codingplayground.blogspot.co.uk/2013/01/spelling-spelling-spelling-facebook.html

http://codingplayground.blogspot.co.uk/2013/01/facebook-graph-search-with-bing-web.html

Spelling, Spelling, Spelling. Facebook Graph Search and Bing Web Search

Continuing with my personal analysis on the Facebook Graph Search and Bing Web Search's integration,  here is another example of why you can get the best of two worlds. In this case, I will discuss misspelled words, a common problem for English (see for instance this funny article: "Why misspelled names are so common and what journalists are doing to prevent them").

Let's suppose that users start to type the word {swarzin}: their intent is to get information about the actor, but they are unsure of the correct spelling. As you see in the below image, Bing’s Speller processes tens of millions of data points mined from searches, web pages, clicks and user actions to help you find the right “Schwarzenegger".

Another example is {terramis} a delicious Italina cake of which the correct spelling is {tiramisu} - technically, {terramis} is a mispelled query prefix  for the full query{tiramisu}. Other mispelled prefixes are {bufet warr} and one of the myriad variants of {britnay s}. In all of these cases, Bing nails the correct suggestions and  are integrated into Facebook typeahead search.

Bing has a significant investment in building a state-of-art speller and those technologies are also leveraged by our team in London in securing the right suggestions. In this context, the additional problem is dealing with the mispelled fragments represented by the query prefix, correct the errors and, at the same time, predict which the more relevant suggestions are, and we need to do this every time new characters are typed in real time!

Can you imagine how fast the predictions and corrections need to be?

Facebook Graph Search, with Bing Web Search

Many people asked what are the benefits of merging Facebook internal search (aka Facebook Graph Search), with Bing Web Search results. This is my poster query {Conrad Bain} just died, and Facebook knows many people with that name from their internal data, while Bing nails the name of the actor performing 'Different Strokes' series. 

Try your own queries and give us feedback

The meaning of life

Someone in my team pointed out that now I have an answer to the meaning of the life http://www.bing.com/search?q=42

Facebook Graph Search and Bing Web Search suggestions

You have probably seen the new Facebook Graph Search for searching Facebook internal data. Anytime you search something from the public Web, then you will use the suggestions coming from Bing Web Search. This is a feature run by my team. Congratulation to all of them for driving the amazing team who shipped the core web suggestions feature from London

Calculate the span on a stock

You are given the value of a stock during different days. For each day d, we want to know how many preceding and consecutive day the stock had a value less or equal to the one observed on d.

finding the longest substring with at least k occurrence

Find all the permutations of an array A

Find the lowest common ancestor

For a binary tree for a binary search tree

Serialize and deserialize a generic tree

File * serialize (node * n); node * deserialize (File * f);

Given an array randomize it

Isomorphic trees

Two trees can be called isomorphic if they have similar structure and the only difference amongst them can be is, that their child nodes may or may not be swaped. Write a function to detect whether two trees are isomorphic

int isIsomorphic(Node root1,Node root2) {
   if(root1==null && root2==null)
       return 1;
         
   if((root1 ==  null && root2 != null) || (root1 !=null && root2 == null ))
     return 0;
             
    if(root1.val == root2.val){
             
       if(isIsomorphic(root1.left, root2.left) == 1){
            return (isIsomorphic(root1.right, root2.right));
       } else if(isIsomorphic(root1.left, root2.right) == 1){
            return (isIsomorphic(root1.right, root2.left));
       }
             
    }
         
return 0;
}

Pascal’s triangle is a triangular array of the binomial coefficients

Method 1 -
Each line n is the binomial coefficient C(n, k) where k is the row. This has complexity n^3. because in this case k has the same order of n

Method 2
Complexity n^2, with space n^2

Method 3
complexity n^2, with space O(1) -- this is more difficult because you need to move in the triangle storing just a constant number of locations. Can you express C(n, k) as function of C(n, k-1)?

Compute the binomial coefficient in efficient way

C(n, k) = n ! / (n-k) ! k! = n (n-1) ... (n-k+1) / 1. 2. ... (k-1)k

C(n,k) = C(n, n-k) = n! / (n-n +k)! (n-k)!  so we can change r to r-p is r > p-r and keep the operation smaller


for (i = 0; i < k; i++)
{
    res *= (n - i);
    res /= (i+1);
}

O(k) time and (1) space

Given an array of integers, populate another array with the product of the elements of the first array except for the current index element.

Identify all the pythagorian triplets in the given array.

2 , 4 -> 4 + 16 = 20
1, 3 -> 1 + 9 = 10

In efficient way

BST, kth

 Find the Kth largest integer in a Binary Search Tree. 

Find non-unique characters in a given string

Optimal complexity in time and space

Generic graph with weights

Here the code based on boost::unordered_map

Gas stations

You have a certain number of gas stations in a circle and a car running on the circle. The car has a certain amount of gas available at the beginning. Find the right station to start for not running out of gas

This is a version of max subarray