Grouping to extract common values in semi-structured data

Question

I've got a 'somewhat' ugly field in a database which holds the names of locations. For instance, Madison Square Gardens which has also been entered as "The Madison Square Gardens", etc. etc.

I'm trying to extract the data so that I can get an accurate list of all the locations. In order to accomplish this, what I've done is created a sql query where I join the events for each location, and then group by the location name and only use location groups having more than 10 entries (that filters out the somewhat non-reliable entries), but I still end up with Some very different spellings and entries, resulting in duplicate properties/locations.

My SQL query looks like this

"SELECT location, COUNT(*) FROM locations 
JOIN event ON locations.lid=events.lid
WHERE `long`
BETWEEN - 74.419382608696
AND - 73.549817391304
AND lat
BETWEEN 40.314017391304
AND 41.183582608696
GROUP BY location 
HAVING COUNT(*)>10

Running this query provides 3 different entries "Madison Square Garden", "Madison Square Gardens", "The Madison Square Garden". Of course, this is only for the Madison Square Garden entry. Most entries have multiple slightly different spellings.

I restrict my searches by lat/long so I don't get locations with the same name in different cities grouped together.

Is there a way with Regular expressions or something in the GROUP clause to have these grouped consistently? Even just removing the trailing 's', and 'the' before the grouping would probably be a big benefit.

I was going to take each result and then do a regular expression match against all the locations in within the lat/long range?

Fortunately I have enough linked events to locations, that I am somewhat able to recognize the major locations.

Any other suggestions for extracting locations from semi-structured data? The data is scrapped from a variety of sources, so I don't have control over the input.

Answer 1

If your issue is treating "similar" strings the same, you may want to check out the SOUNDEX algorithm. I'm not sure if it will work for all of your different scenarios, but it's a start.

It's discussed in this thread: http://stackoverflow.com/questions/369755/how-do-i-do-a-fuzzy-match-of-company-names-in-mysql-with-php-for-auto-complete

Answer 2

Here are some suggestions for you.

Create a normalized venue-name column in your data base: (1) Run each name through some simple transformations ... Turn "The Madison Square Garden" and "The Washington Monument" into "Madison Square Garden" and "Washington Monument" Turn plural nouns into singular the easy way ... strip "es", then "s" from each word in your name. Downcase everything. Eliminate any remaining short words "a" "it" "the" "and" "&" you get the idea. Sort your words into alphabetical order, getting you "garden madison square" Store that resulting string into a new column in your table. Match on it, while still displaying your original string.

(2) Create a lookup table with variant spellings of venues. This works well for venue names like "Boston Garden" / "Fleet Center" / "TD Banknorth Garden" / "North Station" and junk like that. Same place, different spelling. ("Penn Station" for your example).

(3) You could use the Yahoo or Google Maps geocoding services, which will take incomplete names and addresses and standardize them.

Soundex is going to get you quite a few false positive matches. It's designed as a fallback and requires human disambiguation.