Earlier this week, we added the ability to tag location in stories published from apps on the open graph. Like with any update you make from your composer, location can now be added to any photo, link, or update written from an app back to Facebook, allowing people to add more context to their stories.
Since we launched Places in 2010, several key evolutions of location on Facebook have made it possible for us to support this new functionality, both on our site and on the platform. To make adding location as useful as possible, we’ve spent the past year and a half making location tagging universal, devising a new way to present your check-ins on Timeline, and creating ways for apps to engage with where you’ve been and where you want to go next.
Making location tagging universal
While Places was an easy way for people to share where they were, we soon realized that the places people have gone in the past are just as integral to their identity as what they did there and who they were with. So in August 2011, we focused on making it as easy as possible for people to share their location, no matter what kind of updates they were posting. To do this, our first step was to change the concept of location from being a specific type of information people broadcasted via their mobile phones, to metadata that you could add to any experience in your life. We added the ability to tag all your photos and statuses with location to provide useful context for the moments they represented.
A major component of the first version of Places that we needed to rework was the ability to search for places in the vicinity of the user’s current location. For checking in, we would first request permission to use the GPS API to fetch the current location for a person. If we were granted access to this data, the candidate set of places could be restricted to a small area. We divided the globe into a large number of small polygons, and all “places” in the world were stored in memory and indexed to their respective polygons. While sufficient for the original use case, this infrastructure restricted the ability of a user to incorporate location into their Facebook profile. For instance, you could not add location to your vacation photos uploaded from a camera. You also couldn’t specify the places you had visited retroactively.
When we redesigned the Facebook composer, a clear goal was to allow users to add location to any content that they have shared on the site. This made searching for places much harder to process since the user could potentially be searching for any place in the world, irrespective of their current location. To cope with this huge dataset, we changed the infrastructure to optimize for quick lookup of all possible candidate places.
Building a global places directory for every phone
Rather than indexing a place to a single polygon, we assigned four different polygons of increasing size to each place. All “places” in the world were indexed by each of these polygons and also by the first three letters for each word in the place name. Given a query, places matching the first three letters of the query were fetched and intersected with the list of places in all four polygons containing the user’s current location. Depending on the use case, results can be biased toward places closer to the user or provide completely global search. Since the candidate set of places increases significantly in this new system, ranking each of these places to find those that are most relevant to the current user becomes very important. With each place in the index, we store a large set of features to improve ranking, including check-ins and likes received by the place and our best estimate for the opening/closing time for the place.
The original check-in feature was restricted to smartphones that support fetching the current location for the user via GPS, but this was a big limitation for a significant portion of people who access Facebook mobile from phones that don’t have this capability. However, developing the universal search infrastructure allowed us to work around this issue and provide users the ability to search for places on any phone, improving search quality with location if it’s available. This significantly increased the set of users who could check in to a place via their mobile phones.
Data fetching for the map
While the new composer provided a way for people to add location to all of their content, the current profile design did not surface this information into interesting, easy-to-digest stories on their profiles. So when we created Timeline, we designed the timeline map as an integral part. This creates a single place that can surface every place you’ve checked into, as well as the photos and statuses you uploaded at those places. Now, when your friends visit your profile, they can go to your map and quickly get an idea of the cities you have lived in, the trips you’ve taken, and the places you visited during those trips.
Building the timeline map was a unique challenge. Most pages on Facebook display data chronologically, so any single page is only required to fetch the last 20 to 30 pieces of content, and more data is fetched as required when the user scrolls down. Through this process, any single call to the server is only required to fetch a fixed amount of data from the databases. Conversely, the timeline map requires that we fetch every piece of content that the user has created with location. To manage this data load, we created infrastructure to farm out data fetching to multiple servers. On every page load, a single server fetches the IDs of all pieces of content that can be displayed for the current user. This server then breaks up this data into smaller chunks, and each chunk is sent in a request to another server to actually fetch the data and do privacy checks. The responses from these servers is then combined to create the timeline map display.
Aggregation algorithms for location pins
Building the logic for aggregating pins on the map was another interesting challenge because we wanted to choose an optimal algorithm for aggregation while ensuring that we show as many distinct pins as possible. One of our first, more optimistic options was to aggregate any two points that overlapped, but this would distort the order of the pins. Another option we explored was to always aggregate the pins that are closest to each other to make the solution deterministic, but this turned out to be too slow. Instead, an engineer on our team, Jon McCord, wrote an algorithm to deterministically draw these pins. At any point in time, two pins were aggregated only if they were each other’s closest neighbor. This was compared with all other pins to find another pin that satisfied this property. If found, the two pins were aggregated into a single pin. This process was followed until no overlapping pins remained.
Location suggestions
While the timeline map gives users an easy way to present their life in terms of the places they have visited, until now the content on the map was restricted to content that people had created since the launch of the redesign and any content that they went back and tagged with location. This means that all the albums and photos that users uploaded before this launch would not show up on this view. So, we created systems that iterate through all the albums uploaded by a user and search the title and location fields for text that could signify the place at which the album could have been taken. Searching for cities and country names in these fields provides a high degree of accuracy. Based on our guess for the location of the album, we display a unit to the users to approve the location for their album. We also built a special flow allowing you to seamlessly tag your existing photos with location and immediately add them to your map.
Launching location APIs
Moving forward, we want to make the timeline map a single source for people to display the places they’ve visited, and an important part of this is making it possible for other applications to add content to this map. We are launching APIs to allow applications that have obtained user permission to post content with location tags directly onto this map. We’re also improving the API for place search to allow applications to access universal search requests so they don’t need to build their own location search capabilities. For instance, different travel sites can publish people’s recent vacations to their maps so they can easily share this data with their social graph. Mobile apps that obtain user opt-in can add this metadata to content shared via the application to add more context to people’s activity. Facebook can also create custom aggregations, such as all the tourist attractions you visited on your recent trip to Europe, to allow people to easily curate and share this information on their profile.
We are also launching APIs to allow applications to read this data. With permission, it will allow any application that a person is interacting with to access the places that that person and their friends have visited. This will allow travel apps to create trip suggestions based on vacations taken by your friends or suggest customized experiences to people based on their current location. A person arriving in a new city can get restaurant suggestions, hotel recommendations, and advice on the best gyms to use based on the places their friends in the area frequent to make the experience easier.
The eight engineers building location and timeline map worked together across the Timeline, Places, mobile, search, and tagging teams to create fun and useful ways to link the information we share on Facebook through location. With mobile phones quickly becoming one of the main interfaces people are using to consume data, providing spacial relevance like where a photo was taken or what restaurants are popular nearby becomes very important. We want to make it as easy as possible for new applications to incorporate location data into their content and surface not only socially relevant, but also spacially relevant content to provide people with the best experience possible.
