Method, system, and computer program product for providing traffic data using subtree data structure

Patent metadata

Field	Value
Publication number	US-11675819-B2
Application number	US-202017079002-A
Country	US
Kind code	B2
Filing date	Oct 23, 2020
Priority date	Oct 23, 2020
Publication date	Jun 13, 2023
Grant date	Jun 13, 2023

Abstract

A method, a system, and a computer program product may be provided for providing traffic data to a client device. The system may receive from the client device, a request for traffic data corresponding to road segments of at least one map area, said request identifying the at least one map area and determine road segment identifiers corresponding to each of the road segments of the at least one map area and determine traffic data for at least a portion of the road segment identifiers, said traffic data obtained from a traffic data source. The system may further determine a plurality of traffic ranges based on the obtained traffic data and generate a subtree data structure set, each subtree data structure of the subtree data structure set corresponding to a traffic range of the plurality of traffic ranges, wherein each subtree data structure encodes road segment identifiers corresponding to the respective traffic range.

First claim

We claim:

1. A method comprising:
receiving from a client device, a request for traffic data corresponding to road segments of at least one map area, said request identifying the at least one map area;
determining road segment identifiers corresponding to each of the road segments of the at least one map area;
determining traffic data for at least a portion of the road segment identifiers, said traffic data obtained from a traffic data source;
determining a plurality of non-overlapping traffic ranges and one or more road segment identifiers corresponding to a respective one of the traffic ranges based on the obtained traffic data;
generating a subtree data structure set by applying at least one hash function on the one or more road segment identifiers, and encoding the hashed one or more road segment identifiers into a respective subtree data structure of the subtree data structure set corresponding to the respective traffic range; and
providing the subtree data structure set to the client device without the traffic data for determining a traffic range of a road segment in the at least one map area based on the subtree data structure set.

2. The method of claim 1 , wherein the generating of the subtree data structure set further comprises:
determining for each of the subtree data structure in the subtree data structure set, an identifier test set, the identifier test set comprising all road segment identifiers of the at least one map area that do not correspond to the respective traffic range of the subtree data structure;
determining whether any of the road segment identifiers of the identifier test set satisfy the subtree data structure; and
responsive to determining that a road segment identifier of the identifier test set satisfies the subtree data structure, increasing the size of the subtree data structure until there are no road segment identifiers in the identifier set that satisfy the subtree data structure.

3. 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 the at least one hash function; and
providing the coded map version agnostic identifier of each of the road segments as the road segment identifiers.

4. The method of claim 1 , wherein the subtree data structure is a prefix hash subtree or a prefix-compressed hash subtree, and wherein the client device encodes a road segment identifier of the road segment in the at least one map area using the at least one hash function, matches the encoded road segment identifier with a subtree data structure of the subtree data structure set, and determines the traffic range of the road segment identifier as a respective traffic range of the matched subtree data structure.

5. The method of claim 1 , wherein the plurality of non-overlapping traffic ranges is determined by dividing a maximum traffic speed of the traffic data for the at least one map area with a traffic resolution parameter.

6. The method of claim 5 , further comprising: determining the traffic resolution parameter based on at least one functional class of the road segments of the at least one map area.

7. The method of claim 1 , wherein the determining of traffic data for at least a portion of the road segment identifiers further comprises:
extracting at least one functional class parameter from the request for traffic data; and
determining traffic data for road segment identifiers of road segments associated with the at least one functional class parameter,
wherein each of the road segment identifiers is a text string generated by concatenating a road name, a functional class, a travel direction, a speed limit, or a combination thereof.

8. The method of claim 1 , further comprising: appending time information to the subtree data structure set, said time information indicative of a validity timeframe for the traffic data.

9. The method of claim 1 , wherein the request for traffic data comprises a map area range, a bounding box comprising map areas, or a combination thereof, and wherein the plurality of non-overlapping traffic ranges includes road segment travel directions, road segment functional classes, or road segment traffic speed quality scales.

10. A system comprising:
at least one non-transitory memory configured to store computer program code instructions; and
at least one processor configured to execute the computer program code instructions to:
receive from a client device, a request for traffic data corresponding to road segments of at least one map area, said request identifying the at least one map area;
determine road segment identifiers corresponding to each of the road segments of the at least one map area;
determine traffic data for at least a portion of the road segment identifiers, said traffic data obtained from a traffic data source;
determine a plurality of non-overlapping traffic ranges and one or more road segment identifiers corresponding to a respective one of the traffic ranges based on the obtained traffic data;
generate a subtree data structure set by applying at least one hash function on the one or more road segment identifiers, and encoding the hashed one or more road segment identifiers into a respective subtree data structure of the subtree data structure set corresponding to the respective traffic range; and
provide the subtree data structure set to the client device without the traffic data for determining a traffic range of a road segment in the at least one map area based on the subtree data structure set.

11. The system of claim 10 , wherein to generate the subtree data structure set, the at least one processor is further configured to:
determine for each of the subtree data structure in the subtree data structure set, an identifier test set, the identifier test set comprising all road segment identifiers of the at least one map area that do not correspond to the respective traffic range of the subtree data structure;
determine whether any of the road segment identifiers of the identifier test set satisfy the subtree data structure; and
in response to a road segment identifier of the identifier test set satisfying the subtree data structure, increase the size of the subtree data structure until there are no road segment identifiers in the identifier set that satisfy the subtree data structure.

12. The system 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 the at least one hash function; and
provide the coded map version agnostic identifier of each of the road segments as the road segment identifiers.

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

14. The system of claim 10 , wherein the plurality of non-overlapping traffic ranges a maximum traffic speed of the traffic data for the at least one map area with a traffic resolution parameter.

15. The system of claim 14 , wherein the at least one processor is further configured to determine the traffic resolution parameter based on at least one functional class of the road segments of the at least one map area.

16

Assignees

• Here Global Bv

Inventors

• Cajias Raul
• Rolf Daniel

Classifications

• G01C21/34

  Route searching; Route guidance · CPC title

• G08G1/096775

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

• G06F16/29 Primary

  Geographical information databases · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G08G1/0141

  for traffic information dissemination · CPC title