ThinkGeo.com    |     Documentation    |     Premium Support

Speeding up geocoding performance

#1

 Hi,


I am trying to optimize the performance of our geocoding approach.  We are trying to geocode about 1.5 million records and obviously every call to geocoder counts.  What I have noticed is that when I call geocoder with a second parameter specific (ie, geoCoder.Match(location, zip), the performance is great (and very close to the metrics specified in your benchmark document).  However, at some cases, it fails to return valid geocoded results (not sure if its an issue with a zip code or not), so in that case I fall back to calling geocoder.Match(location) without specifying the location.  The good news is that in most cases it returns me some results, the bad news is that second call is way, way slower and pretty much kills the overall performance.  


What are the particular reasons for the second call being so much slower (sometimes it takes seconds instead of milliseconds)?  Is there anyway to speed it up?  On a large number of records (1.5 million) the difference is very significant.


For reference, here is an example of an address that fails to geocode with the first call but is ok with the second:


Address: "1314 University Ave, Sewanee TN" Zip: "37375"


Looking at Google Maps, the address below seems to be valid and matching ZIP code as specified.  However, if I include ZIP code as part of the call to ThinkGeo I get 0 results.  Any help or ideas would be appreciated


For reference, I am using the latest development build 4.5.40.0 as well as the last released version 4.5.0.0 with the same results.


 


Thank you



#2

Val, 
  
 Thanks for your post, 
  
 About your issue, I cheked the address what you mentioned, when I just entered the street address without zipcode, there are valid results returned, but when I entered the street address with zip code using the second Match function to search, there are not any street results returned, the problem is from the house number, here is the search result below for "1314 University Ave, Sewanee TN": 
  
 Street : UNIVERSITY Avenue ; PrefixDirectional : None ; SuffixDirectional : None ; StreetType : Avenue ; TigerLineID : 608794984 ; FromAddressLeft : 1320 ; ToAddressLeft : 1304 ; FromAddressRight : 1321 ; ToAddressRight : 1305 ; Zip : 37383 ; FromLongitude : -85.913047 ; FromLatitude : 35.208567 ; ToLongitude : -85.913326 ; ToLatitude : 35.208601 ; State : TN ; County : FRANKLIN ; City : SEWANEE ; CensusTractL : 960700 ; CensusTractR : 960700 ; CensusBlockL : 3028 ; CensusBlockR : 3027 ; CensusBlockGroupL : 3 ; CensusBlockGroupR : 3 ; IsHighway : False ; IsPOBox : False ; HouseNumber : 1314 ; SideOfStreet : Left ; BoundingBox : POLYGON((-85.9181548764496 35.2135513761151, -85.9081548764496 35.2135513761151, -85.9081548764496 35.2035513761151, -85.9181548764496 35.2035513761151, -85.9181548764496 35.2135513761151)) ; CentroidPoint : POINT(-85.9131548764496 35.2085513761151) ;  
  
 You can realize the zip code in the result list is 37383, not 37375, it means the matched street is inside the area of 37383 zipcode. So if you searched the same street address with zip code 37375, although there are 15 results can be found out, but when it matches the house number, there are no results can be matched, so it returned Null. This is determined by the dbf index files, the dbf index files was built based on the TigerData 2009, the map data for google maps is more complete than the TigerData 2009, so maybe some streets it can be matched by google maps, cannot be matched by our MapSuiteGeocoder. 
  
 Also about the performance issue, when you used this method: Match(location) the speed is very slow, but when you used this method:Match(location, zip) the performance is higher but some cases cannot return valid results. Obviously, when you search an address without zipcode, it will searched the whole streets.dbf file, the dataset is large, so it would cost more times, but if you used the second method to search, the search range is small, it would limit the range to the area of the entered zipcode then search the entered street address in the zipcode area, so the speed is faster than using the first method. 
  
 If you misunderstand anything please let us know, 
  
 Thanks, 
  
 Scott,

#3

 This makes sense.  However, is there anyway I can speed up the performance in the case where zip code is not matching your criteria and I need to fall back to just using the address?  I tried sending in city and state as parameters to the call and per your logic above for sending in zip code, I would have expected that to be at least relatively faster than just sending in the address, but it still takes a very long time to geocode in that case.  Is there a way to address the performance in that case?  Shouldn't passing the city and state narrow down the result set that ThinkGeo needs to search through?  Is there any other way to boost the performance (indexing, limiting the number of plugins or something on that level?) The performance of geocoder in the fallback case is on the order of seconds per call which is unacceptably slow when it comes to a large set batch geocoding.


Thanks



#4

 Going back to the original question about geocoding that particular address - I believe there is a technical issue with the geocoder not finding the address for that ZIP code.


I have downloaded 2009 Tiger files for that particular data set from Census:  www2.census.gov/cgi-bin/shap...unty=47051 (Franklin County, TN).  Checking their data set, there are 2 entries for that address - one for the left side of the street and one for the right side.  The left side belongs to zipcode 37375 (the one in the address that I supplied) and the right side is zip code 37383.  So when I geocoded, it should have chosen the left side record with the zipcode 37375 and therefore, even according to 2009 Tiger data, "1314 University Ave, Sewanee TN" Zip: "37375" should be a valid address. There are 2 entries with TLID 608794984 since TLID is not a unique key in that dataset - ARID is.


Going further, looking at streets.dbf file that was supplied as part of ThinkGeo geocoder data, there is only one entry for TLID 608794984 and it seems that in your data, the left side and the right street data ranges are combined into one record and includes zip code as part of that record - this is definitely an issue with this particular case since the ZIP codes for the left and the right sides are different.


Here are the records from Tiger 2009 files






    TLID
    
        
            TLID
            FROMHN
            TOHN
            SIDE
            ZIP
            PLUS4
            FROMTYP
            TOTYP
            FROMARMID
            TOARMID
            ARID
            MTFCC
            FULLNAME
            NAME
            PREDIRABRV
            PRETYPABRV
            PREQUALABR
            SUFDIRABRV
            SUFTYPABRV
            SUFQUALABR
            PREDIR
            PRETYP
        
    
    
        
            608794984
            1320
            1304
            L
            37375
            

            
            

            
            I
            0
            0
            40051154942
            D1000
            University Ave
            University
            

            
            

            
            

            
            

            
            Ave
            

            
            

            
            

            
        
        
            608794984
            1321
            1305
            R
            37383
            

            
            

            
            I
            0
            0
            40051156566
            D1000
            University Ave
            University
            

            
            

            
            

            
            

            
            Ave
            

            
            

            
            

            
        
    
    


And here is the screenshot from your data






    UnivSamp
    
        
            ID_Street
            DT_Prefix
            DT_Suffix
            DT_STType
            DT_TLID
            DT_FromL
            DT_ToL
            DT_FromR
            DT_ToR
            DT_Zip
            DT_FromX
            DT_FromY
            DT_ToX
            DT_ToY
            DT_State
            DT_County
            DT_City
            DT_PSt
            DT_PC
        
    
    
        
            603332
            0
            0
            4
            608794984
            1320
            1304
            1321
            1305
            37383
            -85913047
            35208567
            -85913326
            35208601
            TN
            FRANKLIN
            SEWANEE
            103201673
            3
        
    
    


You can see sample data and results from the query in the attached access db by executing query called TLID.


 



#5

Val,


Sorry for the inconvenient, so there are two issues in your side, please see my comments below for these two issues:


1, Performance issue:


Actually, the performance of advanced geocode is not so bad according to our tests, for example, I tested this street address: Network Blvd. Suite 215, Frisco, TX 75034, the search time is 202 ms, we think the performance is acceptable, also in your dataset maybe some of the street addresses have so many match results so it caused the performance is lower. Whatever, there is another way can increase the performance greatly, please use the Geocoder object to instead of the UsaGeocoder object to match, here is the sample code:


 



  Geocoder geocoder = new Geocoder();
                geocoder.MatchingPlugIns.Add(new StreetMatchingPlugin(@"C:\GeocoderFullEditionIndexData_4.0.0.0", MatchMode.ExactMatch));
                geocoder.Open();
                Collection<GeocoderMatch> result = geocoder.Match(txtSearch.Text);
                geocoder.Close();
I tested the location "Network Blvd. Suite 215, Frisco, TX 75034" used the sample code above, the search time just cost 120ms, the performance increased about 60%. The reason is that in the UsaGecoder, we have several internal plugins, when an address is passed, it will pass through all internal plugins and match it. Obviously, it would decrease the performance if the entered location is just a street address. So you can use the sample code above to your application, also please note, the sample code above just can use for street address, if in your dataset, there are some other locations such as city, county, please according to the following sample code to add city and county plugins to the Geocoder object: 
 Geocoder geocoder = new Geocoder();
                geocoder.MatchingPlugIns.Add(new StreetMatchingPlugin(YourGeocoderIndexDataPath, MatchMode.ExactMatch));
                geocoder.MatchingPlugIns.Add(new CityDbfMatchingPlugin(YourGeocoderIndexDataPath, "citystate.dbf")));
                geocoder.MatchingPlugIns.Add(new CountyDbfMatchingPlugin(YourGeocoderIndexDataPath, "county.dbf")));
                geocoder.Open();
                Collection<GeocoderMatch> result = geocoder.Match(txtSearch.Text);
                geocoder.Close();
