System and method for geospatial indexing

• US 10,007,677 B1
• Filed: 11/04/2015
• Issued: 06/26/2018
• Est. Priority Date: 12/04/2014
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Hines, Steven Keith
• Primary Examiner(s): Kim, Taelor
• Assistant Examiner(s): Frumkin, Jesse P
• Application Number:
  US14/932,053
• Time in Patent Office: 965 Days
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A geospatial indexing module operating in a server device operates on an efficient index for retrieving and providing map features which represent geographic entities such as streets, roads, cities, states, buildings, bodies of water, etc. The index includes identification information for a map feature fragment, which represents at least a portion of a map feature, as well as a node in a tree data structure to which the map feature fragment corresponds and a range of levels of detail for which the map feature fragment is valid. When a user requests map data for a geographic region at a level of detail, the geospatial indexing module queries the index for all map feature fragments within the requested region and level of detail and provides the retrieved map feature fragments to the user.

Claims

1. A method for efficiently indexing geospatial data, the method comprising:

receiving, at one or more processors, a request from a client device for map data for a particular geographic region and at a particular level of detail (LOD);

selecting, by the one or more processors, at least one node of a tree data structure which corresponds to the requested geographic region and the requested LOD, wherein each descendant node in the tree data structure corresponds to a portion of a geographic area to which an ancestor node of the descendant node corresponds, and each descendant node corresponds to a higher LOD than the ancestor node corresponds, and wherein the tree data structure is associated with a plurality of map features, each map feature representing a geographic entity and including one or more map feature fragments which represent at least a portion of the corresponding map features, each map feature fragment including a geometry and corresponding to a range of LODs and a node of the tree data structure;

retrieving, by the one or more processors from the plurality of map feature fragments, a subset of map feature fragments, wherein each fragment of the subset of map feature fragments corresponds to the selected at least one node of the tree data structure or a descendant node of the selected at least one node and includes the requested LOD in the range of LODs for the respective map feature fragment, wherein at least two map feature fragments of the subset of map feature fragments correspond to a same map feature within the requested geographic region at the particular LOD, and wherein the at least two map feature fragments have different ranges of LODs; and

providing, by the one or more processors, the retrieved subset of map feature fragments to the client device.

2. The method of claim 1, wherein the subset of map feature fragments is a first subset of map feature fragments and further comprising:

retrieving, by the one or more processors from the plurality of map feature fragments, a second subset of map feature fragments, wherein each fragment of the second subset of map feature fragments corresponds to an ancestor node of the selected at least one node of the tree data structure and includes the requested LOD in the range of LODs for the respective map feature fragment; and

providing, by the one or more processors, the retrieved first and second subsets of map feature fragments to the client device.

3. The method of claim 2, wherein at least some of the map feature fragments have corresponding non-spatial attribute values, and wherein receiving a request from a client device includes receiving a request from the client device for map data for the particular geographic region, at the particular LOD, and having a non-spatial attribute value that is within a requested set of non-spatial attribute values, and further comprising:

generating, by the one or more processors, a plurality of buckets, each bucket representing a range of the corresponding non-spatial attribute values for the at least some map feature fragments;

assigning, by the one or more processors, a bucket from of the plurality of buckets to each of the at least some map feature fragments based on the corresponding non-spatial attribute value for the respective map feature fragment;

selecting, by the one or more processors, one or more of the plurality of buckets which correspond to the requested set of non-spatial attribute values;

retrieving, by the one or more processors, one or more of the at least some map feature fragments which are assigned the selected one or more buckets and correspond to the requested geographic region, and

providing, by the one or more processors, the one or more retrieved map feature fragments to the client device.

4. The method of claim 3, wherein generating the plurality of buckets comprises:

generating, by the one or more processors, a distribution of the non-spatial attribute values for the at least some map feature fragments; and

determining, by the one or more processors, one or more evenly distributed portions of the distribution wherein each portion corresponds to a bucket of the plurality of buckets.

5. The method of claim 4, wherein determining one or more evenly distributed portions of the distribution comprises determining, by the one or more processors, a plurality of quantiles based on the distribution of the non-spatial attributes, and assigning a bucket to each respective quantile.

6. The method of claim 1, wherein the range of LODs for each map feature fragment includes a minimum LOD and a maximum LOD.

7. The method of claim 2, wherein each map feature fragment further includes a priority level ranking, and further comprising retrieving, by the one or more processors, each of the first and second subsets of map feature fragments based on the respective priority level rankings.

8. A computing device comprising:

a communication interface;

one or more processors coupled to the communication interface; and

a non-transitory computer-readable medium storing thereon instructions that, when executed by the one or more processors, cause the computing device to;

receive, via the communication interface, a request from a client device for map data for a particular geographic region and at a particular level of detail (LOD),

select at least one node of a tree data structure which corresponds to the requested geographic region and the requested LOD, wherein each descendant node in the tree data structure corresponds to a portion of a geographic area to which an ancestor node of the descendant node corresponds, and each descendant node corresponds to a higher LOD than the ancestor node corresponds, and wherein the tree data structure is associated with a plurality of map features, each map feature representing a geographic entity and including one or more map feature fragments which represent at least a portion of the corresponding map features, each map feature fragment including a geometry and corresponding to a range of LODs and a node of the tree data structure,

retrieve from the plurality of map feature fragments, a subset of map feature fragments, wherein each fragment of the subset of map feature fragments corresponds to the selected at least one node of the tree data structure or a descendant node of the selected at least one node and includes the requested LOD in the range of LODs for the respective map feature fragment, wherein at least two map feature fragments of the subset of map feature fragments correspond to a same map feature within the requested geographic region at the particular LOD, and wherein the at least two map feature fragments have different ranges of LODs, and

