Generating address term synonyms

• US 8,650,024 B1
• Filed: 04/13/2011
• Issued: 02/11/2014
• Est. Priority Date: 04/13/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Caillette, Fabrice, Snellman, Juho E.
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): Sirjani, Fariba
• Application Number:
  US13/086,017
• Time in Patent Office: 1,035 Days
• Field of Search: 704/9
• US Class Current: 704/9
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 40/157 using dictionaries or tables
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for generating address component synonyms. In one aspect, a method includes determining that a plurality of addresses cannot be geocoded by a geocoding system. Variants of the addresses that can be geocoded by the geocoding system are generated, wherein each variant of a respective address lacks a removed term. Name terms for each variant are provided by the geocoding system. Each removed term is associated with name terms received for all variants that lack the removed term, including determining, for each associated name term of each removed term, a count of the number of variants for which the geocoding system provided the name term. Whether a name term is an address term synonym for a removed term is determined based at least in part on the count of the number of variants.

Claims

1. A method performed by one or more computers, the method comprising:

determining that a plurality of addresses cannot be geocoded by a geocoding system, wherein each address includes a plurality of terms;

generating a plurality of variants of the addresses that can be geocoded by the geocoding system, wherein each variant of a respective address lacks a removed term included in the respective address;

receiving a plurality of name terms for each variant provided by the geocoding system;

associating each removed term with name terms received for all variants that lack the removed term, including determining, for each associated name term of each removed term, a count of the number of variants for which the geocoding system provided the name term;

determining, for each associated name term of each removed term, whether the name term is an address term synonym for the removed term based at least in part on the count of the number of variants.

2. The method of claim 1, wherein determining whether the name term is an address term synonym for the removed term comprises:

determining a total number of variants that lack the removed term; and

determining whether the count of the number of variants divided by the total number of variants exceeds a threshold, and if it does exceed the threshold, determining that the name term is an address term synonym for the removed term.

3. The method of claim 1, further comprising:

for each name term associated with any removed term;

for each removed term associated with the name term, incrementing a counter based on the count of the number of variants of the name term; and

determining whether to remove the name term from consideration as an address term synonym based on a value of the counter.

4. The method of claim 3, wherein:

incrementing the counter based on the count of the number of variants comprises;

dividing the count of the number of variants by a total number of variants that lack the removed term; and

determining whether the count of the number of variants divided by the total number of variants that lack the removed term exceeds a first threshold, and if so, incrementing the counter; and

determining whether to remove the name term from consideration includes;

dividing the counter by a total number of removed terms associated with the name term; and

determining whether the counter divided by the total number of removed terms exceeds a second threshold, and if so, determining to remove the name term from consideration as an address term synonym.

5. The method of claim 1, further comprising providing a list of removed terms and address term synonyms for the removed terms for human inspection.

6. The method of claim 1, further comprising, for each removed term having any address term synonyms, adding the address term synonyms to a repository of address term synonyms for the geocoding system.

7. The method of claim 1, wherein determining that a plurality of addresses cannot be geocoded by a geocoding system includes attempting to geocode each potential address in a corpus of potential addresses by sending each potential address to the geocoding system.

8. The method of claim 7, wherein each potential address is an address for a same country.

9. The method of claim 1, wherein the geocoding system is configured to geocode addresses having missing terms.

10. The method of claim 1, wherein the names for a geocoded location of a variant include one or more of:

a street name, a city name, a region name, an International Organization for Standardization (ISO) region code, a country name, a postal code, and a high precision postal code.

11. A system of one or more computers configured to perform operations comprising:

determining that a plurality of addresses cannot be geocoded by a geocoding system, wherein each address includes a plurality of terms;

generating a plurality of variants of the addresses that can be geocoded by the geocoding system, wherein each variant of a respective address lacks a removed term included in the respective address;

receiving a plurality of name terms for each variant provided by the geocoding system;

associating each removed term with name terms received for all variants that lack the removed term, including determining, for each associated name term of each removed term, a count of the number of variants for which the geocoding system provided the name term;

determining, for each associated name term of each removed term, whether the name term is an address term synonym for the removed term based at least in part on the count of the number of variants.

12. The system of claim 11, wherein determining whether the name term is an address term synonym for the removed term comprises:

determining a total number of variants that lack the removed term; and