So if that, we can round some unnecessary plugins to match so that the performance can be increased greatly.


2, Match result issue: I checked the original TigerData 2009 for the record with TLID 608794987, it has actual two zip codes, they are 37375 and 37383 as you mentioned, the 37375 is the left zip code and the 37383 is the right zip code. When we built the streets.dbf file we just extracted the right zipcode if it is not NULL and use this zip code as the real zip code for the special street. So the logic of building street index file is that we extracted the left zip code and right zip code together, but we would judge the right zip code first, if it is not null, we would drop the left zip code and just extracted the right zip code as the only zip code for the street. So for this test data, we just searched the result with zipcode 37383. The reason is that we have to ensure the index files is not so large and each street record(each TLID record) just has one matched zipcode. If you really want to improve the index data please let us know and we will help you to do that,


Thanks,


Scott,



#6

 I am still having problems with your explanations.


1.  That's correct - with your example it seems to behave ok.  But if you look at the original address example that I provided that gives you a different story "1314 University Ave, Sewanee TN 37375" .   Because of the data issue in ThinkGeo as outlined before in my previous post, the geocoder fails to match anything when a ZIP code is included in the string.  If I remove the ZIP code from the address string and submit the address without the zipcode "1314 University Ave, Sewanee TN", geocoder takes 1028ms to return even with the changes you proposed to initialization of geocoder.  See sample code below of what I ran:



  var results = geoCoder.Match("1314 University Ave, Sewanee TN");


