Geo-ontology extraction from entities with spatial and non-spatial attributes

• US 9,529,823 B2
• Filed: 09/07/2011
• Issued: 12/27/2016
• Est. Priority Date: 09/07/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Marciniak, Tomasz A., Dupre, Xavier Sloane, Voinea, Daniel, Bernhardt, Daniel, Hegerty, Ian
• Primary Examiner(s): Uddin, Md. I
• Application Number:
  US13/226,509
• Publication Number:
  US 20130060764A1
• Time in Patent Office: 1,938 Days
• Field of Search: 707/736, 707/743, 707/921, 707/737, 707/723
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Architecture that provides fully automatic generation of a geo-ontology and does not use pre-existing geo-ontologies or other location entity repositories (e.g., a licensed location). The architecture extracts the formal administrative structure of a geographical region of interest (e.g., country) (a geo-ontology of locations with attributes and relations) from a collection of entities with spatial attributes, extracts the informal administrative structure of a geographical region of interest (e.g., country) (informal administrative regions and names and informal neighborhoods and their attributes), and extracts location static rank features for all these entities (attributes used for ranking locations from the geo-ontology that appear in user queries).

Claims

1. A memory device and a hardware processor respectively configured to store and execute instructions that implement a system, the system comprising:

an extraction component configured to automatically extract location reference data from a data store of geo-entities, the location reference data includes a list of geo-entities, a measure of relative importance of the geo-entities, and static rank attributes, the location reference data annotated with spatial location attributes and non-spatial attributes, the location reference data comprises location names related to a geographic region of interest, the spatial location attributes and non-spatial location attributes employed to associate each geo-entity with a point on a map to generate a point cloud on a multi-dimensional map, the static rank attributes used to recall a correct location in a user query to distinguish a same location name, the extraction component configured to perform automatic augmentation from external lists of locations using a probabilistic relation inference mechanism; and

a construction component configured to automatically reconstruct a geo-ontology of the geographic region of interest based on a geographical clustering of the location names within the extracted location reference data, the reconstructed geo-ontology is spatially indexed and comprises location boundaries of the geographical region of interest associated with the location names, and, further comprises aliases and alternative names generated based on clustering and segmentation of clouds of points.

2. The system of claim 1, wherein the reconstructed geo-ontology includes at least one of the geo-entities, relationships between the geo-entities, aliases, or inferred attributes used for detecting geo-entities in a user query and ranking the detected geo-entities.

3. The system of claim 1, wherein the reconstructed geo-ontology includes a formal administrative structure of the geographic region of interest.

4. The system of claim 1, wherein the reconstructed geo-ontology includes an informal administrative structure of the geographic region of interest.

5. The system of claim 1, wherein the extraction component infers a relationship between geo-entities based on an is-close/related-to relation.

6. The system of claim 1, wherein a polygonal boundary of a geo-entity is extracted.

7. The system of claim 1, wherein polygonal boundary, best center, relative importance, size, alias, most popular name, and names of parent entity are inferred from the point cloud.

8. The system of claim 1, wherein spatial inclusion defines relations between entities in the reconstructed geo-ontology.

9. A computer-implemented method, comprising computer-executable instructions that when executed by a hardware processor, cause the hardware processor to perform acts of:

extracting location reference data from a data store of geo-entities, the location reference data includes a list of geo-entities, a measure of relative importance of the geo-entities, and static rank attributes, the location reference data annotated with spatial location attributes and non-spatial location attributes, the location reference data includes location names related to a geographic location of interest, the spatial location attributes and non-spatial location attributes employed to associate each geo-entity with a point on a map to generate a point cloud on a multi-dimensional map, the static rank attributes used to recall a correct location in a user query to distinguish a same location name, the extraction component configured to perform automatic augmentation from external lists of locations using a probabilistic relation inference mechanism;

and

automatically reconstructing a geo-ontology of the geographic location of interest based on a geographical clustering of the location names within the extracted location reference data, the reconstructed geo-ontology spatially indexed and comprising location boundaries of the geographical location of interest associated with the location names, and, further comprising aliases and alternative names generated during clustering and segmentation of clouds of points.

10. The method of claim 9, further comprising creating a formal administrative structure as the reconstructed geo-ontology of the geographic location of interest.

11. The method of claim 9, further comprising creating an informal administrative structure as the reconstructed geo-ontology of the geographic location of interest.

12. The method of claim 9, further comprising extracting geo-entities of differing granularity based on point clouds formed by filtered geo-entities.

13. The method of claim 9, further comprising extracting the aliases for the geographic location of interest.

14. The method of claim 9, further comprising extracting the aliases based on cluster merging.

15. The method of claim 9, further comprising associating each geo-entity and geo-entity metadata with a point on a map to generate the point cloud.

16. The method of claim 9, further comprising extracting the aliases based on outlier detection and clustering.

17. A computer-implemented method, comprising computer-executable instructions that when executed by a hardware processor, cause the hardware processor to perform acts of:

extracting location reference data from a data store of geo-entities, the location reference data includes a list of geo-entities, a measure of relative importance of the geo-entities, and static rank attributes, the location reference data annotated with spatial attributes and non-spatial attributes, the location reference data comprises location names related to a geographic location of interest, the spatial location attributes and non-spatial location attributes employed to associate each geo-entity with a point on a map to generate a point cloud on a multi-dimensional map, the static rank attributes used to recall a correct location in a user query to distinguish a same location name, the extraction component configured to perform automatic augmentation from external lists of locations using a probabilistic relation inference mechanism;

and

automatically reconstructing a geo-ontology of the geographical region of interest comprising at least one of a formal geo-ontology or informal geo-ontology of the geographic location of interest based on a clustering of the location names of the location reference data as points on a map, the reconstructed geo-ontology is reconstructed without using pre-existing geo-ontology data, is spatially indexed, comprises location boundaries of the geographical region of interest associated with the location names, and, further comprises aliases and alternative names generated based on clustering and segmentation of clouds of points.

18. The method of claim 17, further comprising inferring a list of geo-entities from the data store based on the annotations of the spatial attributes and non-spatial attributes.

19. The method of claim 17, further comprising extracting reference data to output at least one of locations, relations, attributes, boundaries, aliases, or static ranks.

20. The method of claim 17, further comprising extracting the aliases based on outlier detection and clustering.