Menu
How Facebook built Graph Search and what it means to social media

How Facebook built Graph Search and what it means to social media

In the summer of 2011 Facebook czar Mark Zuckerberg and former Googler Lars Rasmussen, who had joined the company about a year earlier, had a conversation about building a third "pillar" of Facebook.

Facebook's Timeline is a snapshot of a person's life: Who they are, what they do, who their friends are, what they like. Newsfeed is a look into the latest happenings in each user's social network. Graph Search, introduced this week during a private unveiling at the company's headquarters, is a third pillar, Zuckerberg says. It is an advanced search that lets users type in what they're looking for and return results based on their distinctive social surroundings.

Building such a search system is no trivial task. Facebook has 1 billion active users each month who have shared more than 240 billion photos. The social network is a complex web of more than 1 trillion connections of thousands of different types. "Every day, people share billions of pieces of new content, and Graph Search needs those indexed within seconds of their creation," Rasmussen describes. So how did they do it?

FIRST LOOK: Facebook Graph Search 

PRESIDENTIAL INAUGURATION: There's an app for that 

Facebook is fairly mum about its internal operations, although it does give some hints on the company's engineering Facebook page. Database experts, and even those who track Facebook closely don't even know for sure exactly how Facebook built Graph Search, but combining both structured and unstructured data into a unified search tool, which also takes into account the individual privacy settings of each user is undoubtedly a massive technical challenge.

"Searching a database on this scale is massively complex, with the key problem being how to search the entire database without degrading the performance of Facebook itself," says Matt Aslett, a data expert at the 451 Group. "Add in the fact that Facebook is doing a graph search - which not only searches all the data but the relationships between the data - and it is very hard to do efficiently."

Graph Search, Aslett believes, is likely based off of Facebook's internally-developed Tao database, a cached layer on top of Facebook's thousands of sharded MySQL databases, according to a blog post a Facebook engineer wrote last fall describing challenges related to working with cached content.

To create Graph Search, the engineers likely used some combination of open source tools that are available on the market, combined with internally-developed code written specifically for Facebook's extremely unique use case, predicts Jeffrey Kelly, big data expert at The Wikibon Project. Tools like Apache Lucene Solr and Cassandra- used by Netflix to index its movie library in Amazon Web Service's cloud. "FB doesn't use straight off the shelf software and hardware," he says. They can't, they either customize open source technology or develops it in-house.

"None of us had built anything remotely like this before," Rasmussen says in describing the "Under the hood" details of Graph Search beta. No one had built something like Graph Search before because it's a completely new type of search tool, one designed specifically for use by a social network.

Traditional search tools would not do the trick, Rasmussen says. "Using traditional information-retrieval systems to mix keyword and structured queries is fairly well understood," he writes. But Graph Search needs to be able to return results that are more than just a single connection away, he says. And then there's the whole privacy angle. Engineers were able to design a system that combs through the data, but users have in many cases created explicit restrictions on who can see that information. Graph Search needs to ensure that it only creates results that have been shared with the searcher. The more complex the search query, the bigger the challenge is to ensure that whoever is searching does not see something they're not supposed to.

WATCH THAT CARRY-ON: 25 of the wackiest things found by the TSA on travelers 

Initial prototypes included simple graphical user interfaces that users could click through to "build up structured, database-like queries. But they all seemed too complex and not quite up for the full scope of Zuck's challenge to us," Rasmussen writes. Advancements led to a second-generation prototype that was a "naive, exponential-time 'parser' written in JavaScript that could mimic the experience we were looking for as long as the searcher input no more than a few tokens."

And that's basically where Graph Search is today. Facebook officials have stressed that Graph Search is still very young. It's only open to select users - there's already a waiting list you can request to be on - and Graph Search only searches people, photos, places and interests. It's not yet available on mobile devices, nor in languages other than English. It's also not searching timeline posts and comments - by far the biggest dataset for Graph Search, Facebook says.

Facebook is betting big on Graph Search though, even calling it the third pillar of the social network. In an article about Graph Search that came out the same hour Facebook announced the tool, Wired reporter Steven Levy notes that in Graph Search, the Facebook logo is replaced with an F - the search toolbar actually kicked Facebook's name off its own network. A patent Facebook received in November 2012 could be Facebook's signal that it has bet heavily on Graph Search as being a major initiative for the company.

Levy writes that Graph Search is "fundamentally different from web search." Because of the trove of data Facebook has about users, "we can answer a set of questions that no one else can really answer," Zuckerberg told Wired. Levy, the Wired author, notes that "nobody has feared this day more than Google, which suddenly faces a competitor able to index tons of data that Google's own search engine can't access."

APPLE INNOVATION: 15 of the boldest designs by Apple 

Facebook engineering manager Kari Lee explains in a video announcing Graph Search: "In web search it's very often the case that if you do a search for apple and I do search for apple, that we'll basically get the same results," she says. "On Facebook, when you do the same searches, you get completely different results because of the depth of personalization we do."

This could allow Facebook, using Graph Search, to eat other social networks for lunch. Zuckerbeg notes his newfound ability with Graph Search to find engineers at Google who are Facebook friends with Facebook employees - a direct swipe at professional networking site LinkedIn. Online dating sites? With Graph Search, users can search for single friends of friends in a specific geographic area, digging right into the wheel-house of popular dating sites like Match.com or eHarmony.

So has Facebook revolutionized search? Time will tell, says Susan Etlinger, a data expert at the Altimeter group. Graph Search does have its limitations though, she points out. While Facebook has data that Google doesn't, that statement is true the other way around too. Graph Search, for one, is inherently limited by the social network of the searcher, and Facebook's users. Facebook doesn't allow users younger than the age of 13 to create an account, she adds. "Google has a much larger base dataset," she notes. "Basically anyone with an Internet connection."

Still, Eltinger believes Graph Search could be a game changer for the search and social networking industry by personalizing search. "There just hasn't been a platform that's been this truly personal in nature," she says. "Graph Search results are related directly to your friends, interests and connections. That's a powerful tool."

Network World staff writer Brandon Butler covers cloud computing and social collaboration. He can be reached at BButler@nww.com and found on Twitter at @BButlerNWW.

Read more about lans and routers in Network World's LANs & Routers section.

Join the CIO Australia group on LinkedIn. The group is open to CIOs, IT Directors, COOs, CTOs and senior IT managers.

Join the newsletter!

Or

Sign up to gain exclusive access to email subscriptions, event invitations, competitions, giveaways, and much more.

Membership is free, and your security and privacy remain protected. View our privacy policy before signing up.

Error: Please check your email address.

Tags social mediainternetunified communicationsGoogleFacebookNetworkingsoftwareapplicationsWeb 2.0Internet-based applications and servicesNTIGraph SearchFacebook Graph Searchdatabase searchdatabase tools

Show Comments
[]