Method, apparatus, and computer program product for requesting traffic data using subtree data structure

Patent metadata

Field	Value
Publication number	US-11922801-B2
Application number	US-202017079050-A
Country	US
Kind code	B2
Filing date	Oct 23, 2020
Priority date	Oct 23, 2020
Publication date	Mar 5, 2024
Grant date	Mar 5, 2024

Abstract

A method, an apparatus, and a computer program product may be provided for requesting traffic data. The apparatus may determine at least one map area comprising road segments, said map area having at least one map area identifier, determine road segment identifiers for the road segments of the at least one map area, send to a data service, a request for traffic data, said request identifying the map area, and receive from the data service, a subtree data structure set, the subtree data structure set comprising a plurality of subtree data structures, said subtree data structures in the set corresponding to traffic ranges. The apparatus may associate a road segment in a corresponding traffic range based on the road segment identifier satisfying one subtree data structure of the traffic range and provide the traffic range as traffic data for the road segment to a navigation application.

First claim

We claim:

1. A method, comprising:
determining at least one map area comprising road segments, said map area having at least one map area identifier;
determining road segment identifiers for the road segments of the at least one map area;
sending to a data service, a request for traffic data, said request identifying the map area;
receiving from the data service, a subtree data structure set, the subtree data structure set comprising a plurality of subtree data structures, said subtree data structures in the set corresponding to traffic ranges;
associating a road segment to a corresponding traffic range based on the road segment identifier satisfying one subtree data structure of the traffic range; and
providing the traffic range as traffic data for the road segment to a navigation application.

2. The method of claim 1 , further comprising:
determining a geographic region encompassing at least a portion of a route;
determining for the geographic region, a plurality of map areas covering the at least one portion of a route; and
including the multiple map area identifiers in the request for traffic data.

3. The method of claim 1 , further comprising:
determining expected validity timeframes for the traffic data of the at least one map area; and
including the expected validity timeframes in the request.

4. The method of claim 1 , wherein the at least one map area corresponds to one or more map areas and wherein the at least one map area identifier corresponds to one or more map tile identifiers.

5. The method of claim 1 , wherein the subtree data structure is a prefix hash subtree or a prefix-compressed hash subtree.

6. The method of claim 1 , further comprising:
determining a traffic resolution parameter; and
sending the traffic resolution parameter as part of the request.

7. The method of claim 6 , wherein the request for traffic data is a request for traffic speed data and the traffic resolution parameter is based on a maximum speed limit of the at least one map area.

8. The method of claim 1 , wherein the determining of the road segment identifiers further comprises:
accessing map version agnostic information regarding each of the road segments;
generating a map version agnostic identifier for each of the road segments;
coding the map version agnostic identifier for each of the road segments using at least one coding function; and
providing the coded map version agnostic identifier as the road segment identifier.

9. The method of claim 1 , wherein the associating further comprises:
in response to a road segment identifier not satisfying any of the received subtree data structures, assigning traffic data to the road segment based on at least one of a local road segment speed limit parameter, a local road segment traversal cost parameter, or a local historical traffic speed pattern for the road segment.

10. An apparatus, comprising:
at least one memory configured to store computer program code instructions; and
at least one processor configured to execute the computer program code instructions to:
determine at least one map area comprising road segments, said map area having at least one map area identifier;
determine road segment identifiers for the road segments of the at least one map area;
send to a data service, a request for traffic data, said request identifying the map area;
receive from the data service, a subtree data structure set, the subtree data structure set comprising a plurality of subtree data structures, said subtree data structures in the set corresponding to traffic ranges;
associate a road segment to a corresponding traffic range based on the road segment identifier satisfying one subtree data structure of the traffic range; and
provide the traffic range as traffic data for the road segment to a navigation application.

11. The apparatus of claim 10 , wherein the at least one processor is further configured to:
determine geographic region encompassing at least a portion of a route;
determine for the geographic region, a plurality of map areas covering the at least one portion of a route;
include the multiple map area identifiers in the request for traffic data.

12. The apparatus of claim 10 , wherein the at least one processor is further configured to:
determine expected validity timeframes for the traffic data of the at least one map area; and,
include the expected validity timeframes in the request.

13. The apparatus of claim 10 , wherein the at least one map area corresponds to one or more map tiles and wherein the at least one map area identifier corresponds to one or more map tile identifiers.

14. The apparatus of claim 10 , wherein the subtree data structure is a prefix hash subtree or a prefix-compressed hash subtree.

15. The apparatus of claim 10 , wherein the at least one processor is further configured to:
determine a traffic resolution parameter; and
send the traffic resolution parameter as part of the request.

16. The apparatus of claim 15 , wherein the request for traffic data is a request for traffic speed data and the traffic resolution parameter is based on a maximum speed limit of the at least one map area.

17. The apparatus of claim 10 , wherein to determine the road segment identifiers, the at least one processor is further configured to:
access map version agnostic information regarding each of the road segments;
generate a map version agnostic identifier for each of the road segments;
code the map version agnostic identifier for each of the road segments using at least one coding function; and
provide the coded map version agnostic identifier as the road segment identifier.

18. The apparatus of claim 10 , wherein to associate, the at least one processor is further configured to:
in response to a road segment identifier not satisfying any of the received subtree data structures, assigning traffic data to the road segment based on at least one of a local road segment speed limit parameter, a local road segment traversal cost parameter, or a local historical traffic speed pattern for the road segment.

19. A computer program product comprising a non-transitory computer readable medium having stored thereon computer executable instruction which when executed by at least one processor, cause the at least one processor to carry out operations comprising:
determining at least one map area comprising road segments, said map area having at least one map area identifier;
determining road segment identifiers for the road segments of the at least one map area;
sending to a data service, a request for traffic data, said request identifying the map area;
receiving from the data service, a subtree data structure set, the subtree data structure set comprising a plurality of subtree data structures, said subtree data structures in the set corresponding to traffic ranges;
associating a road segment to a corresponding traffic range based on the road segment identifier satisfying one subtree data structure of the traffic range; and
providing the traffic range as traffic data for the road segment to a navigation application.

20. The computer program product of claim 19 , the operations further comprising:
determining a geographic region encompassing at least a portion of a route;
determining for the geographic region, a plurality of map areas covering the at least one portion of a route; and
including the multiple map area identifiers in the request for traffic data.

21. The computer program product

Assignees

• Here Global Bv

Inventors

• Cajias Raul
• Rolf Daniel

Classifications

• G08G1/00 Primary

  Traffic control systems for road vehicles (arrangement of road signs or traffic signals E01F9/00 {; automatic vehicle control B62D}) · CPC title

• G06F16/29

  Geographical information databases · CPC title

• G08G1/096775 Primary

  where the origin of the information is a central station · CPC title

• G08G1/096741

  where the source of the transmitted information selects which information to transmit to each vehicle · CPC title

• G08G1/0133

  for classifying traffic situation · CPC title