Systems and methods for matching similar geographic objects

• US 8,949,196 B2
• Filed: 12/07/2012
• Issued: 02/03/2015
• Est. Priority Date: 12/07/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Duleba, Krzysztof
• Primary Examiner(s): To, Baoquoc N
• Application Number:
  US13/708,483
• Publication Number:
  US 20140164415A1
• Time in Patent Office: 788 Days
• Field of Search: 707/722, 707/726
• US Class Current: 707/673
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A computer-implemented method including obtaining a subject dataset including two or more features associated with a subject geographic object, obtaining a candidate dataset including two or more features associated with a candidate geographic object, comparing, using a computer, at least two features of the subject dataset to at least two corresponding features of the candidate dataset, at least one of the features compared comprising a geographic feature, and determining whether the candidate geographic object matches the subject geographic object based on the comparison.

Claims

1. A computer-implemented method for mapping geographic objects of a second database to geographic objects of a first database, the method comprising:

identifying a subject geographic object of the first database comprising an identifier for which a corresponding candidate geographic object of the second database comprising the same identifier has not been identified, the subject geographic object corresponding to a subject dataset comprising at least two of the following;

a descriptor of the subject geographic object;

a geographic center of the subject geographic object; and

a geographic shape of the subject geographic object;

identifying, via comparison of the subject dataset corresponding to the subject geographic object to a plurality of candidate datasets each corresponding to a candidate geographic object of the second database, a candidate dataset comprising at least two of the following;

a descriptor of a candidate geographic object that matches the descriptor of the subject geographic object;

a geographic center of a candidate geographic object that matches the geographic center of the subject geographic object; and

a geographic shape of a candidate geographic object that matches the geographic shape of the subject geographic object; and

mapping the subject geographic object to a candidate geographic object corresponding to the identified candidate dataset, wherein both the subject dataset and the candidate dataset are stored as structured data in the first database and the second database, respectively, prior to identifying the candidate dataset.

2. The method of claim 1, wherein:

the geographic center of the subject geographic object is defined by the center of the land area occupied by the subject geographic object; and

the geographic shape of the subject geographic object is defined by the boundaries of the land area occupied by the subject geographic object.

3. A computer-implemented method, comprising:

obtaining a subject dataset comprising two or more features associated with a subject geographic object;

obtaining a candidate dataset comprising two or more features associated with a candidate geographic object;

comparing, using a computer, at least two features of the subject dataset to at least two corresponding features of the candidate dataset, at least one of the features compared comprising a geographic feature; and

determining whether the candidate geographic object matches the subject geographic object based on the comparison, wherein both the subject dataset and the candidate dataset are stored in memory as structured data prior to comparing the at least two features of the subject dataset to the at least two corresponding features of the candidate dataset.

4. The method of claim 3,

wherein the subject dataset comprises at least two of the following:

a descriptor of the subject geographic object, a geographic center of the subject geographic object, and a geographic shape of the geographic object, and

wherein the candidate dataset comprises at least two of the following;

a descriptor of the candidate geographic object, a geographic center of the candidate geographic object, and a geographic shape of the candidate geographic object.

5. The method of claim 4, wherein comparing at least two features of the subject dataset to at least two corresponding features of the candidate dataset comprises at least two of:

comparing the descriptor of the subject geographic object to the descriptor of the candidate geographic object;

comparing the geographic center of the subject geographic object to the geographic center of the candidate geographic object; and

comparing the geographic shape of the subject geographic object to the geographic shape of the candidate geographic object.

6. The method of claim 5, wherein comparing the descriptor of the subject geographic object to the descriptor of the candidate geographic object comprises determining a string edit distance between the descriptor of the subject geographic object and the descriptor of the candidate geographic object, and comparing the string edit distance to a string edit threshold value.

7. The method of claim 5, wherein comparing the descriptor of the subject geographic object to the descriptor of the candidate geographic object comprises determining a string edit equality between the descriptor of the subject geographic object and the descriptor of the candidate geographic object, and comparing the string edit equality to a string edit threshold value.

8. The method of claim 5, wherein comparing the geographic center of the subject geographic object to the geographic center of the candidate geographic object comprises determining a distance between the geographic center of the subject geographic object and the geographic center of the candidate geographic object, and comparing the distance to a center distance threshold value.

9. The method of claim 5, wherein comparing the geographic center of the subject geographic object to the geographic center of the candidate geographic object comprises:

determining a first tile of a map comprising the geographic center of the subject geographic object;

determining a second tile of the map comprising the geographic center of the candidate geographic object; and

determining whether the first and second tiles of the map are located within a threshold number of tiles of one another.

10. The method of claim 5, wherein comparing the geographic shape of the subject geographic object to the geographic shape of the candidate geographic object comprises determining an extent of overlap between the geographic shape of the subject geographic object and the geographic shape of the candidate geographic object, and comparing the extent of overlap to a threshold overlap value.

11. The method of claim 5, wherein areas of the geographic shape of the subject geographic object and the geographic shape of the candidate geographic object are defined by covering of the respective geographic shapes.

