5

What is the best method to do location disambiguation for geonames data?

There are some scoring algorithm for geonames search, but they do not open source it and I'm not sure they are very sophisticated. (i.e. for soma, ca it returns Soma lake in Canada which haven't even wikipedia article, instead of very popular Soma Neirbohood in san francisco)

There also some works I have found in google scholar, but they seems very shallow and similar with my heuristics like scoring by something(log(population) + 1000*hasWikipedia(article)+ isCity100+isCapital(10)).

My domain in travel articles so my scoring function should provide most probable tourist places(cities, place of interest(Disneyland, colleseum, big ben)).

Do you know any important article in this field, or algorithms used in production by Google maps, yahoo, bing or even geonames?

yura
  • 14,489
  • 21
  • 77
  • 126
  • It's a bounty question... 'retag-ing' will bring more visitors. Please, I would like someone to add tags. (I don't have a 500+ rep). _Suggestion of what I think are good tags to add_; [string-matching] [search] [algorithm]. – r4. Jun 27 '12 at 06:19
  • @OlofAdler we can add maximum 5 tag – Hector Jun 30 '12 at 05:21
  • added string-matching as the 5th tag. – john.k.doe Jun 30 '12 at 22:30

1 Answers1

3

@yura, this isn't what you're looking for, but I don't think any clever algorithm will be able to consistently disambiguate whether queries like "soma ca" refer to Soma in San Fran or Soma Lake in Canada. The problem is not that your algorithm is not sophisticated enough; the problem is that there is simply not enough information in the query "soma ca".

I don't know how to express it clearly, but there is an information theoretic thing going on here. It's like the way that random data can't be compressed losslessly: there's not enough information in the input to compute the desired output.

Even if a human was to interpret your queries manually, they would not necessarily understand that "soma ca" is supposed to mean Soma in SF. Maybe to you a 2-letter abbreviation like "ca" "naturally" refers to a US state rather than a foreign country, but there is nothing fundamentally "correct" about that choice, and it cannot be derived using pure logic. It's an arbitrary, domain-specific, ad-hoc rule, just like the ad-hoc log(population) heuristic which you referred to.

Some possible "solutions" (aside from designing a telepathic computer which can read users' minds):

  1. Provide users a list of possible matches for each query. Keep track of the ones they choose, and when other users later type the same query, order the results by popularity.
  2. OR, once you gather lots of data on the popularity of query results, you may even be able to mine the data with machine-learning algorithms, and derive better heuristics from it.
  3. Or, before putting the application into production use, you could first compile a body of fake queries, along with the results which you think your algorithm should yield for each such query. Then use your machine-learning algorithms on that.
  4. Compile a body of fake queries and desired responses, OR get the data from the choices of real users, and use that data to benchmark the accuracy of your manually designed and coded ranking heuristics. Keep inventing new heuristics until you find one which achieves high accuracy on your test data set.
Alex D
  • 29,755
  • 7
  • 80
  • 126