Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

My project uses one of ESRI's ArcGIS online geocoding services to provide address searching capability.

Specifically I use this locator (only through the premium subscription model): http://tasks.arcgisonline.com/ArcGIS/rest/services/Locators/TA_Address_NA_10/GeocodeServer

Now, what I want to do is take the address candidates from the result set (when there are more than one, which is often) and choose the closest, best matching candidate for the user and present that to them rather than have them choose from a list of candidates. Take this simple example:

Address:

50 22nd St, National City, CA

Returns the results, with the address, score and locator name for each:

--------------------------------------------------------------------
50 E 22nd St, National City, CA, 91950     – 90.97    – US_Streets
50 W 22nd St, National City, CA, 91950     - 90.97    – US_Streets
National City, CA                          – 100.0    – US_CityState
City Terrace, CA                           – 94.35    - US_CityState

For this example the best thing to do is present the user with a choice between 50 E/W 22nd St. Right? I say that because taking National City, CA as the right choice would be inaccurate, even thought it has score of 100.

Another example:

1700 Alondra Blvd, Compton, CA

Returns these results:

---------------------------------------------------------------------
1700 W Alondra Blvd, Compton, CA 90220     – 90.97    – US_RoofTop
1700 E Alondra Blvd, Compton, CA 90221     – 90.97    - US_Streets
1700 W Alondra Blvd, Compton, CA 90220     – 90.97    – US_Streets
Alondra Blvd, Compton, CA, 90746           - 100      - US_StreetName
Alondra Blvd, Compton, CA 90220            - 100      - US_StreetName
Alondra Blvd, Compton, CA, 90221           - 100      - US_StreetName
E Alondra Blvd, Compton, CA, 90746         – 88.71    - US_StreetName
W Alondra Blvd, Compton, CA, 90220         – 88.71    - US_StreetName
W Alondra Blvd, Compton, CA, 90220         – 88.71    - US_StreetName
W Alondra Blvd, Compton, CA, 90746         - 88.71    - US_StreetName
E Alondra Blvd, Compton, CA, 90221         – 88.71    - US_StreetName
E Alondra Blvd, Compton, CA, 90220         – 88.71    - US_StreetName
Compton, CA                                – 100.0    - US_CityState
East Compton, CA                           – 95.48    - US_CityState
West Compton, CA                           – 95.48    - US_CityState

Do you return a choice between E/W as the previous example or do you try and make an educated guess and return Alondra Blvd, Compton, CA because US_StreetName is pretty reliable and shouldn't be ignored? My algorithm below will return Alondra Blvd, Compton, CA but perhaps it'd be more consistent to return E/W as a choice. You could also argue that you should just choose for the user and return 1700 W Alondra Blvd as Google does.


Here is the algorithm that I use to determine the best address, most of the time.

The Algorithm

  1. Ahead of time make a list of your preferred locators and determine a minimum match score for each. You are to prefer the results from these locators over any others. Also, make an all-time minimum match score to filter all results by, as your fall back option. This is so that you avoid, really poorly geocoded results.
  2. Iterate over your preferred locators one a time. Look at just those candidates whose locator is the locator your interested in during each iteration.
  3. For each candidate compare the score with the current preferred locator's score to see if it meets or exceeds the locator's minimum match score.
  4. If the candidate's score meets or exceeds the minimum match score for that candidate take that one candidate as your best match and return it to the user.
  5. If the candidate's score does not meet or exceed the minimum match score, keep looking through the candidates.
  6. If you haven't found a candidate whose score meets or exceeds the minimum match score for the current locator, keep looking through the locators for a match.

    // Usually a candidate is found in these first steps, but if not ....

  7. Take your all-time minimum match score and iterate over your candidates removing any candidates whose score is below this all-time minimum match score.

  8. Order this list of candidates by their score and return them all to the user to choose from.

What is the best way to do this? How can I improve my algorithm?

Thanks!

share|improve this question
    
Geocoding will only be as accurate as the data it is referencing to. USA data has many good sources so matches are of high accuracy 'rooftop' is the highest. –  Mapperz May 30 '13 at 1:46
    
Are you interested in validating the address first, or just standardizing it to return to your users? I ask because "1700 W Alondra Blvd, Compton, CA 90220" is a valid address while "1701 W Alondra Blvd, Compton, CA 90220" is not a valid address. However, both can be standardized (and mapped if needed). If address validation is needed, a quick google search for that term "address validation" or even "address verification" will find plenty of good companies for you. –  Jeffrey May 30 '13 at 17:54
    
I'm interested in taking the results and attempting to find the correct (or most correct in some cases) and returning it to the user. If that's what you mean by standardizing, then yes that's what I want to do. Its not user-friendly to return a list of address choices to a user if one can be determined from it. My algorithm is attempting to do that. –  Aaron May 30 '13 at 18:54
add comment

