Providing incremental updates of categorical information using a probabilistic encoding data structure

Patent metadata

Field	Value
Publication number	US-11720538-B2
Application number	US-202017109430-A
Country	US
Kind code	B2
Filing date	Dec 2, 2020
Priority date	May 20, 2020
Publication date	Aug 8, 2023
Grant date	Aug 8, 2023

Abstract

Information corresponding to one or more traversable map elements (TMEs) within a zone of interest is accessed from the geographic database. A respective category of a plurality of categories is determined for each of the one or more TMEs based at least in part on the information corresponding to the TME. A first category encoding data structure is generated based at least in part on map version agnostic identifiers corresponding to TMEs determined to be in a first category of the plurality of categories, wherein the first category encoding data structure is a probabilistic data structure configured to not provide false negatives for TMEs within the zone of interest. The first category encoding data structure is provided such that a mobile apparatus receives the first category encoding data structure.

First claim

That which is claimed:

1. A method comprising:
accessing, by a network apparatus comprising a processor, a memory storing a geographic database, and a communication interface, information corresponding to one or more traversable map elements (TMEs) within a zone of interest from the geographic database;
determining, by the network apparatus, a respective category of a plurality of categories for each of the one or more TMEs based at least in part on the information corresponding to the TME;
generating, by the network apparatus, a first category encoding data structure based at least in part on map version agnostic identifiers corresponding to TMEs determined to be in a first category of the plurality of categories, wherein the first category encoding data structure is a probabilistic data structure configured to not provide false negatives for TMEs within the zone of interest; and
providing, by the network apparatus, the first category encoding data structure such that a mobile apparatus receives the first category encoding data structure.

2. The method of claim 1 , wherein the information corresponding to the TME is a probability of finding parking along the TME or traffic information for the TME.

3. The method of claim 1 , wherein the plurality of categories are categories of likelihood to find parking along TMEs.

4. The method of claim 1 , wherein the first category encoding data structure is one of a bloom filter or a subtree data structure.

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

6. The method of claim 1 , wherein generating the first category encoding data structure comprises:
accessing map version agnostic information regarding each TME determined to be in the first category;
generating a map version agnostic identifier for each TME determined to be in the first category;
coding the map version agnostic identifier for each TME determined to be in the first category using at least one coding function; and
generating the first category encoding data structure having as members the coded map version agnostic identifiers for each TME determined to be in the first category.

7. The method of claim 1 , wherein the first category encoding data structure is provided such that the mobile apparatus receives the first category encoding data structure via a persistent connection established between the network apparatus and the mobile apparatus.

8. The method of claim 7 , further comprising:
generating, in accordance with a refresh rate, an update encoding data structure that provides an incremental update of TMEs determined to be in the first category; and
providing the update encoding data structure via the persistent connection.

9. The method of claim 8 , wherein the update encoding data structure is generated to have as members the coded map version agnostic identifiers for TMEs determined to be in the first category at a first update time and that were not in the first category at a second update time, the first update time corresponding to an update comprising the update encoding data structure and the second update time corresponding to an immediately preceding update.

10. The method of claim 9 , wherein the update encoding data structure is tested to ensure that no TMEs within the zone of interest that were determined to be in the first category at the second update time and determined to not be in the first category at the first update time satisfy the update encoding data structure.

11. 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 geographic database, the at least one memory and the computer program code configured to, with the processor, cause the apparatus to at least:
access information corresponding to one or more traversable map elements (TMEs) within a zone of interest from the geographic database;
determine a respective category of a plurality of categories for each of the one or more TMEs based at least in part on the information corresponding to the TME;
generate a first category encoding data structure based at least in part on map version agnostic identifiers corresponding to TMEs determined to be in a first category of the plurality of categories, wherein the first category encoding data structure is a probabilistic data structure configured to not provide false negatives for TMEs within the zone of interest; and
provide the first category encoding data structure such that a mobile apparatus receives the first category encoding data structure.

12. The apparatus of claim 11 , wherein the information corresponding to the TME is a probability of finding parking along the TME or traffic information for the TME.

13. The apparatus of claim 11 , wherein the plurality of categories are categories of likelihood to find parking along TMEs.

14. The apparatus of claim 11 , wherein the first category encoding data structure is one of a bloom filter or a subtree data structure.

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

16. The apparatus of claim 11 , wherein to generate the first category encoding data structure, the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to at least:
access map version agnostic information regarding each TME determined to be in the first category;
generate a map version agnostic identifier for each TME determined to be in the first category;
code the map version agnostic identifier for each TME determined to be in the first category using at least one coding function; and
generate the first category encoding data structure having as members the coded map version agnostic identifiers for each TME determined to be in the first category.

17. The apparatus of claim 11 , wherein the first category encoding data structure is provided such that the mobile apparatus receives the first category encoding data structure via a persistent connection established between the network apparatus and the mobile apparatus.

18. The apparatus of claim 17 , wherein the at least one memory and the computer program code are further configured to, with the processor, cause the apparatus to at least:
generate, in accordance with a refresh rate, an update encoding data structure that provides an incremental update of TMEs determined to be in the first category; and
provide the update encoding data structure via the persistent connection.

19. The apparatus of claim 18 , wherein the update encoding data structure is generated to have as members the coded map version agnostic identifiers for TMEs determined to be in the first category at a first update time and that were not in the first category at a second update time, the first update time corresponding to an update comprising the update encoding data structure and the second update time corresponding to an immediately preceding update.

20. The apparatus of claim 19 , wherein the update encoding data structure is tested to ensure that no TMEs within the zone of interest that were determined to be in the first category at the second update time and determined to not be in the first category at the first update time satisfy the update encoding data structure.

Assignees

• Here Global Bv

Inventors

• Cajias Raul
• Rolf Daniel

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