Speed Profile Dictionary

• US 20110144900A1
• Filed: 12/15/2009
• Published: 06/16/2011
• Est. Priority Date: 12/15/2009
• Status: Active Grant

• Current Assignee: HERE Global B.V. (Nokia Corporation)
• Original Assignee: Navteq North America LLC (Nokia Corporation)
• Inventors: Rockwood, Gary R., Aper, Michael L., Tennent, Toby S., Lindsay, Matthew G.
• Granted Patent: US 8,396,663 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• 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 historic traffic data associated with a road network in a geographic area;

partitioning the historic traffic data into speed data ranges;

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

assigning each speed profile a unique identifier;

associating 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 a lookup table that references the speed profile identifier by the location code and the day code.

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;

assign each speed profile a unique identifier;

associate the plurality of speed profiles to location codes that reference physical locations on the road network and day codes; and

provide a lookup table that references the speed profile identifier by the location code and the day code.

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 a request for route guidance from a user, wherein the request includes a origin, a destination, and a departure day and time;

calculating a route from the origin to the destination;

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

using the at least one location code and the departure day to obtain a speed profile identifier from a lookup table;

obtaining a speed profile from a speed profile dictionary using the speed profile identifier;

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

providing 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.