Methods for efficiently querying multiple points in an indexed quadtree

• US 8,639,725 B1
• Filed: 01/31/2011
• Issued: 01/28/2014
• Est. Priority Date: 01/31/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Udeshi, Tushar, Praun, Emil
• Primary Examiner(s): Lu, Charles
• Application Number:
  US13/018,333
• Time in Patent Office: 1,093 Days
• Field of Search: 707/797, 707/793, 707/705
• US Class Current: 707/797
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/316 Indexing structures

Abstract

A method for efficiently querying multiple points in an indexed quadtree is disclosed. The elevation along a path containing points covered by nodes in a quadtree is desired. Index nodes covering the nodes with elevation data are retrieved. Based on the data in the index nodes, the highest resolution data is retrieved while limiting database lookups below a specified limit.

Claims

1. A computer implemented method in a geographical information system for reducing a number of database lookups below a maximum number for a set of desired points contained in an indexed quadtree stored in a database, where the nodes of the quadtree store elevation data, comprising:

(a) determining a number of index nodes covering all desired points;

(i) when the number of index nodes in (a) is less than or equal to a first maximum number of lookups, retrieving the index nodes from the database;

(b) determining a number of lookups required to retrieve quadtree nodes covering all desired points based on the index nodes retrieved in (i);

(i) when the number of lookups determined in (b) is greater than a second maximum number of lookups, substituting the quadtree nodes with their ancestors until the number of lookups is less than or equal to the second maximum number of lookups; and

(ii) when the number of lookups determined in (b) or (b)(i) is less than or equal to the second maximum number of lookups, retrieving the quadtree nodes covering all desired points from the database.

2. The method of claim 1, further comprising:

(c) determining the number of quadtree nodes at a coverage resolution covering all desired points when the number of index nodes determined in (a) exceeds the first maximum number of lookups;

(i) when the number of quadtree nodes determined in (c) is less than the second maximum number of lookups, adding descendant nodes of the quadtree nodes at the coverage resolution until the number of quadtree nodes is equal to the second maximum number of lookups and retrieving the quadtree nodes covering all desired points from the database; and

(ii) when the number of quadtree nodes determined in (c) is greater than the second maximum level of lookups, substituting the quadtree nodes with their ancestors until the number of quadtree nodes is equal to or less than the second maximum number of lookups, and retrieving the quadtree nodes covering all desired points from the database.

3. The method of claim 1, wherein the first maximum number of lookups and the second maximum number of lookups are equal.

4. The method of claim 2, wherein in step (c)(i), descendants are selected for addition based on the number of query points covered by the descendant.

5. A computer implemented method for determining the elevation along a path in a geographical information system consisting of geocoded points and elevations, where the elevation of the points along the path is stored in an indexed quadtree stored in a database, and where the maximum number of lookups performed on the database is set to a desired number or numbers, the method comprising:

(a) determining a number of index nodes covering all desired points along the path;

(i) when the number of index nodes in (a) is less or equal to a first maximum number of lookups, retrieving the index nodes from the database;

(b) determining a number of lookups required to retrieve quadtree nodes covering all desired points based on the index nodes retrieved in (i);

(i) when the number of lookups determined in (b) is greater than a second maximum number of lookups, substituting the quadtree nodes with their ancestors until the number of lookups required is less than or equal to the second maximum number of lookups; and

(ii) when the number of lookups determined in (b) or (b)(i) is less than or equal to the second maximum number of lookups, retrieving the quadtree nodes covering all desired points from the database.

6. The method of claim 5, further comprising:

(c) determining the number of nodes at the coverage resolution covering all points along the path when the number of index nodes determined in (a) exceeds the first maximum number of lookups;

(i) when the number of quadtree nodes determined in (c) is less than the second maximum number of lookup, adding descendant nodes of the quadtree nodes at the coverage resolution until the number of quadtree nodes is equal to the second maximum number of lookups and retrieving the quadtree nodes covering all desired points from the database; and

(ii) when the number of quadtree nodes determined in (c) is greater than the second maximum number of lookups, substituting the quadtree nodes with their ancestors until the number of quadtree nodes is equal to or the second maximum number of lookups and retrieving the quadtree nodes covering all desired points from the database.

7. The method of claim 5, wherein the coverage level is the level of the quadtree at which all nodes have data.

8. The method of claim 5, wherein the first maximum number of lookups and the second maximum level of lookups are equal.

9. The method of claim 5, further comprising determining the elevation of the points along the path from the quadtree nodes retrieved from the database.

10. The method of claim 6, further comprising determining the elevation of the points along the path from the quadtree nodes retrieved from the database.

11. The method of claim 6, wherein in step (c)(i), descendants are selected for addition based on the number of query points covered by the descendant.