Hierarchical spatial data structure and 3D index data versioning for generating packet data

• US 8,762,493 B1
• Filed: 06/22/2006
• Issued: 06/24/2014
• Est. Priority Date: 06/22/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kirmse, Andrew, Praun, Emil C., Bailly, Olivier
• Primary Examiner(s): Burgess, Glenton B
• Assistant Examiner(s): AILES, BENJAMIN A
• Application Number:
  US11/473,461
• Time in Patent Office: 2,924 Days
• Field of Search: 709/218, 382/154, 382/305
• US Class Current: 709/218
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

The disclosed implementations are related to hierarchical spatial data structures with 3D data versioning for generating packet data. The packet data can be used by a client application to determine the availability of data at certain levels of a hierarchical spatial data structure. A 3D index table storing data version information can be used to support data updates and to ensure that a consistent view of data is provided to clients without suffering interruptions in service.

Claims

1. A method comprising:

determining, at a server computer, availability of each of a plurality of data types of one or more tiles of an interactive map, wherein the tiles are arranged into multiple levels of a hierarchical spatial data structure;

generating a packet including presence information, wherein the presence information indicates to a client computer availability of each of the plurality of data types of one or more tiles at one or more levels of the hierarchical spatial data structure and version information for each data type;

serving the packet including presence information to the client computer;

after serving the packet including presence information to the client computer, receiving a request for data associated with one or more tiles identified by the presence information as being available; and

providing the requested data in response to the request,

wherein the method steps are performed by one or more processors.

2. The method of claim 1, wherein determining availability of each of a plurality of data types comprises determining availability of a version of one or more of the data types of the one or more tiles at the one or more levels of the data structure.

3. The method of claim 1, wherein the hierarchical spatial data structure is a quadtree and the method further comprises:

generating an index table having rows corresponding to quadnodes in the quadtree, wherein each of the one or more tiles corresponds to a quadnode of the quadtree, and wherein the presence information is based at least in part on data in the index table.

4. The method of claim 3, further comprising:

generating a quadtree table from the index table, the quadtree table having rows corresponding to quadsets in the quadtree, wherein the presence information is based at least in part on data in the quadtree table.

5. The method of claim 4, wherein generating presence information comprises:

for each quadnode N in the index table,

collecting information for each quadset S between quadnode N and a quadtree root, wherein the presence information includes the collected information.

6. The method of claim 1, wherein the generated packet includes presence information for a quadset including a particular quad node and multiple levels of nodes descendent from the particular quad node.

7. The method of claim 1, further comprising:

receiving a request from the client computer for one or more types of data at a particular level of the hierarchical spatial data structure; and

in response to the request, serving the requested data to the client computer.

17. The method of claim 1, wherein a data type is one or more of imagery data, terrain data, and vector data.

8. A method comprising:

receiving, at a client computer, a data packet including presence information, wherein the presence information indicates to the client computer availability of each of a plurality of data types of one or more tiles of an interactive map, wherein the tiles are arranged into multiple levels of a hierarchical spatial data structure;

receiving, at the client computer, a first user navigation command of the interactive mapping system, the command requesting data of a particular tile at a particular level of the hierarchical spatial data structure;

determining from the presence information received in the data packet, that data of the particular tile is available; and

in response to determining from the presence information that the data of the particular tile is available, requesting data of the particular tile from the server computer in response to the first user navigation command,

wherein the determining is performed by one or more processors.

9. The method of claim 8, wherein the plurality of data types of presence information include imagery data, terrain data, and vector data.

10. A computer-readable storage device having stored thereon instructions, which, when executed by a processor, causes the processor to perform operations comprising:

determining, at a server computer, availability of each of a plurality of data types of one or more tiles of an interactive map, wherein the tiles are arranged into multiple levels of a hierarchical spatial data structure;

generating a packet including presence information, wherein the presence information indicates to a client computer availability of each of the plurality of data types of one or more tiles at one or more levels of the hierarchical spatial data structure;

serving the packet including presence information to the client computer;

after serving the packet including presence information to the client computer, receiving a request for data associated with the one or more tiles identified by the presence information as being available; and

providing the requested data in response to the request.

11. The computer-readable storage device of claim 10, wherein determining availability of each of a plurality of data types comprises determining availability of a version of one or more of the data types of the one or more tiles at the one or more levels of the data structure.

12. The computer-readable storage device of claim 10, wherein the hierarchical spatial data structure is a quadtree and the instructions further cause the processor to perform operations comprising:

generating an index table having rows corresponding to quadnodes in the quadtree, wherein each of the one or more tiles corresponds to a quadnode of the quadtree, and wherein the presence information is based at least in part on data in the index table.

13. The computer-readable storage device of claim 12, further comprising:

generating a quadtree table from the index table, the quadtree table having rows corresponding to quadsets in the quadtree, wherein the presence information is based at least in part on data in the quadtree table.

14. The computer-readable storage device of claim 13, where generating presence information comprises:

for each quadnode N in the index table,

collecting information for each quadset S between quadnode N and a quadtree root, wherein the presence information includes the collected information.

15. A computer-readable storage device having stored thereon instructions, which, when executed by a processor, cause the processor to perform operations comprising:

receiving, at a client computer, a data packet including presence information, wherein the presence information indicates to the client computer availability of each of a plurality of data types of one or more tiles of an interactive map, wherein the tiles are arranged into multiple levels of a hierarchical spatial data structure;

receiving, at the client computer, a first user navigation command of the interactive mapping system, the command requesting data of a particular tile at a particular level of the hierarchical spatial data structure;

determining from the presence information received in the data packet, that data of the particular tile is available; and

in response to determining from the presence information that the data of the particular tile is available, requesting data of the particular tile from the server computer in response to the first user navigation command.

16. A system comprising:

one or more processors; and

a computer storage medium storing instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

determining, at a server computer, availability of each of a plurality of data types of one or more tiles of an interactive map, wherein the tiles are arranged into multiple levels of a hierarchical spatial data structure;

generating a packet including presence information, wherein the presence information indicates to a client computer availability of each of the plurality of data types of one or more tiles at one or more levels of the hierarchical spatial data structure;

serving the packet including presence information to the client computer;

after serving the packet including presence information to the client computer, receiving a request for data associated with the one or more tiles identified by the presence information as being available; and

providing the requested data in response to the request.