12. The method of claim 5, wherein determining whether the candidate geographic object corresponds to the subject geographic object based on the comparison comprises determining that the candidate geographic object corresponds to the subject geographic object if at least one of the following conditions are satisfied:

based on comparing the descriptor of the subject geographic object to the descriptor of the candidate geographic object it is determined that the descriptors are the same, and based on comparing the geographic center of the subject geographic object to the geographic center of the candidate geographic object it is determined that the geographic centers are the same;

based on comparing the descriptor of the subject geographic object to the descriptor of the candidate geographic object it is determined that a string edit between the descriptors satisfies a string edit threshold value, and based on comparing the geographic shape of the subject geographic object to the geographic shape of the candidate geographic object it is determined that an overlap of the geographic shapes satisfy a first threshold overlap value;

based on comparing the descriptor of the subject geographic object to the descriptor of the candidate geographic object it is determined that a string edit between the descriptors satisfies a string edit threshold value, and based on comparing the geographic center of the subject geographic object to the geographic center of the candidate geographic object it is determined that the distance between the geographic centers satisfies a center distance threshold value; and

based on comparing the geographic shape of the subject geographic object to the geographic shape of the candidate geographic object it is determined that an overlap of the geographic shapes satisfy a second threshold overlap value that requires a greater overlap between the geographic shapes than is required by the first threshold overlap value.

13. The method of claim 5, wherein:

the geographic center of the subject geographic object is defined by the center of the surface area of the planet occupied by the subject geographic object; and

the geographic shape of the subject geographic object is defined by the boundaries of the center of the surface area of the planet occupied by the subject geographic object.

14. The method of claim 3, wherein the subject geographic object comprises a subject identifier for which a corresponding geographic object comprising an identifier corresponding to the subject identifier has not been identified.

15. The method of claim 14, wherein a corresponding identifier comprises an identifier that is the same or similar to the subject identifier.

16. The method of claim 3, wherein the candidate geographic object comprises an identifier that does not correspond to an identifier of the subject geographic object.

17. The method of claim 16, wherein the identifier corresponding to the subject geographic object is generated based on the application of a hash function to at least a portion of the subject dataset, and wherein the identifier corresponding to the candidate geographic object is generated based on the application of the hash function to at least a portion of the candidate dataset.

18. The method of claim 3, wherein identifying a candidate geographic object comprises identifying the candidate geographic object from a subset of geographic objects identified as being related to the subject geographic object.

19. The method of claim 18, wherein the subset of geographic objects identified as being related to the subject geographic object comprise a candidate dataset having at least some features in common with the subject dataset.

20. The method of claim 3, wherein the subject data set comprises features corresponding to the subject geographic object at a first time, and wherein the candidate dataset comprises features corresponding to the candidate geographic object at a second time subsequent to the first time.

21. A tangible non-transitory computer readable storage medium having computer-executable program instructions stored thereon, that are executable by one or more computers to cause steps comprising:

obtaining a subject dataset comprising two or more features associated with a subject geographic object;

obtaining a candidate dataset comprising two or more features associated with a candidate geographic object;

comparing, using a computer, at least two features of the subject dataset to at least two corresponding features of the candidate dataset, at least one of the features compared comprising a geographic feature; and

determining whether the candidate geographic object matches the subject geographic object based on the comparison, wherein both the subject dataset and the candidate dataset are stored in memory as structured data prior to comparing the at least two features of the subject dataset to the at least two corresponding features of the candidate dataset.

22. A system, comprising:

one or more processors;

a memory; and

an object matching module stored on the memory, the object matching module configured to be executed by the one or more processors to cause operations comprising;

obtaining a subject dataset comprising two or more features associated with a subject geographic object;

obtaining a candidate dataset comprising two or more features associated with a candidate geographic object;

comparing, using the one or more processors, at least two features of the subject dataset to at least two corresponding features of the candidate dataset, at least one of the features compared comprising a geographic feature; and

determining whether the candidate geographic object matches the subject geographic object based on the comparison, wherein both the subject dataset and the candidate dataset are stored in the memory as structured data prior to comparing the at least two features of the subject dataset to the at least two corresponding features of the candidate dataset.

23. A computer implemented method for matching first and second geographic entity stored in one or more geographic information systems, comprising:

retrieving information about a first geographic entity and a second geographic entity from at least one of the one or more geographic information systems, the retrieved information including two or more of a name, a geographic center and a geographic area of the entity; and

comparing the retrieved information to determine whether the first and second geographical entities match one another, wherein the first and second geographic entities are determined to match one another if it is determined that at least one of the following conditions exists;

A) the name of the first entity matches the name of the second entity within a predetermined string edit distance and the area of the first entity overlaps the area of the second entity by at least a first amount;

B) the name of the first entity matches the name of the second entity to within a predetermined string edit distance, and the geographic centers of the first and second entities are less than a predetermined distance apart; and

C) the area of the first geographic entity overlaps the area of the second geographic entity by at least a second amount that is greater than the first amount,

wherein both the subject dataset and the candidate dataset are stored in the one or more geographic information systems as structured data prior to comparing the retrieved information to determine whether the first and second geographical entities match one another.