Speed profile dictionary

• US 8,396,663 B2
• Filed: 12/15/2009
• Issued: 03/12/2013
• Est. Priority Date: 12/15/2009
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq B.V.
• Inventors: Tennent, Toby S., Aper, Michael L., Lindsay, Matthew G., Rockwood, Gary R.
• Primary Examiner(s): Algahaim, Helal A
• Application Number:
  US12/637,980
• Publication Number:
  US 20110144900A1
• Time in Patent Office: 1,183 Days
• Field of Search: 701/119, 701/410, 701/414, 701/532
• US Class Current: 701/532
• CPC Class Codes: G01C 21/3492 employing speed data or traffic data, e.g. real-time or historical traffic control systems for road vehicles involving transmission of navigation instructions to the vehicle G08G1/0968
• CPC Class Codes: G08G 1/0112 from the vehicle, e.g. floating car data [FCD]
• CPC Class Codes: G08G 1/0116 from roadside infrastructure, e.g. beacons
• CPC Class Codes: G08G 1/012 from other sources than vehicle or roadside beacons, e.g. mobile networks
• CPC Class Codes: G08G 1/0129 for creating historical data or processing based on historical data
• CPC Class Codes: G08G 1/0141 for traffic information dissemination

Abstract

A speed profile dictionary and associated lookup tables are disclosed. A set of distinct speed profiles is defined using a statistical analysis routine. Preferably, the statistical analysis routine uses clustering. The speed profiles are then matched to location codes identifying physical locations on a road network and days of the week. Applications using historic traffic data may use the speed profile dictionary and one or more lookup tables instead of a complete historic traffic database, thereby reducing the amount of memory needed to store historic traffic data.

Claims

1. A computer-implemented method for generating a speed profile dictionary embedded in a computer readable memory, comprising:

receiving, by a processor, historic traffic data associated with a road network in a geographic area;

partitioning, by the processor, the historic traffic data into speed data ranges;

analyzing, by the processor, the historic traffic data by partition to generate a plurality of speed profiles;

determining, for each of the plurality of speed profiles, whether any other of the plurality of speed profiles are substantially similar and combing those of the plurality of speed profiles which are determined to be substantially similar to each other into a combined speed profile;

assigning, by the processor, a unique identifier to each of the combined speed profiles and each remaining speed profile of the plurality of speed profiles determined not to be substantially similar to another of the plurality of speed profiles;

associating, by the processor, each of the combined speed profiles and each remaining speed profile of the plurality of speed profiles determined not to be substantially similar to another of the plurality of speed profiles to location codes that reference physical locations on the road network and day codes that reference days of a week; and

providing, by the processor, a lookup table that references the unique speed profile identifier by the location code and the day code, the unique speed profile identifier then being used to determine the assigned combined speed profile or speed profile of the plurality of speed profiles determined not to be substantially similar to another of the plurality of speed profiles.

2. The method of claim 1, wherein the historic traffic data includes historic speed data associated with the road network.

3. The method of claim 1, wherein analyzing the historic traffic data includes organizing the historic traffic data by the location code, the day code, and a plurality of time periods.

4. The method of claim 1, wherein analyzing the historic traffic data includes performing a cluster analysis.

5. The method of claim 4, wherein the cluster analysis is performed for each partition and the number of clusters per partition is equal to (partition location code count/total location code count)*target output of clusters+2.

6. The method of claim 1, wherein analyzing the historic traffic data includes identifying similar speed profiles using a least squares error analysis.

7. The method of claim 6, further comprising combining speed profiles that are similar.

8. A system for generating a speed profile dictionary, comprising in combination:

a processor;

data storage; and

machine language instructions stored in the data storage executable by the processor to;

analyze historic traffic data within speed data ranges to generate a plurality of speed profiles, wherein the historic traffic data is associated with a road network in a geographic area;

determine, for each of the plurality of speed profiles, whether any other of the plurality of speed profiles are substantially similar and combine those of the plurality of speed profiles which are determined to be substantially similar to each other into a combined speed profile;

assign a unique identifier to each of the combined speed profiles and each remaining speed profile of the plurality of speed profiles determined not to be substantially similar to another of the plurality of speed profiles;

associate each of the combined speed profiles and each remaining speed profile of the plurality of speed profiles determined not to be substantially similar to another of the plurality of speed profiles to location codes that reference physical locations on the road network and day codes that reference days of a week; and

provide a lookup table that references the unique speed profile identifier by the location code and the day code, the unique speed profile identifier then being used to determine the assigned combined speed profile or speed profile of the plurality of speed profiles determined not to be substantially similar to another of the plurality of speed profiles.

9. The system of claim 8, wherein the historic traffic data includes historic speed data associated with the road network.

10. The system of claim 8, wherein the historic traffic data is stored in a data store and organized by the location code, the day code, and a plurality of time periods.

11. The system of claim 8, wherein clustering is used to analyze the historic traffic data within speed data ranges.

12. A computer-implemented method for providing route guidance embedded in a computer readable memory, comprising:

receiving, by a processor, a request for route guidance from a user, wherein the request includes a origin, a destination, and a departure day and time;

calculating, by the processor, a route from the origin to the destination;

identifying, by the processor, at least one location code associated with a physical location along the route;

using, by the processor, the at least one location code and the departure day to obtain a speed profile identifier from a lookup table, the speed profile identifier identifying in a speed profile dictionary one of a unique speed profile unique to the location code or a combined speed profile comprising a combination of substantially similar speed profiles;

obtaining, by the processor, the identified unique speed profile or combined speed profile from the speed profile dictionary using the speed profile identifier;

calculating, by the processor, an estimated time of travel for the route using the speed profile; and

providing, by the processor, the route and the estimated time of travel to the user.

13. The method of claim 12, wherein the departure day and time is based on the day and time the user requests route guidance.

14. The method of claim 12, further receiving an arrival day and time.

15. The method of claim 14, further calculating an estimated time of departure to arrive at the received arrival day and time.

16. The method of claim 15, further providing the estimated time of departure to the user.