provide, via the communication interface, the retrieved subset of map feature fragments to the client device.

9. The computing device of claim 8, wherein the subset of map feature fragments is a first subset of map feature fragments, and the instructions further cause the computing device to:

retrieve from the plurality of map feature fragments, a second subset of map feature fragments, wherein each fragment of the second subset of map feature fragments corresponds to an ancestor node of the selected at least one node of the tree data structure and includes the requested LOD in the range of LODs for the respective map feature fragment, and

provide, via the communication interface, the retrieved first and second subsets of map feature fragments to the client device.

10. The computing device of claim 9, wherein at least some of the map feature fragments have corresponding non-spatial attribute values, and wherein to receive a request from a client device the instructions cause the computing device to receive a request from the client device for map data for the particular geographic region, at the particular LOD, and having a non-spatial attribute value that is within a requested set of non-spatial attribute values, and wherein the instructions further cause the computing device to:

generate a plurality of buckets, each bucket representing a range of the corresponding non-spatial attribute values for the at least some map feature fragments,

assign a bucket from of the plurality of buckets to each of the at least some map feature fragments based on the corresponding non-spatial attribute value for the respective map feature fragment,

select one or more of the plurality of buckets which correspond to the requested set of non-spatial attribute values;

retrieve one or more of the at least some map feature fragments which are assigned the selected one or more buckets and correspond to the requested geographic region, and

provide, via the communication interface, the one or more retrieved map feature fragments to the client device.

11. The computing device of claim 10, wherein to generate the plurality of buckets, the instructions cause the computing device to:

generate a distribution of the non-spatial attribute values for the at least some map feature fragments, and

determine one or more evenly distributed portions of the distribution wherein each portion corresponds to a bucket of the plurality of buckets.

12. The computing device of claim 11, wherein to determine one or more evenly distributed portions of the distribution, the instructions cause the computing device to determine a plurality of quantiles based on the distribution of the non-spatial attributes, and assign a bucket to each respective quantile.

13. The computing device of claim 8, wherein the range of LODs for each map feature fragment includes a minimum LOD and a maximum LOD.

14. The computing device of claim 9, wherein each map feature fragment further includes a priority level ranking, and the instructions further cause the computing device to retrieve each of the first and second subsets of map feature fragments based on the respective priority level rankings.

15. A non-transitory computer-readable medium storing instructions for indexing geospatial data that, when executed by one or more processors in a computing device, cause the one or more processors to:

receive, via a communication interface, a request from a client device for map data for a particular geographic region and at a particular level of detail (LOD),

select at least one node of a tree data structure which corresponds to the requested geographic region and the requested LOD, wherein each descendant node in the tree data structure corresponds to a portion of a geographic area to which an ancestor node of the descendant node corresponds, and each descendant node corresponds to a higher LOD than the ancestor node corresponds, and wherein the tree data structure is associated with a plurality of map features, each map feature representing a geographic entity and including one or more map feature fragments which represent at least a portion of the corresponding map features, each map feature fragment including a geometry and corresponding to a range of LODs and a node of the tree data structure,

retrieve from the plurality of map feature fragments, a subset of map feature fragments, wherein each fragment of the subset of map feature fragments corresponds to the selected at least one node of the tree data structure or a descendant node of the selected at least one node and includes the requested LOD in the range of LODs for the respective map feature fragment, wherein at least two map feature fragments of the subset of map feature fragments correspond to a same map feature within the requested geographic region at the particular LOD, and

wherein the at least two map feature fragments have different ranges of LODs, and provide, via the communication interface, the retrieved subset of map feature fragments to the client device.

16. The computer-readable medium of claim 15, wherein the range of LODs for each map feature fragment includes a minimum LOD and a maximum LOD.

17. The computer-readable medium of claim 15, wherein the subset of map feature fragments is a first subset of map feature fragments, and the instructions further cause the one or more processors to:

retrieve from the plurality of map feature fragments, a second subset of map feature fragments, wherein each fragment of the second subset of map feature fragments corresponds to an ancestor node of the selected at least one node of the tree data structure and includes the requested LOD in the range of LODs for the respective map feature fragment, and

provide, via the communication interface, the retrieved first and second subsets of map feature fragments to the client device.

18. The computer-readable medium of claim 17, wherein each map feature fragment further includes a priority level ranking, and the instructions further cause the one or more processors to retrieve each of the first and second subsets of map feature fragments based on the respective priority level rankings.

19. The computer-readable medium of claim 17, wherein at least some of the map feature fragments have corresponding non-spatial attribute values, and wherein to receive a request from a client device the instructions cause the one or more processors to receive a request from the client device for map data for the particular geographic region, at the particular LOD, and having a non-spatial attribute value that is within a requested set of non-spatial attribute values, and wherein the instructions further cause the one or more processors to:

generate a plurality of buckets, each bucket representing a range of the corresponding non-spatial attribute values for the at least some map feature fragments,

assign a bucket from of the plurality of buckets to each of the at least some map feature fragments based on the corresponding non-spatial attribute value for the respective map feature fragment,

select one or more of the plurality of buckets which correspond to the requested set of non-spatial attribute values;

retrieve one or more of the at least some map feature fragments which are assigned the selected one or more buckets and correspond to the requested geographic region, and

provide, via the communication interface, the one or more retrieved map feature fragments to the client device.

20. The computer-readable medium of claim 19, wherein to generate the plurality of buckets, the instructions cause the one or more processors to:

generate a distribution of the non-spatial attribute values for the at least some map feature fragments, and

determine one or more evenly distributed portions of the distribution wherein each portion corresponds to a bucket of the plurality of buckets.