April 7, 2014

Deduplicating a Places Database

International World Wide Web Conference (WWW)

By: Philip Bohannon, Nilesh Dalvi, Marian Olteanu, Manish Raghavan

Abstract

We consider the problem of resolving duplicates in a database of places, where a place is defined as any entity that has a name and a physical location. When other auxiliary attributes like phone and full address are not available, deduplication based solely on names and approximate location becomes an extremely challenging problem that requires both domain knowledge as well an local geographical knowledge. For example, the pairs ”Newpark Mall Gap Outlet” and ”Newpark Mall Sears Outlet” have a high string similarity, but determining that they are different requires the domain knowledge that they represent two different store names in the same mall. Similarly, in most parts of the world, a local business called ”CentralParkCafe” might simply be referred to by ”Central Park”, except in New York, where the key- word ”Cafe” in the name becomes important to differentiate it from the famous park in the city.

In this paper, we present a language model that can encapsulate both domain knowledge as well as local geographical knowledge. We also present unsupervised techniques that can learn such a model from a database of places. Finally, we present deduplication techniques based on such a model, and we demonstrate, using real datasets, that our techniques are much more effective than simple TF-IDF based models in resolving duplicates. Our techniques are used in production at Facebook for deduplicating the Checkins Places database.