Geocoding Multi-Feature Addresses

• US 20090177643A1
• Filed: 01/04/2008
• Published: 07/09/2009
• Est. Priority Date: 01/04/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Khot, Tushar, Gupta, Apurv
• Granted Patent: US 8,150,848 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30
• CPC Class Codes: Y10S 707/918 Location
• CPC Class Codes: Y10S 707/919 Geographic
• CPC Class Codes: Y10S 707/921 Spatial

Abstract

A system and method of parsing natural language descriptions of features to determine an approximate location. An embodiment includes splitting the natural language descriptions into components, geocoding each component, and returning the geocode with the highest confidence level. The geocode references a specific location, and this information may be determined by content from a variety of sources. The system may use an assortment of techniques for determining highest confidence level.

Claims

1. A method of geocoding a multi-feature address, comprising:

(a) receiving an address term;

(b) splitting the address term into at least one region, at least one feature, and at least one delimiter, wherein a start or an end of each feature is determined by one or more of the delimiters, and wherein each feature includes one or more components;

(c) for each feature, determining at least one first geocode, wherein each first geocode is based on one of the regions and one of the components of the feature;

(d) merging the first geocodes of the feature to determine a second geocode that represents the merged first geocodes of the feature having a highest confidence score of all the merged first geocodes of the feature;

(e) intersecting the second geocodes of all respective features of the address term to determine a third geocode; and

(f) outputting a signal representing the third geocode.

2. The method of claim 1, wherein (c) comprises:

generating geographical coordinate information that includes latitude and longitude values.

3. The method of claim 2, wherein generating geographical coordinate information comprises:

selecting the geographical coordinate information from a geocode database.

4. The method of claim 2, wherein generating geographical coordinate information comprises:

selecting the geographical coordinate information from a publicly available user created geocode database.

5. The method of claim 1, wherein (d) comprises:

evaluating a subset of the first geocodes of the feature, wherein the subset includes one or more geocodes based on a same region and a same component.

6. The method of claim 5, wherein evaluating the subset of the first geocodes comprises:

determining a confidence score for the subset of the first geocodes, wherein the confidence score is inversely related to the number of geocodes in the subset of first geocodes.

7. The method of claim 5, wherein evaluating the subset of the first geocodes comprises:

determining a centroid of all geocodes in the subset of the first geocodes if all geocodes in the subset of the first geocodes are valid;

determining a failure if all geocodes in the subset of the first geocodes are invalid; and

determining one geocode of the subset of the first geocodes if only the one geocode is valid and lowering a confidence score of the one geocode if at least one other geocode of the subset is invalid.

8. The method of claim 1, wherein (e) comprises:

determining a centroid of the second geocodes.

9. The method of claim 1, wherein each delimiter includes one of a word, a punctuation character, or a blank space.

10. A system of geocoding a multi-feature address, comprising:

an address parser, configured to split an address term into at least one region and at least one feature, wherein a start or an end of each feature is determined by one or more delimiters, and wherein each feature includes one or more components;

a geocoder, configured to determine for each feature at least one first geocode, wherein each first geocode is based on one of the regions and one of the components of the feature;

a geocode confidence analyzer, configured to merge, for each feature, each first geocode of the feature to determine a second geocode that represents the merged first geocodes of the feature having a highest confidence score of all the merged first geocodes of the feature; and

a highest confidence geocode intersector, configured to determine the intersection of the second geocodes of all respective features of the address term to determine a third geocode.

11. The system of claim 10, wherein the geocoder is further configured to generate geographical coordinate information that includes latitude and longitude values.

12. The system of claim 11, wherein generating geographical coordinate information comprises:

selecting the geographical coordinate information from a geocode database.

13. The system of claim 11, wherein generating geographical coordinate information comprises:

selecting the geographical coordinate information from a publicly available user created geocode database.

14. The system of claim 10, wherein the geocode confidence analyzer is further configured to evaluate a subset of the first geocodes of the feature, wherein the subset includes one or more geocodes based on a same region and a same component.

15. The system of claim 14, wherein evaluating the subset of the first geocodes comprises:

determining a confidence score for the subset of the first geocodes, wherein the confidence score is inversely related to the number of geocodes in the subset of the first geocodes.

16. The system of claim 14, wherein evaluating the subset of the first geocodes comprises:

determining a centroid of all geocodes in the subset of the first geocodes if all geocodes in the subset of the first geocodes are valid;

determining a failure if all geocodes in the subset of the first geocodes are invalid; and

determining one geocode of the subset of the first geocodes if only the one geocode of the subset of the first geocodes is valid and lowering a confidence score of the one geocode if at least one other geocode of the subset of the first geocodes is invalid.

17. The system of claim 10, wherein determining the intersection comprises:

determining a centroid of the second geocodes.

18. The system of claim 10, wherein each delimiter includes one of a word, a punctuation character, or a blank space.

19. A method of merging geocodes, comprising:

(a) receiving an address term that includes at least one region, at least one feature, and at least one delimiter, wherein a start or an end of each feature is determined by one or more of the delimiters, and wherein each feature includes one or more components;

(b) for each feature, selecting a subset of first geocodes, wherein each first geocode is based on one of the regions and one of the components of the feature, and wherein the subset includes one or more geocodes based on a same region and a same component;

(c) evaluating the subset by

determining a centroid of all geocodes in the subset of the first geocodes if all geocodes in the subset of the first geocodes are valid,

determining a failure if all geocodes in the subset of the first geocodes are invalid, and

determining one geocode of the subset of the first geocodes if only the one geocode of the subset of the first geocodes is valid and lowering a confidence score of the one geocode if at least one other geocode of the subset of the first geocodes is invalid; and

(d) outputting a signal corresponding to a result of the evaluation.

20. The method of claim 19, wherein each first geocode comprises geographical coordinate information including latitude and longitude values.

21. The method of claim 19, wherein (c) further comprises:

determining a confidence score for the subset of the first geocodes, wherein the confidence score is inversely related to the number of geocodes in the subset of the first geocodes.

22. The method of claim 19, wherein each delimiter includes one of a word, a punctuation character, or a blank space.