Since I don't have any alternative for information for any other zip codes for this address (as received from the source client data), my only option is to go with matching without the address (and since ThinkGeo does not understand the address with the correct zip code anyway).  Given that I am trying to geocode about 1.5 million records out of which about 500,000 fail to geocode with the zip code, the fall back for the problematic records would take about 140 hours which is not acceptable.  


2.  From your explanation, streets.dbf was built incorrectly and the logic seems to be faulty.  Basically you are missing quite a lot of data in your streets.dbf file.   The cases of having different zip codes on the left and right sides of the street is quite common in the US since that's how Postal Office defines zip code boundaries. In the example file that I supplied in my previous post that covered only one county in US there were 130 cases where the ZipCodes were different on the left and right side of the street.  In addition one TLID record can match to multiple address ranges.  Here is another example of the data problems in your data set:


Census data:








    TLID
    
        
            TLID
            FROMHN
            TOHN
            SIDE
            ZIP
            PLUS4
            FROMTYP
            TOTYP
            FROMARMID
            TOARMID
            ARID
            MTFCC
            FULLNAME
            NAME
            PREDIRABRV
            PRETYPABRV
            PREQUALABR
            SUFDIRABRV
            SUFTYPABRV
            SUFQUALABR
            PREDIR
            PRETYP
        
    
    
        
            614844025
            4073
            4071
            R
            37345
            

            
            I
            

            
            0
            0
            4002318771642
            D1000
            John Hunter Hwy
            John Hunter
            

            
            

            
            

            
            

            
            Hwy
            

            
            

            
            

            
        
        
            614844025
            4073
            4071
            R
            37345
            

            
            I
            

            
            0
            0
            4002318771642
            D1000
            State Hwy 122
            122
            

            
            State Hwy
            

            
            

            
            

            
            

            
            

            
            579
        
        
            614844025
            4074
            4072
            L
            37345
            

            
            I
            

            
            0
            0
            4002318771632
            D1000
            John Hunter Hwy
            John Hunter
            

            
            

            
            

            
            

            
            Hwy
            

            
            

            
            

            
        
        
            614844025
            4074
            4072
            L
            37345
            

            
            I
            

            
            0
            0
            4002318771632
            D1000
            State Hwy 122
            122
            

            
            State Hwy
            

            
            

            
            

            
            

            
            

            
            579
        
        
            614844025
            4142
            4100
            L
            37328
            

            
            I
            

            
            0
            0
            4002318771639
            D1000
            John Hunter Hwy
            John Hunter
            

            
            

            
            

            
            

            
            Hwy
            

            
            

            
            

            
        
        
            614844025
            4142
            4100
            L
            37328
            

            
            I
            

            
            0
            0
            4002318771639
            D1000
            State Hwy 122
            122
            

            
            State Hwy
            

            
            

            
            

            
            

            
            

            
            579
        
        
            614844025
            4143
            4101
            R
            37328
            

            
            I
            

            
            0
            0
            4002318771626
            D1000
            John Hunter Hwy
            John Hunter
            

            
            

            
            

            
            

            
            Hwy
            

            
            

            
            

            
        
        
            614844025
            4143
            4101
            R
            37328
            

            
            I
            

            
            0
            0
            4002318771626
            D1000
            State Hwy 122
            122
            

            
            State Hwy
            

            
            

            
            

            
            

            
            

            
            579
        
    
    


