Method for organizing map data

• US 7,062,377 B2
• Filed: 08/17/2005
• Issued: 06/13/2006
• Est. Priority Date: 11/26/2002
• Status: Expired due to Fees

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: McDonough, William G.
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US11/205,497
• Publication Number:
  US 20060004515A1
• Time in Patent Office: 300 Days
• Field of Search: None
• US Class Current: 701/208
• CPC Class Codes: G01C 21/3881 Tile-based structures
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method of organizing map data on a physical storage medium is disclosed. The map data represents geographic features located in a geographic region. The method identifies at least one dense area in the geographic region. The map data representing the geographic features within the dense area have a data size exceeding a predetermined maximum size for a predetermined sized geographic area of the region. The method subdivides the map data representing the geographic features within the dense area into parcels so that the portion of map data contained in the parcel is close to a predetermined parcel size. The method subdivides the map data less the map data representing the dense area into parcels so that the portion of map data contained in the parcel is close to the predetermined parcel size. Additionally, the method locates the map data in each parcel together on the physical storage medium.

Claims

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

identifying at least one dense area in the geographic region, the data representing the geographic features within said dense area having a data size larger than a predetermined size for a predetermined sized area;

forming at least one small area parcel from the data representing the geographic features within said dense area, each of said small area parcels having a data size less than a predetermined maximum parcel size; and

forming at least one large area parcel from the data representing the geographic features located in the geographic region less the data representing the dense area, each of said large area parcels having a data size less than said predetermined maximum parcel size.

2. The method of claim 1 wherein the dense area includes a metropolitan area.

3. The method of claim 1 wherein the dense area has boundaries corresponding to metropolitan area boundaries.

4. The method of claim 1 wherein the dense area has boundaries following a plurality of road segments within the geographic region.

5. The method of claim 1 wherein each of the small area parcels and large area parcels has rectangular shaped boundaries.

6. The method of claim 1 wherein said small area parcels and said large area parcels have an aspect ratio less than a predetermined value.

7. The method of claim 1 wherein said step of identifying the dense area comprising:

organizing the region into a grid of tiles;

for each tile, calculating a metric value estimating an amount of map data within the tile; and

identifying each tile having the metric value greater than a maximum metric value as said dense area.

8. The method of claim 1 further comprising locating the data in each of small area parcels and each of said large area parcels on the physical storage medium.

9. A map database product formed according to the method of claim 1.

10. A navigation system having map data organized according to the method of claim 1.

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

organizing the region into a grid of tiles;

identifying at least one dense tile having an estimated map data size larger than a predetermined size;

forming a plurality of small area parcels from the map data representing the geographic features located within the dense tile, each small area parcel having a data size less than a predetermined maximum parcel size; and

forming a plurality of large area parcels from the map data less the map data representing the geographic features located within the dense tiles, each large area parcel having a data size less than said predetermined maximum parcel size.

12. The method of claim 11 wherein the tiles have a rectangular shape.

13. The method of claim 11 wherein the tiles have a fixed size.

14. The method of claim 11 wherein the large area parcels comprise the map data representing the geographic features located within at least one tile.

15. The method of claim 11 wherein the large area parcels comprise the map data representing the geographic features located within a rectangular grouping of the tiles.

16. The method of claim 11 further comprising organizing the dense tile into a plurality of subtiles, wherein said small area parcels being fanned from said subtiles.

17. The meted of claim 11 further comprising locating the data of each small area parcel and large area parcel on the physical storage medium.

18. A map database for use with a computing platform providing navigation-related features, said may database comprising:

map data that represent geographic features located in a region;

the map data are organized into a plurality of large area parcels and a plurality of small area parcels;

each of the small area parcels formed from the map data representing the geographic features located in dense areas in the region, the map data representing the geographic features located in said dense area having a data size larger than a predetermined size for a predetermined sized area, each of said small area parcels having a data size less than a predetermined maximum parcel size;

each of the large area parcels formed from the map data representing the geographic features located in the region less the map data representing the geographic features located in the dense area, each of said large area parcels having a data size less than said predetermined maximum parcel size,

said map database being stored on a computer readable medium, said map data organized into the plurality of large area parcels and the plurality of small area parcels being efficiently accessible from said computer readable medium by said computing platform to provide said navigation-related features.

19. The map database of claim 18 wherein the dense areas include metropolitan areas.

20. The map database of claim 18 said small area parcels and said large area parcels have rectangular shaped boundaries.