Multi-dimensional spatial index for a geographic database

• US 7,689,621 B1
• Filed: 11/06/2000
• Issued: 03/30/2010
• Est. Priority Date: 11/06/2000
• Status: Expired due to Fees

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Huber, Thomas, Gale, William
• Primary Examiner(s): Le; Miranda
• Application Number:
  US09/706,937
• Time in Patent Office: 3,431 Days
• Field of Search: 707 1- 10, 707100-102, 707/104.1, 707200-201, 707/743, 707/918, 707/919, 707/920, 701/205, 701/208, 701/200, 340/995.1
• US Class Current: 707/743
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: Y10S 707/918 Location
• CPC Class Codes: Y10S 707/919 Geographic
• CPC Class Codes: Y10S 707/92 Navigation

Abstract

A multi-dimensional spatial index includes at least two dimensions that define physical boundaries of the features represented by the indexed data. In addition, the multi-dimensional spatial index includes at least one additional dimension that represents another property. The other property is an orthogonal, non-spatial property. The other property may be a property of the features represented by the indexed data or the other property may be a property of the data. The other property represented by the additional dimension may include: granularity, distance, altitude, scale bounds within which each spatial entity is significant, or other property. The multi-dimensional spatial index is applicable to the storage, retrieval, visualization and traversal of spatial data sets.

Claims

1. A computer-implemented method of operating a navigation system, said method comprising:

using a geographic database stored on a computer readable storage medium containing data that represents geographic features, wherein said database includes a single indexing structure with three dimensions, wherein said indexing structure is a k-d tree comprising a root node, intermediate nodes and leaf nodes, wherein each node is part of a parent-child relationship wherein each parent node includes control information from which one of at least two child nodes associated with the parent node are distinguishable based on a search key, wherein a first dimension of said three dimensions includes latitude boundary information, wherein a second dimension of said three dimensions includes longitude boundary information, wherein said latitude boundary information and said longitude boundary information define a bounded area represented by a maximum latitude, a maximum longitude, a minimum latitude and a minimum longitude, wherein a third dimension of said three dimensions includes rank information,

wherein each of said geographic features have an associated rank information, wherein said rank information has at least two levels, a first level of rank is associated with the geographic features of greater importance and a second level of rank is associated with geographic features of lesser importance,

searching said geographic database stored on the computer readable storage medium for data representing a geographic feature using a latitude value, a longitude value and a rank value, wherein said search uses said first and second dimensions of said single indexing structure to identify the bounded area in which the latitude value and longitude value falls within, wherein said search uses said third dimension of said single indexing structure to identify said level of rank corresponding to said rank value.

3. The invention of claim 1 or 2 wherein said index is non-homogeneous.

4. The invention of claim 1 or 2 wherein said geographic features are roads.

5. The invention of claim 1 or 2 wherein said rank includes both integers and fractional values.

6. The method of claim 1 wherein said data that represent geographic features are organized into layers based on said rank associated with the represented features.

7. The invention of claim 1 or 2 wherein said index is homogeneous.

2. A computer-implemented index stored on a computer readable storage medium for a geographic database containing geographic data that represent geographic features, said index comprising:

a single index structure that includes two spatial dimensions and a non-spatial third dimension, wherein said two spatial dimensions define a bounded area represented by a maximum latitude, a maximum longitude, a minimum latitude and a minimum longitude,

wherein said single index structure is a k-d-tree index structure comprising a root node, intermediate nodes and leaf nodes, wherein each node is part of a parent-child relationship wherein each parent node includes control information from which one of at least two child nodes associated with the parent node are distinguishable based on a search key,

said geographic data indexed by said single index structure are searchable spatially using computer-executable instructions and said two spatial dimensions of said single index structure and a latitude and a longitude, said geographic data indexed by said single index structure are searchable for a non-spatial property of the indexed geographic data that represent the geographic features using computer-executable instructions and said third dimension of said single index structure, wherein said non-spatial property of the geographic data includes a rank associated with the geographic features represented by the geographic data, a granularity of said indexed geographic data, and a scale associated with said indexed geographic data, wherein said data that represent geographic features are organized into layers based on said rank associated with the represented features.

8. A computer-implemented index stored on a computer readable storage medium comprising:

a single k-d tree indexing structure that includes a first dimension, a second dimension and a third dimension, wherein said k-d-tree index structure comprising a root node, intermediate nodes and leaf nodes, wherein each node is part of a parent-child relationship wherein each parent node includes control information from which one of at least two child nodes associated with the parent node are distinguishable based on a search key,

wherein the k-d tree indexing structure is used to index parcels of geographic data, wherein said parcels are collections of said geographic data that represent geographic features encompassed within a bounded area;

wherein said first dimension includes latitude boundary information of said bounded area,

wherein said second dimension includes longitude boundary information of said bounded area, wherein said latitude boundary information and said longitude boundary information define said bounded area represented by a maximum latitude, a maximum longitude, a minimum latitude and a minimum longitude, said parcels of geographic data indexed by said single indexing structure are searchable using computer-executable instructions and a latitude value, a longitude value and said first and second dimension of said indexing structure,

wherein said third dimension includes rank information that has at least two levels, wherein a first level of rank is associated with geographic features of greater importance and a second level of rank is associated with the geographic features of lesser importance, said data indexed by said single indexing structure is searchable for said rank using computer-executable instructions and said third dimension of said single indexing structure.

9. The invention of claim 8 wherein said rank includes both integers and fractional values.

10. The invention of claim 8 wherein said geogmpkic features are roads.

11. The invention of claim 8 wherein said index is non-homogeneous.

12. The invention of claim 8 wherein said index is homogeneous.