System and method for storing and retrieving geospatial data

• US 9,734,260 B2
• Filed: 12/19/2013
• Issued: 08/15/2017
• Est. Priority Date: 06/05/2012
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hancher, Matthew Dexter, Rohlf, John H.
• Primary Examiner(s): Chen, Susan
• Application Number:
  US14/134,128
• Publication Number:
  US 20140108464A1
• Time in Patent Office: 1,335 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/83 Querying
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06T 17/05 Geographic models

Abstract

Systems and methods for storing and retrieving geospatial data in a geographic information system are provided. Geospatial data can be spatially partitioned along axes of a spherical coordinate system associated with a virtual globe or other spheroid into a plurality of discrete geospatial volumes pursuant to a hierarchical spatial partitioning scheme. For instance, geospatial data can be spatially partitioned into geospatial volumes along surfaces of constant latitude, longitude, and altitude defined by the spherical coordinate system. The discrete geospatial volumes can be stored as nodes in a hierarchical tree data structure. Additional methods are provided for portioning geospatial objects, such as tiles or discrete geospatial volumes, in tritree to reduce polar distortions.

Claims

1. A computer-implemented method of storing geospatial data in a geographic information system for a spheroid, the method comprising:

storing, by one or more computing devices, geospatial data associated with a polar geospatial object in a memory as at least a part of a payload of a parent node in a hierarchical tree data structure, the polar geospatial object associated with a geospatial area located adjacent to a pole of the spheroid;

spatially partitioning, by the one or more computing devices, the polar geospatial object in tritree to obtain a first set of descendant geospatial objects, the first set of descendant geospatial objects comprising first, second, and third child geospatial objects, the first geospatial object being located adjacent the pole, the second and third geospatial data objects being located away from the pole relative to the first geospatial data object, the first geospatial object associated with a geospatial area having a longitudinal span spanning a longitudinal extent of the polar geospatial object, wherein a combined longitudinal span of the second and third child geospatial data objects located away from the pole is equal to the longitudinal span of the first geospatial object;

storing, by the one or more computing devices, geospatial data associated with each of the first, second, and third child geospatial objects as at least a part of a payload of one of a plurality of child nodes of the parent node in the hierarchical tree data structure.

2. The computer-implemented method of claim 1, wherein the plurality of child nodes are selected to preserve parent-child hierarchy among geospatial objects across three or more node levels in the hierarchical tree data structure.

3. The computer-implemented method of claim 2, wherein the method comprises storing geospatial data associated with the fourth, fifth, and sixth child geospatial objects as at least a part of a payload of one of a plurality of second child nodes in the hierarchical tree data structure, each of the second child nodes being a descendant of the child node associated with the first child geospatial object.

4. The computer-implemented method of claim 1, wherein the method further comprises spatially partitioning, by the one or more computing devices, the first child geospatial object in tritree to obtain a second set of descendant geospatial objects, the second set of descendant geospatial objects comprising fourth, fifth, and sixth child geospatial objects, the fourth child geospatial object associated with a geospatial area located adjacent to the pole of the spheroid and spanning the longitudinal extent of the first child geospatial object.