Server for geospatially organized flat file data

• US 7,225,207 B1
• Filed: 10/10/2002
• Issued: 05/29/2007
• Est. Priority Date: 10/10/2001
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Aubin, Mark A, Ohazama, Chikai J, Keslin, Phillip C
• Primary Examiner(s): Ali; Mohammad
• Application Number:
  US10/270,272
• Time in Patent Office: 1,692 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205, 709/203, 701/213
• US Class Current: 1/1
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: Y10S 707/919 Geographic
• CPC Class Codes: Y10S 707/921 Spatial
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A flat file data organization technique is used for storing and retrieving geospatially organized data. The invention reduces transfer time by transferring a few large files in lieu of a large number of small files. It also moves the process of locating a given data file away from the file system to a proprietary code base. Additionally, the invention simplifies database management by having quadtree packets generated on demand.

Claims

1. A method of merging a first packet of geospatial data with a second packet of geospatial data, comprising:

a) creating a first list of node descriptors from the first packet of geospatial data;

b) creating a second list of node descriptors from the second packet of geospatial data;

c) if at least one node descriptor remains in the first list;

c.1) obtaining a next node descriptor in the first list;

c.2) determining a first position associated with the node descriptor in the first list, the first position having a first level;

d) if at least one node descriptor remains in the first list and at least one node descriptor remains in the second list;

d.1) obtaining the next node descriptor in the second list;

d.2) determining a second position associated with the node descriptor in the second list, the second position having a second level;

d.3) if the first level is less than the second level, adding the node descriptor in the first list to a merged list of node descriptors; and

d.4) if the first level is greater than the second level, adding the node descriptor in the second list to the merged list of node descriptors;

e) if at least one node descriptor remains in the first list and no node descriptors remain in the second list;

e.1) adding the node descriptor in the first list to the merged list of node descriptors;

f) if no node descriptors remain in the first list and at least one node descriptor remains in the second list;

f.1) adding the node descriptor in the second list to the merged list of node descriptors; and

g) creating a merged packet from the merged list.

2. The method of claim 1, wherein step d) further comprises:

d.5) if the first level is equal to the second level;

d.5.1) determining a first child number of the first position and a second child number of the second position;

d.5.2) if the first child number is less than the second child number, adding the node descriptor in the second list to the merged list of node descriptors;

d.5.3) if the first child number is greater than the second child number, adding the node descriptor in the first list to the merged list of node descriptors; and

d.5.4) if the first child number is equal to the second child number, merging the node descriptor in the first list with the node descriptor in the second list and adding the merged node descriptor to the merged list of node descriptors.

3. A computer program product for merging a first packet of geospatial data with a second packet of geospatial data, comprising:

a computer-readable medium; and

computer program code, encoded on the medium, for;

a) creating a first list of node descriptors from the first packet of geospatial data;

b) creating a second list of node descriptors from the second packet of geospatial data;

c) if at least one node descriptor remains in the first list;

c.1) obtaining a next node descriptor in the first list;

c.2) determining a first position associated with the node descriptor in the first list, the first position having a first level;

d) if at least one node descriptor remains in the first list and at least one node descriptor remains in the second list;

d.1) obtaining the next node descriptor in the second list;

d.2) determining a second position associated with the node descriptor in the second list, the second position having a second level;

d.3) if the first level is less than the second level, adding the node descriptor in the first list to a merged list of node descriptors; and

d.4) if the first level is greater than the second level, adding the node descriptor in the second list to the merged list of node descriptors;

e) if at least one node descriptor remains in the first list and no node descriptors remain in the second list;

e.1) adding the node descriptor in the first list to the merged list of node descriptors;

f) if no node descriptors remain in the first list and at least one node descriptor remains in the second list;

f.1) adding the node descriptor in the second list to the merged list of node descriptors; and

g) creating a merged packet from the merged list.

4. The computer program product of claim 3, wherein the computer program code for performing step d) further comprises computer program code for:

d.5) if the first level is equal to the second level;

d.5.1) determining a first child number of the first position and a second child number of the second position;

d.5.2) if the first child number is less than the second child number, adding the node descriptor in the second list to the merged list of node descriptors;

d.5.3) if the first child number is greater than the second child number, adding the node descriptor in the first list to the merged list of node descriptors; and

d.5.4) if the first child number is equal to the second child number, merging the node descriptor in the first list with the node descriptor in the second list and adding the merged node descriptor to the merged list of node descriptors.

5. A system for merging a first packet of geospatial data with a second packet of geospatial data, comprising:

a node descriptor list module, for creating a first list of node descriptors from the first packet of geospatial data and for creating a second list of node descriptors from the second packet of geospatial data;

a merge module, coupled to the node descriptor list module, for, if at least one node descriptor remains in the first list;

obtaining a next node descriptor in the first list;

determining a first position associated with the node descriptor in the first list, the first position having a first level;

if at least one node descriptor remains in the first list and at least one node descriptor remains in the second list;

obtaining the next node descriptor in the second list;

determining a second position associated with the node descriptor in the second list, the second position having a second level;

if the first level is less than the second level, adding the node descriptor in the first list to a merged list of node descriptors; and

if the first level is greater than the second level, adding the node descriptor in the second list to the merged list of node descriptors;

if at least one node descriptor remains in the first list and no node descriptors remain in the second list;

adding the node descriptor in the first list to the merged list of node descriptors;

if no node descriptors remain in the first list and at least one node descriptor remains in the second list;

adding the node descriptor in the second list to the merged list of node descriptors; and

creating a merged packet from the merged list.

6. The system of claim 5, wherein if the first level is equal to the second level, the merge module performs the steps of:

determining a first child number of the first position and a second child number of the second position;

if the first child number is less than the second child number, adding the node descriptor in the second list to the merged list of node descriptors;

if the first child number is greater than the second child number, adding the node descriptor in the first list to the merged list of node descriptors; and

if the first child number is equal to the second child number, merging the node descriptor in the first list with the node descriptor in the second list and adding the merged node descriptor to the merged list of node descriptors.