Method for efficiently querying multiple points in an indexed quadtree

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.

What is claimed: 
     
         1 . A system for retrieving 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, comprising:
 an index tile lookup module that determines a number of index tiles covering the points along the path;   a database interface that compares a number of index tiles against a maximum number of database lookups; and   a node retrieval module that retrieves quadtree nodes and index tiles.   
     
     
         2 . The system of  claim 1 , wherein the database interface further determines a number of database lookups to retrieve quadtree nodes based on data contained in one or more index tiles. 
     
     
         3 . The system of  claim 2 , wherein the database interface further substitutes quadtree nodes with their ancestors or descendants. 
     
     
         4 . The system of  claim 3 , wherein the database interface substitutes quadtree nodes with their descendants based on the number of covered points along the path. 
     
     
         5 . A method for retrieving elevation along a path in a geographical information system, comprising:
 receiving two or more points to create a path;   executing a plurality of database lookups on a quadtree stored in a database, wherein the number of database lookups is limited below a received threshold.