Encoding a route using a probabilistic encoding data structure

Patent metadata

Field	Value
Publication number	US-11853280-B2
Application number	US-202017109466-A
Country	US
Kind code	B2
Filing date	Dec 2, 2020
Priority date	May 20, 2020
Publication date	Dec 26, 2023
Grant date	Dec 26, 2023

Abstract

A network apparatus determines a route from an origin traversable map element (TME) to a target TME based on map data of a network version of a digital map. The route includes a list of route TMEs to be traveled from the origin TME to the target TME. The network apparatus accesses map version agnostic information identifying each TME of the list of route TMEs from the network version of the digital map; generates a map version agnostic identifier for each route TME of the list of route TMEs based on the accessed information; evaluates coding functions based at least on the map version agnostic identifier for each route TME to generate a coded identifier for each route TME; generates an encoding data structure based on the coded identifiers for the route TMEs; and provides the encoding data structure.

First claim

That which is claimed:

1. A method comprising:
determining, by a network apparatus, a route from a network version origin traversable map element (TME) to a network version target TME based on map data of a network version of a digital map, the route comprising a list of route TMEs to be traveled from the network version origin TME to the network version target TME, the route determined by a network apparatus comprising at least one processor, a memory storing the network version of the digital map, and a communication interface;
accessing, by the network apparatus, map version agnostic information identifying each TME of the list of route TMEs from the network version of the digital map;
generating, by the network apparatus, a map version agnostic identifier for each route TME of the list of route TMEs based on the accessed map version agnostic information;
evaluating, by the network apparatus, one or more coding functions based at least in part on the map version agnostic identifier for each route TME to generate at least one coded map version agnostic identifier for each route TME;
generating, by the network apparatus, an encoding data structure based on the coded map version agnostic identifiers for each route TME, wherein the encoding data structure is a probabilistic data structure configured to not provide false negatives, wherein the encoding data structure is a bloom filter or a subtree data structure; and wherein generating the encoding data structure comprises:
generating at least one coded map version agnostic identifier for at least one adjacent TME using at least one coding function of the one or more coding functions;
determining whether the at least one coded map version agnostic identifier for the at least one adjacent TME satisfies the encoding data structure, wherein an adjacent TME intersects the route and is not a route TME; and
responsive to determining that an adjacent TME satisfies the encoding data structure, increasing the size of the encoding data structure or adding a level to the encoding data structure until there are no adjacent TMEs that satisfy the encoding data structure; and

providing, by the network apparatus, the encoding data structure such that a mobile apparatus receives the encoding data structure.

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

3. The method of claim 1 , wherein the route is determined in response to receiving a route request providing information identifying the starting location and the target location.

4. The method of claim 3 , wherein the information identifying the starting location is a geolocation of a point along a mobile version origin TME corresponding to an origin and the information identifying the target location is a geolocation of a point along a mobile version target TME corresponding to a destination, wherein the mobile version origin TME and the mobile version target TME are derived from a mobile version of the digital map stored in the mobile apparatus.

5. The method of claim 1 , wherein the map version agnostic information comprises at least one of road name, TME length, a direction of travel of a TME, a functional class of a TME, or speed limit associated with a TME.

6. The method of claim 1 , wherein the one or more coding functions comprise a hash function configured to receive a salt.

7. The method of claim 6 , wherein, if the encoding data structure is the subtree data structure, each level of the subtree data structure is associated with a coding function of the one or more coding functions.

8. The method of claim 1 , further comprising determining a route length of the route by summing a length of each route segment and providing the route length with the encoding data structure.

9. The method of claim 1 , wherein the route comprises one or more waypoints between the network version origin TME and the network version target TME, the one or more waypoints defining a plurality of legs of the route, and generating the encoding data structure comprises generating an encoding data structure for each leg of the route.

10. The method of claim 1 , wherein the route is determined using a cost minimization route determination algorithm.

11. The method of claim 10 , wherein a cost value assigned to a TME for use by the cost minimization route determination algorithm for determining the route corresponds to at least one of a length of the TME or an expected time to traverse the TME.

12. The method of claim 1 , wherein the encoding data structure is provided such that the mobile apparatus receives the encoding data structure, wherein the mobile apparatus is configured to (a) decode a decoded route based at least in part on the encoded data structure and a mobile version of the digital map and (b) perform one or more navigation functions based on the decoded route.

13. An apparatus comprising at least one processor, a communications interface configured for communicating via at least one network, and at least one memory storing computer program code and a network version of a digital map, the at least one memory and the computer program code configured to, with the processor, cause the apparatus to at least:
determine a route from a network version origin TME to a network version target TME based on map data of the network version of the digital map, the route comprising a list of route TMEs to be traveled from the network version origin TME to the network version target TME;
access map version agnostic information identifying each TME of the list of route TMEs from the network version of the digital map;
generate a map version agnostic identifier for each route TME of the list of route TMEs based on the accessed map version agnostic information;
evaluate one or more coding functions based at least in part on the map version agnostic identifier for each route TME to generate at least one coded map version agnostic identifier for each route TME;
generate an encoding data structure based on the coded map version agnostic identifiers for each route TME, wherein the encoding data structure is a bloom filter or a subtree data structure; and
provide the encoding data structure such that a mobile apparatus receives the encoding data structure, wherein to generate the encoding data structure, the at least one memory and the computer program code are configured to, with the processor, cause the apparatus to at least:
generate at least one coded map version agnostic identifier for at least one adjacent TME using at least one coding function of the one or more coding functions;
determine whether the at least one coded map version agnostic identifier for the at least one adjacent TME satisfies the encoding data structure, wherein an adjacent TME intersects the route and is not a route TME; and
responsive to determining that an adjacent TME satisfies the encoding data structure, increase the size of the encoding data structure or add a level to the encoding data structure until there are no adjacent TMEs that satisfy the encoding data structure.

14. The apparatus of claim 13 , wherein the one or more coding functions comprise a hash function configured to receive a salt, and wherein, if the encoding data structure is the subtree data structure, each level of the subtree data structure is associated with a level-specific salt.

15. The apparatus of claim 13 , wherein the route is determined using a cost minimization route determination algorithm and a cost value assigned to a TME for use by the cost minimization route determination algorithm for determining the route correspon

Assignees

• Here Global Bv

Inventors

• Rolf Daniel
• Cajias Raul

Classifications

• G06F16/2246 Primary

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

• G01C21/3415

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title

• G01C21/3446

  Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes · CPC title

• G01C21/3453

  Special cost functions, i.e. other than distance or default speed limit of road segments · CPC title

• G01C21/3667

  Display of a road map (G01C21/3614 takes precedence; guidance using 3D or perspective road maps G01C21/3635) · CPC title