All those 8 records get condensed into just one in your dataset.  So in this example you are not only loosing mutliple zip codes, but you are loosing the fact that particular TLID is getting translated into multiple street names. Some other things to consider: County names could be different on each side of the street and so could be the city names.  Think of Lake Cook Road in Chicago area for example.  That road separates Lake and Cook counties.


 So for your last question, do I want you to improve your index data - the answer is definite YES, because in its current state its not exactly usable.


 




#7

Val, 
  
 We are still working on the index data re-building, when the new index data is prepared, we will change the logic in the Geocoder core code, I estimated the next release version will be published next week, 
  
 Thanks, 
  
 Scott,

#8

That's good news.  Looking forward to your updates.



#9

Val, 
  
 The new index data for US streets had been prepared, we are processing the N-Unit to test the correction for the new index data, the test data is a large dataset, so it would cost some times, I estimate we will provide you the new version of Geocoder tomorrow, 
  
 If you have any questions please let me know, 
  
 Thanks, 
  
 Scott,

#10

Val, 
  
 The new index data for US streets had been prepared, please contact the ThinkGeo support to get the updated index files and try again, when you use the updated index files in your application, if you encountered any problems please let us know, 
  
 Thanks, 
  
 Scott,

#11

 I downloaded the latest file and tried to use it.


So the good news is that the first example with TLID record #608794984 is now correctly in the table with 2 entries and geocodes correctly as well.  The bad news is that there is still only one entry in streets.dbf for TLID record #614844025 when it is supposed to be  8 records.  Does someone need to provide you a listing of all TLID that are incorrectly recorded in your streets.dbf or is it something that you can figure out as part of your quality check processes?



#12

Val, 
  
 Maybe I misunderstood something from you, you said the TLID 614844025 just has one record in the streets.dbf, I think it is correct, I checked the original data source for this TLID, it just has one zip code 37328. Also you told me that this TLID is supposed to be 8 records, I think maybe there are anything wrong, each TLID at most has 2 records based on the left zipcode and right zip code. 
  
 Can you show me it so that I can find out what’s the problem you said. 
  
 Thanks, 
  
 Scott,

#13

 Scott - please look at the reply I made on 01-05-2011.  in the original source data TLID 614844025 has 8 records.  It describes address ranges for for 2 roads - 'State Hwy 122' and 'John Hunter Hwy' (I am guessing those are 2 alisese for the same street) and there are 2 zip codes: 37345 and 37328 - per original data from TIGER.  As I mentioned before - a single TLID can have multiple records (not just 2).  It can have multiple road aliases for the same address range as well as different zip codes for the left and the right side of the street. In the example with 614844025, there are 2 address ranges with 2 street aliases and different zip codes on the left and the right side - so its 2x2x2 = 8 records in total that show up in TIGER data and should show up in the streets.dbf


 



#14

 To see an example, look at the TLID query in the database that was created from TIGER data - docs.google.com/leaf?id=0Bx2P-A0O1hJzNzNmMzMyMjAtMTkwYi00NzExLWI0NDgtYWY4YjVkMjdkY2I0&hl=en&authkey=CLDb1agL



#15

Val, 



