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

• US 7,197,500 B1
• Filed: 10/22/2001
• Issued: 03/27/2007
• Est. Priority Date: 10/25/1996
• Status: Expired due to Fees

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Bouzide, Paul M., Crane, Aaron I., Fernekes, Robert P., Israni, Vijaya S., Lampert, David S., Meek, James A., Ashby, Richard A., Nyczak, Gregory M., Jasper, John C., Smith, Nicholas E.
• Primary Examiner(s): Kindred; Alford
• Assistant Examiner(s): Thai; Hanh
• Application Number:
  US10/007,910
• Time in Patent Office: 1,982 Days
• Field of Search: 707/100, 701207-210, 702/5, 34099514- 15
• US Class Current: 707/809
• CPC Class Codes: G01C 21/3815 Road data
• CPC Class Codes: G01C 21/3878 Hierarchical structures, e.g. layering
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: Y10S 707/92 Navigation

Abstract

An improved method and system for storage of data that represent geographic features in a region. The data are organized into parcels each of which contains data that represent those geographic features that are located within a separate one of a plurality of rectangular areas into the region is divided. The method identifies linearly extending features that extend across multiple rectangular areas so that data representing the linearly extending feature can be included in each parcel that contains data that represents a rectangular area in which the linearly extending feature extends at least in part.

Claims

1. A computer-implemented method of enhancing an existing database product that contains data that represent road segments located within a geographic region, the method comprising:

using a source geographic database that contains data entities that represent road segments, wherein each data entity that represents a road segment identifies physical positions along the represented road segment;

for each of said data entities that represents a road segment, if a distance between two adjacent physical positions identified by the data entity as being located along the represented road segment exceeds a threshold, determining a third physical position between said two adjacent physical positions; and

storing a representation of the road segment that identifies the third physical position.

2. The method of claim 1 wherein said threshold is defined by a length.

3. The method of claim 1 wherein said threshold is 512/100,000 of a degree in an east-west direction.

4. The method of claim 1 wherein said threshold is 512/100,000 of a degree in a north-south direction.

5. The method of claim 1 further comprising:

separating the data into a plurality of parcels, wherein each of said plurality of parcels includes a plurality of data entities and wherein the plurality of data entities contained in each of said parcels conforms to a predetermined uniform parcel size.

6. The method of claim 5 further comprising:

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.

7. The method of claim 1 further 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.

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

9. A computer-implemented method of an existing database product that contains data that represent road segments located within a geographic region, the method comprising:

using a source geographic database that contains data entities that represent road segments, wherein each data entity that represents a road segment identifies physical positions along the represented road segment;

for each data entity that represents a road segment, if a portion of the road segment between two adjacent physical positions identified by the data entity as being located along the represented road segment crosses more than two parcel boundaries, determining a third physical position along the represented road segment between said two adjacent physical positions and between said two parcel boundaries; and

storing a representation of the road segment that identifies the third physical position,

wherein said parcel boundaries divide the geographic region into a plurality of rectangular areas, wherein the road segments located in each of said plurality of rectangular areas are represented by data entities located in a separate respective one of a plurality of parcels.

10. The method of claim 9 wherein each of said parcels corresponds to a uniform parcel size.

11. The method of claim 9 further comprising:

prior to the step determining, forming a list of parcels that each segment crosses; and

comparing the parcels crossed by each segment with the parcels associated with data entity that represents the segment.

12. The method of claim 9 further 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.

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

14. A computer-implemented method of enhancing an existing database that contains data that represent roads located within a geographic region, the method comprising:

separating the data into a plurality of parcels, wherein each respective parcel of said plurality of parcels includes a plurality of data entities that represent the roads located within parcel boundaries associated with said respective parcel,

wherein the step of separating comprises;

determining parcel boundaries for forming parcels of said data; and

for each parcel of said data,

identifying each road that crosses the parcel boundaries associated with said parcel but which is represented by a data entity defined by geographic coordinates located outside said parcel boundaries; and

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.

15. The method of claim 14 further comprising:

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.

16. The method of claim 14 further 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.

17. The method of claim 16 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.

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

19. The method of claim 14 wherein each segment of a road is associated with two nodes located at respective endpoints thereof, and wherein the method further comprising the steps of:

evaluating each of the nodes of represented segments of roads with a plurality of criteria, wherein the plurality of criteria include

a first criterion that any number of segments, other than exactly 2 segments, can meet at a node, and

at least one other criterion;

determining that a node is an aggregated-significant node based upon said step of evaluating;

forming an aggregated segment data entity that represents in aggregation a plurality of road segments that connect between aggregated-significant nodes;

storing the aggregated segment data entity in the geographic database,

for each aggregated segment data entity formed by the forming step, forming abbreviated segment data entities that represent the plurality of segments of roads that are represented by the aggregated segment data entity; and

storing the abbreviated segment data entities in the geographic database; and

forming a normalized attribute array having a plurality of entries each of which has an index reference and a specific combination of a plurality of attributes that describe a physical feature;

and further wherein each data entity that represents a road includes an index reference, whereby attributes describing a road represented by data having a first index reference are determined by reference to an entry in the normalized attribute array corresponding to said first index reference.

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