determining whether the count of the number of variants divided by the total number of variants exceeds a threshold, and if it does exceed the threshold, determining that the name term is an address term synonym for the removed term.

13. The system of claim 11, the operations further comprising:

for each name term associated with any removed term;

for each removed term associated with the name term, incrementing a counter based on the count of the number of variants of the name term; and

determining whether to remove the name term from consideration as an address term synonym based on a value of the counter.

14. The system of claim 13, wherein:

incrementing the counter based on the count of the number of variants comprises;

dividing the count of the number of variants by a total number of variants that lack the removed term; and

determining whether the count of the number of variants divided by the total number of variants that lack the removed term exceeds a first threshold, and if so, incrementing the counter; and

determining whether to remove the name term from consideration includes;

dividing the counter by a total number of removed terms associated with the name term; and

determining whether the counter divided by the total number of removed terms exceeds a second threshold, and if so, determining to remove the name term from consideration as an address term synonym.

15. The system of claim 11, the operations further comprising providing a list of removed terms and address term synonyms for the removed terms for human inspection.

16. The system of claim 11, the operations further comprising, for each removed term having any address term synonyms, adding the address term synonyms to a repository of address term synonyms for the geocoding system.

17. The system of claim 11, wherein determining that a plurality of addresses cannot be geocoded by a geocoding system includes attempting to geocode each potential address in a corpus of potential addresses by sending each potential address to the geocoding system.

18. The system of claim 17, wherein each potential address is an address for a same country.

19. The system of claim 11, wherein the geocoding system is configured to geocode addresses having missing terms.

20. The system of claim 11, wherein the names for a geocoded location of a variant include one or more of:

a street name, a city name, a region name, an International Organization for Standardization (ISO) region code, a country name, a postal code, and a high precision postal code.

21. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

determining that a plurality of addresses cannot be geocoded by a geocoding system, wherein each address includes a plurality of terms;

generating a plurality of variants of the addresses that can be geocoded by the geocoding system, wherein each variant of a respective address lacks a removed term included in the respective address;

receiving a plurality of name terms for each variant provided by the geocoding system;

associating each removed term with name terms received for all variants that lack the removed term, including determining, for each associated name term of each removed term, a count of the number of variants for which the geocoding system provided the name term;

determining, for each associated name term of each removed term, whether the name term is an address term synonym for the removed term based at least in part on the count of the number of variants.

22. The computer storage medium of claim 21, wherein determining whether the name term is an address term synonym for the removed term comprises:

determining a total number of variants that lack the removed term; and

determining whether the count of the number of variants divided by the total number of variants exceeds a threshold, and if it does exceed the threshold, determining that the name term is an address term synonym for the removed term.

23. The computer storage medium of claim 21, the operations further comprising:

for each name term associated with any removed term;

for each removed term associated with the name term, incrementing a counter based on the count of the number of variants of the name term; and

determining whether to remove the name term from consideration as an address term synonym based on a value of the counter.

24. The computer storage medium of claim 23, wherein:

incrementing the counter based on the count of the number of variants comprises;

dividing the count of the number of variants by a total number of variants that lack the removed term; and

determining whether the count of the number of variants divided by the total number of variants that lack the removed term exceeds a first threshold, and if so, incrementing the counter; and

determining whether to remove the name term from consideration includes;

dividing the counter by a total number of removed terms associated with the name term; and

determining whether the counter divided by the total number of removed terms exceeds a second threshold, and if so, determining to remove the name term from consideration as an address term synonym.

25. The computer storage medium of claim 21, the operations further comprising providing a list of removed terms and address term synonyms for the removed terms for human inspection.

26. The computer storage medium of claim 21, the operations further comprising, for each removed term having any address term synonyms, adding the address term synonyms to a repository of address term synonyms for the geocoding system.

27. The computer storage medium of claim 21, wherein determining that a plurality of addresses cannot be geocoded by a geocoding system includes attempting to geocode each potential address in a corpus of potential addresses by sending each potential address to the geocoding system.

28. The computer storage medium of claim 27, wherein each potential address is an address for a same country.

29. The computer storage medium of claim 21, wherein the geocoding system is configured to geocode addresses having missing terms.

30. The computer storage medium of claim 21, wherein the names for a geocoded location of a variant include one or more of:

a street name, a city name, a region name, an International Organization for Standardization (ISO) region code, a country name, a postal code, and a high precision postal code.