Matching Non-exact Addresses

Abstract

A two-step algorithm for conducting near real time fuzzy searches of a target on one or more large data sets is described, where the address and the geolocation are included in the match criteria. This algorithm includes the simplification of the data by removing grammatical constructs to bring the target search term (and the stored database) to their base elements and then perform a Levenshtein comparison to create a subset of the data set that may be a match. Location is determined by a geohash comparison of the latitude and longitude and a Levenshtein comparison of the address text. Then performing a scoring algorithm while comparing the target to the subset of the data set to identify any matches.

1 . A method for comparing a target address with a base address, the method comprising:
 receiving the base address in text format;   looking up a base longitude and a base latitude for the base address;   receiving the target address in text format;   looking up a target longitude and a target latitude for the target address;   subtracting the target longitude from the base longitude, resulting in a longitude difference;   subtracting the target latitude from the base latitude, resulting in a latitude difference;   comparing an absolute value of the longitude difference to a longitude threshold value and comparing an absolute value of the latitude difference to a latitude threshold value;   if the longitude difference is less than or equal to the longitude threshold value and the latitude difference is less than or equal to the latitude threshold value, returning an indication of a match; and   if the longitude difference is greater than the longitude threshold value or the latitude difference is greater than the latitude threshold value, calculating a score Levenshtein distance between the target address and the base address in the target, and returning the indication of the match if the score Levenshtein distance is greater than a Levenshtein threshold value.   
     
     
         2 . The method of  claim 1  wherein the longitude threshold value is the same as the latitude threshold value. 
     
     
         3 . The method of  claim 1  further comprising storing the base longitude and the base latitude for the base address. 
     
     
         4 . The method of  claim 3  wherein the looking up of the base address and the storing of the base longitude and the base latitude are done as part of a a batch. 
     
     
         5 . The method of  claim 1  wherein the base address in text format is automatically corrected before looking up the base longitude and the base latitude. 
     
     
         6 . The method of  claim 1  wherein the target address in text format is automatically corrected before looking up the target longitude and the target latitude. 
     
     
         7 . A non-transitory computer readable media programmed to:
 receive a target address in text format;   look up a target location information for the target address;   calculate a target geohash from the target location information;   add a first threshold value to the target geohash to calculate a geohash high range;   subtract the first threshold value to the target geohash to calculate a geohash low range;   extract all extracted records in a watch list, where the extracted records contain a watch list geohash value between the geohash low range and the geohash high range; and   identify the extracted records as a match to the address target.   
     
     
         8 . The non-transitory computer readable media of  claim 7  further programmed to loop through the watch list records, if the there are no extracted records, and calculate a score Levenshtein distance between the target address and a watch list address in the watch list, and return each watch list record where the score Levenshtein distance is greater than a second threshold value. 
     
     
         9 . The non-transitory computer readable media of  claim 7  wherein the target information is a longitude value and a latitude value. 
     
     
         10 . The non-transitory computer readable media of  claim 9  further programmed to calculate the geohash by combining bits of the longitude value with the bits of the latitude value, where even bits in the geohash are taken for the longitude value and odd bits in the geohash are taken for the latitude value. 
     
     
         11 . The non-transitory computer readable media of  claim 7  wherein the extraction of the extracted records in the watch list involves a linear search. 
     
     
         12 . The non-transitory computer readable media of  claim 7  wherein the watch list is sorted by the watch list geohash value. 
     
     
         13 . The non-transitory computer readable media of  claim 12  wherein the extraction of the extracted records in the watch list involves using the geohash value as a key to locate the watch list records. 
     
     
         14 . An apparatus for determining if a target address is found in a watch list of addresses, the apparatus comprising:
 a computing device with a user interface for accepting the target address in text format, the computing device configured to convert the target address into target location information;   a storage device containing the watch list of addresses; and   a server, connected to the storage device, wherein the server operates software instructions to loop through the addresses in the watch list, and for each watch list address calculates a difference between the target address and each watch list address, compares the difference to a first threshold, indicates a match if the difference is less than or equal to the first threshold, and if the difference is greater than the first threshold, calculates a score Levenshtein distance between the target address and each watch list address, and indicates the match if the score Levenshtein distance is greater than a second threshold value.   
     
     
         15 . The apparatus of  claim 14  wherein the score Levenshtein distance is calculated before the difference is calculated. 
     
     
         16 . The apparatus of  claim 14  wherein the difference is calculated by subtracting a target geohash for the target address from a base geohash for each watch list address and normalizing the difference. 
     
     
         17 . The apparatus of  claim 16  wherein the normalizing of the difference involves finding a most significant bit of the difference. 
     
     
         18 . The apparatus of  claim 14  further comprising an internet, connected between the computing device and the server. 
     
     
         19 . The apparatus of  claim 14  wherein the computing device and the server are the same device. 
     
     
         20 . The apparatus of  claim 14  further comprising an internet, connected between the computing device and the storage device.