Semantic location and proximity of maps

• US 10,452,733 B2
• Filed: 09/08/2016
• Issued: 10/22/2019
• Est. Priority Date: 09/08/2016
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Behm, Andreas
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US15/259,093
• Publication Number:
  US 20180067952A1
• Time in Patent Office: 1,139 Days
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/444 Spatial browsing, e.g. 2D maps, 3D or virtual spaces
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

The present disclosure provides systems and methods that determine a semantic location of a map and/or determine a proximity between maps. One example computer system is configured to: obtain information descriptive of a plurality of content locations respectively associated with a plurality of items of content included in a map; identify a set of content cells based at least in part on the plurality of content locations respectively associated with the plurality of items of content included in the map; determine a plurality of sets of feature cells respectively for a plurality of semantic entities; compare the set of content cells to the respective sets of feature cells for at least a portion of the plurality of semantic entities; and select at least one of the plurality of semantic entities as a semantic location for the map based at least in part on the comparison.

Claims

1. A computer-implemented method to determine semantic locations for maps, the method comprising:

obtaining, by one or more computing devices, information descriptive of a plurality of content locations respectively associated with a plurality of items of content included in a map;

identifying, by the one or more computing devices, a set of content cells based at least in part on the plurality of content locations respectively associated with the plurality of items of content included in the map, wherein each cell in the set of content cells corresponds to a particular geographic area that includes one or more of the content locations;

determining, by the one or more computing devices, a plurality of sets of feature cells respectively for a plurality of semantic entities, wherein the set of feature cells associated with each semantic entity is descriptive of a geographic area associated with such semantic entity;

comparing, by the one or more computing devices, the set of content cells to the respective sets of feature cells for at least a portion of the plurality of semantic entities, wherein comparing, by the one or more computing devices, the set of content cells to the respective sets of feature cells for at least the portion of the plurality of semantic entities comprises determining, by the one or more computing devices, for each semantic entity in the portion of the plurality of semantic entities, a percentage of the set of content cells that are included in the respective set of feature cells for such semantic entity; and

selecting, by the one or more computing devices, at least one of the plurality of semantic entities as a semantic location for the map based at least in part on the comparison of the set of content cells to the respective set of feature cells for such at least one semantic entity, wherein selecting, by the one or more computing devices, at least one of the plurality of semantic entities as the semantic location for the map comprises selecting, by the one or more computing devices as the semantic location for the map, each semantic entity for which the percentage of the set of content cells that are included in the respective set of feature cells for such semantic entity exceeds a threshold percentage.

2. The computer-implemented method of claim 1, wherein:

the plurality of items of content comprise one or more of;

a point item of content, a line item of content, and a polygon item of content; and

identifying, by the one or more computing devices, the set of content cells based at least in part on the plurality of content locations comprises;

for each point item of content, designating, by the one or more computing devices, a cell in at least one cell layer that includes a location associated with the point item of content as included in the set of content cells;

for each line item of content, designating, by the one or more computing devices, each cell in the at least one cell layer that includes any of two or more locations respectively associated with two or more endpoints of the line item of content as included in the set of content cells; and

for each polygon item of content;

determining, by the one or more computing devices, an interior cell coverage for at least one polygonal boundary associated with the polygon item of content; and

designating, by the one or more computing devices, each cell included in the interior cell coverage as included in the set of content cells.

3. The computer-implemented method of claim 1, wherein identifying, by the one or more computing devices, the set of content cells based at least in part on the plurality of content locations comprises:

obtaining, by the one or more computing devices, data descriptive of a plurality of cells that respectively correspond to a plurality of geographic areas, wherein the plurality of cells are classified into a plurality of layers;

designating, by the one or more computing devices, one or more cells from a maximum layer that correspond to one or more of the content locations as included in the set of content cells; and

for each layer between the maximum layer and a minimum layer, designating, by the one or more computing devices, each cell that is a parent to one or more cells have previously been designated as content cells as included in the set of content cells.

4. The computer-implemented method of claim 1, further comprising:

identifying, by the one or more computing devices, a parent semantic entity for one or more semantic entities that have been designated as the semantic location for the map;

determining, by the one or more computing devices, a size factor for each parent semantic entity, the size factor for each parent semantic entity describing a size of a geographic area associated with such parent semantic entity relative to the size of the one or more semantic entities that are children to such parent semantic entity and have been selected as semantic locations; and

selecting, by the one or more computing device, each parent semantic entity that has a size factor that is less than a threshold factor value as an additional semantic location for the map.

5. The computer-implemented method of claim 1, further comprising:

identifying, by the one or more computing devices, a map parent location that includes greater than a threshold percentage of the selected semantic locations.

6. The computer-implemented method of claim 1, further comprising:

providing, by the one or more computing devices, the at least one semantic location selected for the map to a search engine for use by the search engine in a determination of the relevance of the map in response to a search query.

7. One or more non-transitory computer-readable media that store instructions that, when executed by one or more processors, cause the one or more processors to:

obtain information descriptive of a first plurality of content locations respectively associated with a first plurality of items of content included in a first map;

identify at least one first semantic location for the first map based at least in part on the first plurality of content locations, wherein the first semantic location comprises a smallest semantic entity that includes greater than a threshold amount of the first plurality of content locations;

obtain information descriptive of a second plurality of content locations respectively associated with a second plurality of items of content included in a second map;

identify at least one second semantic location for the second map based at least in part on the second plurality of content locations, wherein the second semantic location comprises the smallest semantic entity that includes greater than the threshold amount of the second plurality of content locations; and

determine a proximity score between the first map and the second map based at least in part on a comparison of the at least one first semantic location to the at least one second semantic location.

