Algorithm: Identify same Outlets / Supermarkets

Question

We have a database with stores Outlets / Supermarkets (mainly in germany but other countries are also possible). We store some informations of this outlets / supermarkets like name, street, postalcode, city, geocodes (longitude , latitude).

It is very important that one outlet is only once in the database.

From our clients we get lists of outlets / supermarkets to import them in our database. When the outlet / supermarket alreasy exists in our database we ignore the outlet / supermarket in the import list but when it does not exist in our database we create a new entry in our database.

And here comes the problem: The quality of the import lists from our clients is very often extrem badly. Like street and postalcode doesn't match, spelling mistakes in street name, spelling mistakes in outlet name etc...The import lists are not standardized.

We need a far-reaching automatic process. In some cases, an import list has more than 10,000 entries and is far too costly if an employee carries out this process.

Our previous approaches:

1. Strictly check for equality (Name == ImportName && Street == ImportStreet). It is obvious that this can not work. the automatic process would find only a few matches.

2. Geocoding and Levenshtein algorithm (https://en.wikipedia.org/wiki/Levenshtein_distance)

First we geocode the address from the import list. Then we look in a radius of 500 meters if there are another outlets already in the database. If no, then we create a new entry in the database. But if there is already an existing outlet nearby we check if it is the same with the help of the Levenshtein algorithm.

There are several problems with this solution: Geocoding often fails because of the many misspellings and spellings of the address (we tried to change our gecoding provider to google maps because geocoding is much better but this would very expensive), Levenshtein algorithm can be wrong so we have wrong mappings to existing outlets. Depending on which limit your choose for the Levenshtein distance, many outlets have to be manually imported or wrong assignments are created.

We are looking for new approaches and ideas for this problem. Are there suitable algorithms or do you have other ideas? Many Thanks.

Answer 1

There is no way to guarantee a match, even if you hire humans to check each one manually. Therefore, The best approach with this is to push the validation back to your client.

When they enter a new outlet, you can get them to improve the data by presenting them with a map and lists of possible matches. If they don't know whether the store is the same or not, no-one does.

Also, I would record all the inputted outlets and group matches together in your database rather than not accept duplicates. This allows you to correct mistakes either way, incorrect match or duplicate, when they are discovered.