Method for organizing map data

• US 6,751,629 B2
• Filed: 05/30/2003
• Issued: 06/15/2004
• Est. Priority Date: 07/28/2000
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (HERE Holding Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: White, Kerry
• Primary Examiner(s): Rones, Charles
• Application Number:
  US10/448,674
• Publication Number:
  US 20030200228A1
• Time in Patent Office: 382 Days
• Field of Search: 707/101, 707/200, 701/209, 382/243
• US Class Current: 701/209
• 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
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method and system for organizing and storing map data that facilitates use of the map data by navigation application programs such as those in navigation systems. The map data represent geographic features located in a region. The map data are organized into parcels such that each parcel contains a portion of the map data. The map data contained in each parcel represent those geographic features contained in a corresponding separate one of a plurality of rectangular areas located in the region. Each rectangular area has a uniform dimension in a first coordinate direction but has a dimension in the other coordinate direction such that the map data that represent the geographic features contained in the rectangular area are close to, but do not exceed, a maximum data size for a parcel.

Claims

1. A method of organizing map data on a physical storage medium, wherein the map data represent geographic features in a region, the method comprising:

separating the map data into a plurality of parcels, wherein each parcel contains a portion of all the map data and wherein each parcel contains a separate plurality of data records; and

for each parcel, storing the map data for the parcel together on the data storage medium;

wherein the map data in each parcel represents the geographic features located within a separate, respective one of a plurality of rectangular areas into which the region is divided;

wherein all the rectangular areas that are adjacent to each other in an east-west direction form a row of rectangular areas that all have northern east-west boundaries at a common latitude and southern east-west boundaries at another common latitude; and

wherein the rectangular areas within a row have north-south boundaries that are selected so that the data size of a parcel containing the map data that represents the geographic features located within the rectangular area is approximately a predetermined size.

2. The method of claim 1 wherein the map data contained in a parcel are all read together from the data storage medium in one seek.

3. The method of claim 1 wherein all the rectangular areas into which the region is divided have a common dimension in the north-south direction.

4. The method of claim 1 further comprising:

when separating the map data into a plurality of parcels, reserving a percentage for parcel overhead.

5. The method of claim 1 wherein the rectangular areas all have a common north-south dimension selected to correspond in size to a display screen of a vehicle navigation system.

6. A database formed by the method of claim 1.

7. A method of organizing map data on a physical storage medium, wherein the map data represent geographic features in a region, the method comprising:

separating the map data into a plurality of parcels; and

storing the map data for each parcel together on the data storage medium;

wherein the map data in each parcel represent the geographic features located within a separate, respective one of a plurality of rectangular areas into which the region is divided;

wherein the rectangular areas are arranged in a plurality of rows, each of which contains one or more rectangular areas,

wherein, with respect to each row, all the rectangular areas therein have a common dimension in a north-south direction,

and wherein each rectangular area in a row has a dimension in the east-west direction that is selected so that the parcel containing the data that represents the geographic features located in the rectangular area has approximately a predetermined size.

8. The method of claim 7 wherein the map data contained in a parcel are all read together from the data storage medium in one seek.

9. The method of claim 7 wherein all the rectangular areas into which the region is divided have a common dimension in the north-south direction.

10. The method of claim 7 further comprising:

when separating the map data into the plurality of parcels, reserving a percentage for parcel overhead.

11. The method of claim 7 wherein all the rectangular areas in all the rows have a common north-south dimension.

12. The method of claim 11 wherein the common north-south dimension is selected to correspond in size to a display screen of a vehicle navigation system.

13. A database formed by the method of claim 7.

14. A method of organizing map data on a physical storage medium, wherein the map data represent geographic features in a region, the method comprising:

separating the map data into a plurality of parcels; and

storing the map data for each parcel together on the data storage medium;

wherein the map data in each parcel represent the geographic features located within a separate, respective one of a plurality of rectangular areas into which the region is divided;

wherein the rectangular areas are arranged in a plurality of rows, each of which contains one or more rectangular areas,

wherein the rectangular areas are arranged in a plurality of rows, each of which contains one or more of the rectangular areas,

wherein, with respect to the each row, all the rectangular areas in the row have northern boundaries at a common first latitude, southern boundaries at a common second latitude, which is different from the first latitude, and north-south boundaries that are selected so that a data size of a parcel that contains the map data that represents the geographic features located within the rectangular area formed by the northern boundary, the southern boundary and a pair of adjacent north-south boundaries is approximately a predetermined size.

15. The method of claim 14 wherein the map data contained in a parcel are all read together from the data storage medium in one seek.

16. The method of claim 14 wherein all the rectangular areas into which the region is divided have a common dimension in the north-south direction.

17. The method of claim 14 further comprising:

when separating the map data into a plurality of parcels, reserving a percentage for parcel overhead.

18. The method of claim 14 wherein all the rectangular areas in all the rows have a common north-south dimension.

19. The method of claim 18 wherein the common north-south dimension is selected to correspond in size to a display screen of a vehicle navigation system.

20. A database formed by the method of claim 14.