System and method for use and storage of geographic data on physical media

• US 6,308,177 B1
• Filed: 07/28/1999
• Issued: 10/23/2001
• Est. Priority Date: 10/25/1996
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Gregory M. Nyczak, Nicholas E. Smith, Richard A. Ashby, Vijaya S. Israni
• Inventors: Israni, Vijaya S., Ashby, Richard A., Nyczak, Gregory M., Smith, Nicholas E.
• Primary Examiner(s): BLACK, THOMAS G
• Assistant Examiner(s): Trinh, William
• Application Number:
  US09/362,947
• Time in Patent Office: 818 Days
• Field of Search: 707/100, 701/207, 701/208, 340/990
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G08G 1/096827 where the route is computed onboard
• CPC Class Codes: G08G 1/0969 having a display in the form of a map
• CPC Class Codes: G09B 29/106 using electronic means
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

An improved method and system for storage of geographic data on physical storage media. The geographic data are stored in a manner that facilitates and enhances use and access of the data by various navigation application functions in navigation systems that use the data. The geographic data includes a parcelization that separates the geographic data into parcels having less than or equal to a maximum parcel size but having at least a desired fill percentage. The parcelization method also provides for a division arrangement that facilitates addressing and identification of the parcels. According to a further aspect, the geographic data includes special nodal entities that are used to collapse complex intersections, such as roundabouts, cloverleaves, and divided highways, into simpler data representations. The special nodal entities are associated with road segment data entities and used in a route calculation program in place of regular node entities. Further, the geographic data include a normalized attribute array that includes reoccurring combinations of certain selected attributes of the geographic data. Indices to the array are included in place of data corresponding to the selected attributes. When a navigation application program requests data, an entry in the normalized attribute table pointed to by an index in the data is used to return the requested data in the particular combination of attributes from the normalized attribute array. The geographic data is compiled by a method that facilitates access to the data on a physical medium. According to the compilation method, data files to be stored on the medium are organized into parcels. The data records within the data files are identified by the parcel in which they are located. An arrangement of all the data files on the medium is determined and a parcel identification related to the medium is assigned to each parcel. Cross references between data records are updated to include the assigned parcel identifications and the parcels are stored on the medium.

Claims

1. A method for organizing data for storage on a physical storage medium comprising:

forming a plurality of data files wherein each of said data files has data therein;

parcelizing the data in each of said data files into a plurality of parcels;

concatenating the plurality of data files while retaining said parcelization of said data;

assigning a parcel identification to each of said plurality of parcels; and

storing said concatenation on a storage medium.

2. The method of claim 1 wherein said step of forming a plurality of data files further comprises the step of:

forming a data file for route calculation.

3. The method of claim 1 wherein said storage medium is a CD-ROM.

4. The method of claim 1 wherein said storage medium is a PCMCIA card.

5. The method of claim 1 wherein said concatenation is a single data file.

6. The method of claim 1 wherein said parcel identification includes an offset from a start of the concatenation.

7. The method of claim 1 wherein said parcel identification includes an offset from a start of the concatenation and an indication of a size of the parcel identified thereby.

8. The method of claim 1 wherein said data includes cross-references between individual records of said data, and wherein the method further comprises the step of:

after the step of assigning a parcel identification to each of said plurality of parcels, updating said cross-references to include said parcel identifications.

10. The invention of claim 7 wherein said plurality of data entities includes cross reference data, and wherein said cross-reference data includes references to parcel identifications.

11. A geographic database stored on a computer-readable medium formed according to the method of claim 1.

9. A physical storage medium for computer-readable data wherein said medium includes a plurality of similar-sized physical boundaries, comprising:

a plurality of parcels, each of said parcels including a plurality of data entities

padding added to individual parcels of said plurality of parcels to cause said parcels to conform to said similar-sized physical boundaries; and

wherein each parcel of said plurality of parcels includes a parcel identification, said parcel identification related to an offset from a start of said plurality of similar-sized physical boundaries.

12. A method of forming a database that contains data that represent geographic features located within a geographic region, wherein said database is formed for storage on a physical medium selected from a plurality of available physical media, the method comprising:

transforming geographic data from an initial format into an intermediate transfer format, wherein said geographic data in said intermediate transfer format are included in a plurality of intermediate data files, wherein said intermediate data files include separate files for different types of geographic data, wherein said separate types of geographic data comprise at least

routing data that include data entities including attributes relating to navigation;

cartographic data that include data entities including attributes relating to map display;

maneuver data that include data entities including attributes related to route guidance; and

name data that include data entities including attributes related to names of represented geographic features;

separating the data of each of said different types of geographic data into a plurality of parcels, wherein each of said plurality of parcels includes a plurality of data entities of said type and wherein the plurality of data entities contained in each of said parcels conforms to a parcel size related to characteristics of said predetermined physical medium; and

replacing temporary entity identifiers contained in said geographic data by which said data entities can be referenced with new entity identifiers, wherein said new entity identifiers identify which of said plurality of parcels contains the data entity associated with each of said new entity identifiers.

13. The method of claim 12 wherein said step of separating comprises:

for each of said types of geographic data,

estimating a resultant size for a parcel formed of a plurality of data entities of said type of geographic data, wherein said step of estimating uses variables associated with said type of geographic data being separated.

14. The method of claim 13 wherein said variables for said routing intermediate data include quantities of segment entities that exist in a given amount of geographic data.

15. The method of claim 12 wherein said step of separating comprises:

determining parcel boundaries for said routing data;

parcelizing said routing data spatially along said parcel boundaries; and

after parcelizing said routing data, parcelizing said cartographic data along the parcel boundaries determined for said routing data.

16. The method of claim 12 wherein said step of separating comprises:

determining parcel boundaries for said routing data;

parcelizing said routing data spatially along said parcel boundaries; and

while parcelizing said routing data, forming a kd-tree for said parcels of routing data.

17. The method of claim 12 wherein said step of separating comprises:

determining parcel boundaries for forming parcels for said routing data; and

for each parcel of said routing data,

using the routing data in said intermediate data files to identify each road that crosses the parcel boundaries of said parcel but which is represented by a data entity defined by geographic coordinates located outside said parcel boundaries;

determining generated shape point data for said data entity, wherein said generated shape point data represent a position along said road represented by said data entity and wherein said position is located within the parcel boundaries of said parcel; and

storing said generated shape point data in said parcel.

18. The method of claim 12 wherein said step of separating comprises:

determining parcel boundaries for forming parcels for said cartographic data; and

for each parcel of said cartographic data,

using the cartographic data in said intermediate data files to identify strands of connected road segments which are located within said parcel boundaries and which have similar attributes;

forming polyline data entities to represent said strands of connected road segments; and

storing said polyline data entities in said parcel of cartographic data.

19. The method of claim 12 further comprising:

forming a B-tree index for the name data entities included in said parcels; and

storing said B-tree index on the physical medium.

20. A geographic database stored on a computer-readable medium formed according to the method of claim 12.