2 Answers 2

Consider the input address here:

1700 Alondra Blvd, Compton, CA

Let's take a look at the address components that were entered. (In this simple case, an address component is surrounded by spaces or a comma. Cities will certainly have multiple words in them and streets will also have multiple words in them.):

primary_number: 1700
street_predirection: none
street_name: Alondra
street_suffix: Blvd
street_postdirection: none
secondary_number: none
secondary_designator: none
city_name: Compton
state_abbreviation: CA
zipcode: none
plus4_code: none

You definitely don't want to return an address that has fewer address components than the input address.

With that in mind, I would recommend considering both the US_RoofTop response and also the US_Streets response. In this case, the US_Streets response has two comparable responses, one East and one West. There is no way for you to guess which one is preferred. The US_RoofTop respons is a duplicate of the US_Streets respons (based on the output address string) so it can be removed from what you present to the user.

No ZIP Code was input, that means the user is relying on your service to determine the ZIP Code. This is important because if the input had included a ZIP code, either 90220 or 90221, you would have been able to narrow the response down to just one address.

So, in summary, Take the response(s) that have the greatest number of address components as they are most likely be more accurate, consolidate down to just unique responses, and present those back to the user. You have then been as smart as you possibly but still allow your user to clarify when needed.

expertise: I work with addresses all day long as a street genius at SmartyStreets.

share|improve this answer
    
+1 Nice response Jeffrey, I would put the value of the locator type above the score since this will help you weed out the street ranged addresses versus Roof/Parcel point level data. –  D.E.Wright May 29 '13 at 23:41
add comment

@Jeffrey makes a very good point about the fact that you have a lot of information provided in the number of populated fields, with more being more specific. Long before I was in GIS and was a geographically inept developer, I dealt with a black-box geocoder that took in a single line input and gave out an address string, a score, and a lat/lon pair similar to the way you pose this question. Here were some heuristics I came up with to help me out:

  • If you can get the physical position of the person making the geocoding request, rank them based on the distance of the candidate lat/lon pair to the lat/lon of the requester (I believe this is practical application of the First Law of Geography). This only really applies to things like navigation and find restaurants near me type queries and not batch geocoding for data analysis.
  • You can use the score of the match as a sort of fudge factor as well, so rank based on distance divided by score. You can use the distance and/or scores as multipliers for any other ranking you choose to do as well.
  • Use a well-known algorithm (such as a Levenshtein distance) and use the similarity of the returned address string to the query address. In your Compton example,

      Result Address                              Edit Distance
    --------------------------------------------+----------------
    1700 W Alondra Blvd, Compton, CA 90220        8
    1700 E Alondra Blvd, Compton, CA 90221        8
    Alondra Blvd, Compton, CA, 90746              12
    Alondra Blvd, Compton, CA 90220               11
    Alondra Blvd, Compton, CA, 90221              12
    E Alondra Blvd, Compton, CA, 90746            11
    W Alondra Blvd, Compton, CA, 90220            11
    W Alondra Blvd, Compton, CA, 90746            11
    E Alondra Blvd, Compton, CA, 90221            11
    E Alondra Blvd, Compton, CA, 90220            11
    Compton, CA                                   19
    East Compton, CA                              17
    West Compton, CA                              18
    

    You can see the best candidates also have the lowest edit scores.

  • Find the distance between each pair of candidate points, closer result candidates are better than further ones (the results may all cluster around the correct answer) and you can use that in addition to any other multipliers you come up with. This also helps eliminate duplicates and far outliers.

Obviously I'm looking at this from a pretty rough point of view, but by applying a bunch of heuristics like this to geocoders I couldn't look inside in the past I got a pretty impressive improvement in result quality.

share|improve this answer
    
I don't have access to the x,y of the person making the request. Though I like that approach. Also, I think the geocoder uses a Levenshtein-like algorithm already. –  Aaron May 30 '13 at 13:30
    
I was suggesting you did it one more time on the results yourself to figure out which of the results agggregated from multiple geocoders are best. –  Jason Scheirer May 30 '13 at 18:19
    
Jason, but doesn't the score already tell me this and thus be redundant, if the Levenshtein algorithm (or something like it) is run by the geoprocessing task? Also, are you employed by Jack Dangermond? :-) –  Aaron May 30 '13 at 18:56
    
Obviously the scores aren't doing it for you, so I'm suggesting you take the score with a grain of salt or disregard it completely. You get plenty of other information from a geocode query that you can use the evaluate the quality of a match. –  Jason Scheirer May 30 '13 at 19:33
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.