Method and system for forming, updating, and using a geographic database

• US 7,099,882 B2
• Filed: 04/29/2003
• Issued: 08/29/2006
• Est. Priority Date: 04/29/2003
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: McDonough, William
• Primary Examiner(s): Rimell, Sam
• Assistant Examiner(s): Mahmood, Rezwanul
• Application Number:
  US10/426,001
• Publication Number:
  US 20040220957A1
• Time in Patent Office: 1,218 Days
• Field of Search: 701/208, 701200-211, 707 2-200, 340/995
• US Class Current: 1/1
• CPC Class Codes: G01C 21/3874 Structures specially adapted for data searching and retrieval
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: G01C 21/3889 Transmission of selected map data, e.g. depending on route
• CPC Class Codes: G01C 21/3893 Transmission of map data from distributed sources, e.g. from roadside stations
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A method and system are disclosed for the merging of multiple map databases. These multiple map databases can be stored on separate media. Each map database is comprised of whole parcels and conforms to a baseline parcelization pattern. At run time in a navigation system, a single parcel index is constructed that contains references to parcels from the multiple map databases. References to parcels use a combined media directory covering all media objects. The combined media directory is created by merging tables of contents from each media object. This method can be used to incrementally update a geographic database.

Claims

1. A computer-implemented method for using multiple map databases in a navigation system, wherein each map database contains data that represent geographic features located within a respective coverage region associated therewith, wherein the method comprises:

forming a combined parcel index from parcel indexes associated with each of said multiple map database, wherein the combined parcel index associates parcel keys with media addresses, wherein each parcel key identifies a parcel from one of said multiple map databases, wherein the parcel so identified comprises a collection of data that represents geographic features located within a separate one of a plurality of distinct geographic areas into which the coverage regions of the map databases are divided; and

using the combined parcel index to access a selected parcel from the media address associated with the selected parcel.

2. The computer-implemented method of claim 1 wherein one of the multiple map databases is stored on a first computer-readable data storage medium and another of the multiple map databases is stored on a second computer-readable data storage medium that is different from the first computer-readable data storage medium.

3. The computer-implemented method of claim 1 further comprising:

forming a combined media table of contents that identifies a media path associated with each of the multiple map databases, wherein said combined parcel index refers to said combined media table of contents for said media path.

4. The computer-implemented method of claim 1 further comprising:

using a spatial index that associates parcel keys with geographic locations.

5. The computer-implemented method of claim 4 wherein said parcel keys in said spatial index refer to tiles in a grid, and wherein the plurality of geographic areas are defined along said grid.

6. The computer-implemented method of claim 1 wherein said step of forming is performed at run time in said navigation system.

7. The computer-implemented method of claim 1 wherein said combined parcel index is stored on a writable data storage medium in said navigation system.

8. The computer-implemented method of claim 1 wherein said combined parcel index is maintained in a memory in said navigation system.

9. The computer-implemented method of claim 1 further comprising the step of:

upon determining that more than one of said multiple map databases include collections of data that represent geographic features located within the same distinct geographic area, associating the parcel key in the combined parcel index with the media address of the collection of data that is most up-to-date.

10. The computer-implemented method of claim 1 wherein the coverage regions of said multiple map databases overlap to some extent.

11. The computer-implemented method of claim 1 wherein one of the multiple map databases is more up-to-date than another of the multiple map databases.

12. The computer-implemented method of claim 1 further comprising:

using the parcel index as a binary free for ranges of data entity identifiers associated with nodes of the parcel index that represent parcels containing said data entity identifiers.

13. A computer database for containing data that represent geographic features located in a coverage region and organized to provide navigation-related features, the database comprising:

a plurality of parcels, wherein each parcel contains a plurality of data entities, wherein the data entities in a parcel represent those geographic features located in a separate respective one of a plurality of geographic sub-regions into which coverage region is divided,

a non-updateable spatial index that identifies which parcel of the plurality of parcels contains the data that represent geographic features identified by location; and

an updatable parcel index that identifies a media address for each parcel.

14. The computer database of claim 13 further comprising:

a media table of contents, referenced by the updatable parcel index, that identifies each path where parcels of data that form the geographic database are located on media.

15. The computer database of claim 13 wherein a portion of said plurality of parcels is located on one data storage medium and another portion of said plurality of parcel is located on another, different data storage medium.

16. The computer database of claim 13 wherein said updatable parcel index also identifies distinct ranges of data entity identifiers associated with each parcel.

17. The computer database of claim 16 wherein said updatable parcel index can be used as a binary tree for finding parcels using said data entity identifiers.

18. The computer database of claim 13 wherein said updatable parcel index is stored on a re-writable medium in a navigation system.

19. The computer database of claim 13 wherein parcels are identified in said parcel index in order by parcel ID, wherein the parcel ID of a parcel indicates a relative position of the geographic sub-region corresponding to the parcel in a binary tree that represents the divisions of the coverage region that formed the geographic sub-region.

20. A computer-implemented method for distributing geographic databases comprising:

forming a baseline parcelization pattern, wherein the baseline parcelization pattern represents a separation of data in a baseline geographic database into separate groupings, wherein each grouping contains data that represent geographic features located in a separate respective distinct one of a plurality of geographic sub-regions into which a coverage region represented by the baseline geographic database is divided;

forming a first clip database, wherein the first clip database includes data entities separated into separate groupings conforming to said baseline parcelization pattern, wherein said first clip database contains data that represent geographic features located in a first sub-region, wherein said first sub-region is within, but less extensive than, said coverage region of the baseline geographic database; and

forming a second clip database, wherein the second clip database includes data entities separated into separate groupings conforming to said baseline parcelization pattern, wherein said second clip database contains data that represent geographic features located in a second sub-region, wherein said second sub-region is within, but less extensive than, said coverage region of the baseline geographic database; and

wherein said first sub-region and said second sub-region do not coincide.