Segment aggregation and interleaving of data types in a geographic database and methods for use thereof in a navigation application

• US 6,507,850 B1
• Filed: 12/20/1999
• Issued: 01/14/2003
• Est. Priority Date: 03/16/1998
• Status: Expired due to Term

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navigation Technologies Corp. (Nokia Corporation)
• Inventors: Bouzide, Paul M., Fernekes, Robert P., Israni, Vijaya S., Smith, Nicholas E., Livshutz, Michael, Kavakh, Asta, Doddapaneni, Srinivasa, Natesan, Senthil K., McDonough, William, Meek, James A., Ashby, Richard A., Friederich, Matthew, Jasper, John C.
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/467,276
• Time in Patent Office: 1,121 Days
• Field of Search: 707/104, 707/1, 707/102, 707/200, 707/100, 707/4, 707/2, 701/208, 701/117, 701/200, 701/211, 701/202, 701/209, 701/207, 701/213, 701/206, 701/210, 701/217, 701/25, 701/212, 701/214, 711/157, 711/173, 340/995, 342/357.13, 342/457
• US Class Current: 1/1
• 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/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A geographic database for use with a navigation application program that provides navigation features to an end-user. The geographic database includes a plurality of data records of a first type and a plurality of data records of a second type. The plurality of records of the first type are organized into a plurality of parcels, each of which includes a plurality of data records of the first type and the plurality of records of the second type are organized into a plurality of parcels, each of which includes a plurality of data records of the second type. The parcels of data records of the first type are interleaved with the parcels of data records of the second type. This interleaving enables navigation functions that use these different types to access these different types more quickly and efficiently, thereby enhancing navigation system performance. Also disclosed is a method for forming a geographic database that includes a plurality of data records that represent geographic features and which can be used in a navigation system. The method includes the step of interleaving parcels containing pluralities of data records of a first type with parcels containing pluralities of data records of a second type.

Claims

1. A method for forming a geographic database that contains data entities of more than one type comprising:

separating a plurality of data entities of a first type into a first plurality of parcels wherein each parcel of said first plurality of parcels includes a portion of said plurality of data entities of said first type;

separating a plurality of data entities of a second type into a second plurality of parcels wherein each parcel of said second plurality of parcels includes a portion of said plurality of data entities of said second type; and

storing said first plurality of parcels and said second plurality of parcels in a geographic database, wherein said first plurality of parcels and said second plurality of parcels are interleaved with each other.

2. The method of claim 1 wherein said plurality of data entities of said first type are separated into parcels spatially.

3. The method of claim 1 wherein the plurality of data entities of said first type are separated into parcels so that the data entities in each parcel of said first plurality of parcels represent geographic features that are encompassed together within a rectangular area which is separate from rectangular areas that encompass geographic features that are represented by data entities contained in each of the other parcels of said first plurality of parcels.

4. The method of claim 1 wherein said plurality of data entities of said first type are separated into parcels spatially and wherein said plurality of data entities of second first type are separated into parcels spatially.

5. The method of claim 1 wherein the plurality of data entities of said first type are separated into parcels so that the data entities in each parcel of said first plurality of parcels represent geographic features that are encompassed together within a rectangular area which is separate from rectangular areas that encompass geographic features that are represented by data entities contained in each of the other parcels of said first plurality of parcels, and wherein the plurality of data entities of said second type are separated into parcels so that the data entities in each parcel of said second plurality of parcels represent geographic features that are encompassed together within a rectangular area which is separate from rectangular areas that encompass geographic features that are represented by data entities contained in each of the other parcels of said second plurality of parcels.

6. The method of claim 1 wherein data entities of said first type include attributes that represent segments of roads and wherein data entities of said second type include attributes that are abbreviated representations of segments of roads.

7. The method of claim 1 wherein said first type of data entities includes routing data and wherein said second type of data entities includes cartographic data.

8. The method of claim 1 wherein said first type of data entities includes point-of-interest data and wherein said second type of data entities includes cartographic data.

9. The method of claim 1 wherein data entities of said second type are indexes for the data entities of said first type.

10. The method of claim 1 wherein said steps of separating the pluralities of data entities of said first type, separating the pluralities of data entities of said second type and storing are performed by a compiler.

11. The method of claim 1 wherein said first plurality of parcels and said second plurality of parcels are interleaved according to a custom ordering defined by an arbitrary function that specifies an explicit ordering pattern.