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

• US 6,473,770 B1
• Filed: 10/23/2001
• Issued: 10/29/2002
• 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: Fernekes, Robert P., Ashby, Richard A., McDonough, William, Bouzide, Paul M., Israni, Vijaya S., Meek, James A., Friederich, Matthew, Jasper, John C., Smith, Nicholas E., Livshutz, Michael, Kavakh, Asta, Doddapaneni, Srinivasa, Natesan, Senthil K.
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US10/044,580
• Time in Patent Office: 371 Days
• Field of Search: 707/4, 707/200, 707/100, 707/103, 707/5, 707/8, 701/201, 701/206, 701/208, 701/214, 709/227, 342/357.09, 342/357.01, 340/991, 340/990, 340/988
• 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/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

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 of performing route calculation with a navigation system comprising:

using a geographic database containing data representing road segments in a region, wherein the data in the geographic database are organized into multiple layers, wherein each layer of said multiple layers represents a different level of detail of said road segments being represented;

obtaining real-time traffic update data via a wireless communication,

associating weighting factors indicated by the real-time traffic update data with road segments represented by data entities in the layer having greatest detail;

calculating a route using said multiple layers;

when using a layer having lesser detail, using references contained in said layer having lesser detail, wherein said references refer to data in said layer having greatest detail; and

applying said weighting factors indicated by the real-time traffic update data.

2. The method of claim 1 wherein said layer having lesser detail includes data entities that represent aggregations of segments of roads and data entities that are abbreviated representations of the segments of roads that are represented in aggregation by the data entities that represent aggregations of segments of roads.

3. The method of claim 2 wherein said references are contained among said data entities that are abbreviated representations of the segments of roads that are represented in aggregation by the data entities that represent aggregations of segments of roads.

4. The method of claim 2 wherein said data entities that represent aggregations of segments of roads are interleaved with said data entities that are abbreviated representations of the segments of roads.

5. The method of claim 2 wherein said data entities that represent aggregations of segments of roads are included in a first plurality of parcels within said layer having lesser detail and wherein said data entities that are abbreviated representations of the segments of roads are included in a second plurality of parcels within said layer having lesser detail.

6. The method of claim 5 wherein said first plurality of parcels are interleaved with said second plurality of parcels.

7. The method of claim 6 wherein said first plurality of parcels and said second plurality of parcels are spatially parcelized together.

8. A method of performing route calculation using a navigation system and real time traffic update data, wherein the navigation system uses a geographic database that includes

data entities that represent aggregations of multiple consecutive segments of roads and

data entities that represent individual segments of roads, some of which are part of the aggregations,

wherein each data entity that represents an individual segment of road that is part of one of said aggregations includes an upward reference to the data entity that represents said one of said aggregations, the method comprising:

obtaining the real-time traffic update data via wireless communication;

using said real-time traffic update data to associate weighting factors with the data entities that represent individual segments of roads that are affected by traffic;

with respect to each of said data entities that represent individual segments of roads to which said weighting factors are associated, using the upward reference included therewith to relate the weighting factor associated therewith to the data entity that represents the aggregation that includes said individual segment of road; and

calculating a solution route taking into account said weighting factors.

9. The method of claim 8 wherein said geographic database is organized into multiple layers, wherein each layer above a lowest layer excludes data entities that represent roads of corresponding lower ranks.

10. The method of claim 9 wherein the weighting factors are associated with the data entities in the lowest layer.

11. The method of claim 10 wherein each layer that includes data entities that represent aggregations of multiple consecutive segments of roads also includes abbreviated data entities that represent the individual segments of roads which are part of the aggregations, wherein each data entity that represents an aggregation refers to the abbreviated data entities in the same layer that represent the road segments that form the aggregation.

12. The method of claim 11 wherein said data entities that represent aggregations are interleaved with said abbreviated data entities that represent the segments of roads that are represented in aggregation by the data entities that represent aggregations.

13. The method of claim 11 wherein said data entities that represent aggregations are included in a first plurality of parcels within a layer and wherein said abbreviated data entities represent the segments of roads that are represented in aggregation by the data entities that represent aggregations are included in a second plurality of parcels within said same layer.

14. The method of claim 13 wherein said first plurality of parcels are interleaved with said second plurality of parcels.

15. The method of claim 13 wherein said first plurality of parcels and said second plurality of parcels are spatially parcelized together.

16. A method of using a navigation system with real time traffic update data for route calculation, wherein the navigation system uses a geographic database that contains data entities that represent segments of roads, wherein the geographic database includes a plurality of separate layers that include separate collections of the data entities based upon functional ranks of the represented segments of roads;

and further wherein the geographic database contains

data entities that represent aggregations of multiple consecutive segments of roads and abbreviated data entities that represent the individual segments of roads which are part of the aggregations, wherein each data entity that represents an aggregation refers to the abbreviated data entities that represent the road segments that form the aggregation, and further wherein the abbreviated data entities referred to by a data entity that represents an aggregation are located in the same layer as the data entity that represents the aggregation, and

non-abbreviated data entities that represent individual segments of roads, some of which are part of the aggregations, wherein the non-abbreviated data entities that represent individual segments of roads are located in a separate layer from the data entities that represent the aggregations of multiple segments of roads that represent the same segments of roads, wherein the abbreviated data entities contain references to the non-abbreviated data entities that represent the same segments of roads,

wherein the method comprises the steps of;

obtaining the real-time traffic update data via wireless communication;

using said real-time traffic update data to associate weighting factors with the non-abbreviated data entities that represent the segments of roads that are affected by traffic;

calculating a solution route using said plurality of layers; and

when using a layer that contains data entities that represent aggregations of multiple consecutive segments of roads, using the references contained in the abbreviated data entities to take said weighting factors into account.

17. The method of claim 16 further comprising:

forming a table that indicates said non-abbreviated data entities to which weighting factors are associated in order to associate weighting factors with the non-abbreviated data entities that represent segments of roads that are affected by traffic.

18. The method of claim 16 wherein said geographic database is organized into parcels of data entities, wherein the parcels containing data entities that represent aggregations of multiple consecutive segments of roads are interleaved with the parcels containing abbreviated data entities that represent the individual segments of roads.

19. The method of claim 18 wherein the parcels are organized spatially.

20. The method of claim 18 wherein each layer is spatially organized separately.