8. The one or more non-transitory computer-readable media of claim 7, wherein to determine the proximity score between the first map and the second map, the one or more processors:

determine at least a first parent location for the first map;

determine at least a second parent location for the second map; and

determine the proximity score between the first map and the second map based at least in part on the comparison of the at least one first semantic location to the at least one second semantic location and based at least in part on a comparison of the first parent location to the second parent location.

9. The one or more non-transitory computer-readable media of claim 7, wherein to determine the proximity score between the first map and the second map, the one or more processors:

identify at least one first neighbor location for the first map;

identify at least one second neighbor location for the second map; and

determine the proximity score between the first map and the second map based at least in part on the comparison of the at least one first semantic location to the at least one second semantic location and based at least in part on a comparison of the at least one first neighbor location to the at least one second neighbor location.

10. The one or more non-transitory computer-readable media of claim 7, wherein to determine the proximity score between the first map and the second map, the one or more processors:

identify one or more common map locations between the first map and the second map based at least in part on the comparison of the at least one first semantic location to the at least one second semantic location;

determine a total number of map locations for the first map and the second map;

calculate a ratio of the common map locations to the total number of map locations; and

determine the proximity score between the first map and the second map based at least in part on the ratio.

11. A computer-implemented method to determine semantic locations for maps, the method comprising:

obtaining, by one or more computing devices, information descriptive of a plurality of content locations respectively associated with a plurality of items of content included in a map;

identifying, by the one or more computing devices, a set of content cells based at least in part on the plurality of content locations respectively associated with the plurality of items of content included in the map, wherein each cell in the set of content cells corresponds to a particular geographic area that includes one or more of the content locations;

determining, by the one or more computing devices, a plurality of sets of feature cells respectively for a plurality of semantic entities, wherein the set of feature cells associated with each semantic entity is descriptive of a geographic area associated with such semantic entity, and wherein each of the plurality of semantic entities has a respective level associated therewith;

comparing, by the one or more computing devices, the set of content cells to the respective sets of feature cells for at least a portion of the plurality of semantic entities; and

selecting, by the one or more computing devices, at least one of the plurality of semantic entities as a semantic location for the map based at least in part on the comparison of the set of content cells to the respective set of feature cells for such at least one semantic entity, wherein selecting, by the one or more computing devices, at least one of the plurality of semantic entities as the semantic location for the map comprises;

identifying, by the one or more computing devices, a combination of two or more semantic entities that share a level and for which a percentage of the set of content cells that are included in a combined set of feature cells for such combination of two or more semantic entities exceeds a threshold percentage; and

designating, by the one or more computing devices, the two or more semantic entities included in the combination as semantic locations for the map.

12. A computer-implemented method to determine semantic locations for maps, the method comprising:

obtaining, by one or more computing devices, information descriptive of a plurality of content locations respectively associated with a plurality of items of content included in a map;

identifying, by the one or more computing devices, a set of content cells based at least in part on the plurality of content locations respectively associated with the plurality of items of content included in the map, wherein each cell in the set of content cells corresponds to a particular geographic area that includes one or more of the content locations;

determining, by the one or more computing devices, a plurality of sets of feature cells respectively for a plurality of semantic entities, wherein the set of feature cells associated with each semantic entity is descriptive of a geographic area associated with such semantic entity;

comparing, by the one or more computing devices, the set of content cells to the respective sets of feature cells for at least a portion of the plurality of semantic entities;

selecting, by the one or more computing devices, at least one of the plurality of semantic entities as a semantic location for the map based at least in part on the comparison of the set of content cells to the respective set of feature cells for such at least one semantic entity;

identifying, by the one or more computing devices, a parent semantic entity for one or more semantic entities that have been designated as the semantic location for the map;

determining, by the one or more computing devices, a size factor for each parent semantic entity, the size factor for each parent semantic entity describing a size of a geographic area associated with such parent semantic entity relative to the size of the one or more semantic entities that are children to such parent semantic entity and have been selected as semantic locations; and

selecting, by the one or more computing device, each parent semantic entity that has a size factor that is less than a threshold factor value as an additional semantic location for the map.

13. A computer-implemented method to determine semantic locations for maps, the method comprising:

obtaining, by one or more computing devices, information descriptive of a plurality of content locations respectively associated with a plurality of items of content included in a map;

identifying, by the one or more computing devices, a set of content cells based at least in part on the plurality of content locations respectively associated with the plurality of items of content included in the map, wherein each cell in the set of content cells corresponds to a particular geographic area that includes one or more of the content locations;

determining, by the one or more computing devices, a plurality of sets of feature cells respectively for a plurality of semantic entities, wherein the set of feature cells associated with each semantic entity is descriptive of a geographic area associated with such semantic entity;

comparing, by the one or more computing devices, the set of content cells to the respective sets of feature cells for at least a portion of the plurality of semantic entities;

selecting, by the one or more computing devices, at least one of the plurality of semantic entities as a semantic location for the map based at least in part on the comparison of the set of content cells to the respective set of feature cells for such at least one semantic entity; and

determining, by the one or more computing devices, a plurality of proximity scores relative to the map respectively for a plurality of second maps, the proximity score for each second map based at least in part on the semantic locations selected for the map and one or more second semantic locations associated with such second map.

14. The computer-implemented method of claim 13, further comprising:

identifying, by the one or more computing devices, at least one of the plurality of second maps as a related map based at least in part on the proximity scores for the plurality of second maps; and

recommending, by the one or more computing devices, the related map to a user that is viewing the map.

15. The computer-implemented method of claim 13, wherein the proximity score for each second map is further based at least in part on a number of shared neighbor locations between the semantic locations selected for the map and the one or more second semantic locations associated with such second map.