Can you tell me the TigerData version, I checked the original source data for streets and there is only one record for TLID 614844025, also left zipcode and right zipcode are the same for this TLID. The attachment is the original source street data that includes this TLID 614844025, you can open it using Excel or DbfViewer tool and search the "614844025" value so you can locate it in the dbf file, according to the documentation of TigerData2009, the "*_edges.dbf" file list all streets records for a county of a state, you can get the actual state name and county name from the dbf file name, for example, the attached file name is tl_2009_47051_edges.dbf, the "2009" represents the tiger data version, the "47" represents the statefp and the "51" represents the countyfp. I compared the original dbf file with your access file, they have many differences on the street fields. In your original source data TLID 614844025 has 8 records, but in our original source data TLID 614844025 only has one record and one zipcode 37328, when you locate the TLID 614844025 in the attached dbf file you can see the the zipl and zipr are the same, it is 37328. 



So I realize where is the exact problem between us, our source data are not the same, can you give me the link what your original source data so that I can download it and have a comparision on it? 



Thanks for your post, 



Thanks, 



Scott,



tl_2009_47051_edges.zip (243 KB)

#16

 Scott,


as mentioned above, the source files came from 2009 TIGER web site:  www2.census.gov/cgi-bin/shap...unty=47051


There were two files that I was looking at:


1.  Address Ranges Relationship File (addr.dbf)


2. Feature Names Relationship File (featname.dbf).


I have not worked really deeply with TIGER data for about 10 years, but if I had to guess, edges.dbf does not necessarily represent the source of truth for geocoding - it represents the information needed to draw the line segments (and potentially the primary road name).  So there is a potential for mutliple street/address ranges to be associated with one edge segment.


Some notes from looking census.gov/geo/www/tiger...RSHP09.pdf


Excerpt From page: 4-15:  


 


•  Address ranges in the TIGER/Line Shapefiles may be associated with one or more of the street names 


that belong to an edge.  Caution:  Address range overlap conflicts may occur if the address ranges are 


associated with some street names or route numbers that were not intended for use in locating 


addresses.  A route number may traverse several streets with similar house numbers but different 


common names that are used for mail delivery.  .  


 


Excerpt From page: 4-17:  


Geocoding—To get the best match results, the Census Bureau advises data users to use all of the 


available address ranges to geo-reference/geocode addresses.  A single pair of left- and right-side address 


ranges may not always provide complete address range coverage.  This limitation is also true for the most 


inclusive address ranges as well.  The address ranges in the TIGER/Line Shapefiles may be separated 


because of ZIP Code differences or to establish gaps created by out-of-sequence addresses located 


elsewhere.  Some address ranges may include embedded alphanumeric characters or hyphens that make 


them distinct from the other address ranges.


 


4.2 Address Range-Feature Name Relationships  


Address range-to-feature name relationship information is available by county in the following relationship 


file: 


    Address Range-Feature Name Relationship File 


The Address Range-Feature Name Relationship File contains a record for each address range-linear feature 


name relationship.  The purpose of this relationship file is to identify all street names associated with each 


address range.  An edge can have several feature names; an address range located on an edge can be 


associated with one or any combination of the available feature names (an address range can be linked to 


multiple feature names).  The address range is identified by the address range identifier (ARID) attribute, 


which can be used to link to the Address Ranges Relationship File.  The linear feature name is identified by 


the linear feature identifier (LINEARID) attribute that relates the address range back to the Feature Names 


Relationship File (see Figure 5) 


----------


Based on Figure 5 relationships - to get full address ranges, you should have the following joins: edges to addr on TLID, addr to addrfn on ARID, and addrfn to featname on LINEARID.  Once you have all those relationships established (as per TIGER documentation) you would end up with the correct set of address ranges and names - as described previously, for TLID 614844025 there are 8 unique address records


 



#17

 One minor correction on the joins I described in the previous post.  featnames needs to have an additional join to edges.shp on TLID (per Figure 5 of TIGER documentation)



#18

 Scott, any updates?



#19

Val, 
  
 Sorry for the inconvenient about it, we found out the reason and had a discussion about it, as you know, the current streets.dbf file is more than 2.3 G, it has about 39067712 records and we queried the total records of the feature name for the whole USA, the valid record count is 44003151, if we just re-build the streets.dbf file with all feature names, I believe the streets.dbf file is about 5G, I think it is unacceptable and it will cause the performance issue for geocoding, we are looking for a solution on that now, maybe we will change the index data structure so that this problem can be resolved smoothly, 
  
 Please keep your eye on the official site if there are nay new updates we will let you know, 
  
 Thanks, 
  
 Scott,

#20

 Scott, do you have any timelines for updates?  This is a pretty crticial issue for us to be able to use this product effectively in production environment.


Also, as part of this process, are you planning to look at the original performance issues (ie, when ZIP code is not supplied as part of the data to geocode?)