US-12618687-B2 - Method, system, and computer program product for generating map update data

US12618687B2US 12618687 B2US12618687 B2US 12618687B2US-12618687-B2

Abstract

A method, a system, and a computer program product for updating a map database are disclosed herein. The method comprises receiving a map update request including a bloom filter and a bounding box identifying a region of a map. The method may further comprise obtaining a plurality of second map area identifiers and the corresponding area map content. The method may further comprise computing a plurality of second digests corresponding to the plurality of second map area identifiers, based on the plurality of second map area identifiers and the second map area content and generating the map update data for the region, based on the plurality of second digests and the bloom filter.

Inventors

Raul Cajias
Daniel Rolf

Assignees

HERE GLOBAL B.V.

Dates

Publication Date: 20260505
Application Date: 20191025

Claims (20)

1 . A method for generating map update data, comprising: receiving, from a client device over a communications network by one or more processors associated with a data service, a map update request comprising a bloom filter and a bounding box identifying a region of a map, wherein the bloom filter encodes a plurality of first digests using at least one coding function on a plurality of map area identifiers of the bounding box and corresponding first map area content stored at the client device; obtaining, by the one or more processors, second area map content based on the plurality of map area identifiers correspond to the bounding box; computing, by the one or more processors, a plurality of second digests corresponding to the plurality of map area identifiers, using the at least one coding function on the plurality of map area identifiers and the second map area content; identifying, by the one or more processors, a portion of the first area map content at the client device being outdated via determining that at least one of the plurality of second digests is not an element encoded in the bloom filter; generating, by the one or more processors, the map update data for the region, wherein the map update data includes a portion of the second area map content corresponding to the at least one of the plurality of second digests; and transmitting, by the one or more processors over the communications network, the map update data to the client device.
2 . The method of claim 1 , wherein the map update request further comprises a content granularity level of the region, and the map area content includes data regarding roads, road objects, points of interest, traffic limits, or a combination thereof.
3 . The method of claim 1 , wherein the at least one coding function includes a hash function applied to each pair of the map area identifiers and the corresponding second map area content.
4 . The method of claim 3 , wherein the bloom filter is a bit array of a number of bits, and the number of bits is based on a number of the at least one coding function and a number of the map area identifiers in the bounding box.
5 . The method of claim 3 , wherein the hash function is a secure hash algorithm, or a message-digest algorithm.
6 . The method of claim 1 , wherein the map update data further includes one or more map area identifiers correspond to the portion of the second area map content.
7 . The method of claim 1 , wherein the plurality of map area identifiers and the corresponding second map area content represent data corresponding to one of map tiles or map cubes.
8 . A system for generating map update data, the system comprising: a memory configured to store computer-executable instructions; and one or more processors associated with a data service and configured to execute the instructions to: receive, from a client device over a communications network, a map update request comprising a bloom filter and a bounding box identifying a region of a map, wherein the bloom filter encodes a plurality of first digests using at least one coding function on a plurality of map area identifiers of the bounding box and corresponding first map area content stored at the client device; obtain second area map content based on the plurality of map area identifiers correspond to the bounding box; compute a plurality of second digests corresponding to the plurality of map area identifiers, using the at least one coding function on the plurality of map area identifiers and the second map area content; identify a portion of the first area map content at the client device being outdated via determining that at least one of the plurality of second digests is not an element encoded in the bloom filter; generate the map update data for the region, wherein the map update data includes a portion of the second area map content corresponding to the at least one of the plurality of second digests; and transmit, over the communications network, the map update data to the client device.
9 . The system of claim 8 , wherein the map update request further comprises a content granularity level of the region, and the map area content includes data regarding roads, road objects, points of interest, traffic limits, or a combination thereof.
10 . The system of claim 8 , wherein the at least one coding function includes a hash function applied to each pair of the map area identifiers and the corresponding second map area content.
11 . The system of claim 10 , wherein the hash function is a secure hash algorithm, or a message-digest algorithm.
12 . The system of claim 8 , wherein to generate the bloom filter is a bit array of a number of bits, and the number of bits is based on a number of the at least one coding function and a number of the map area identifiers in the bounding box.
13 . The system of claim 8 , wherein the map update data further includes one or more map area identifiers correspond to the portion of the second area map content.
14 . The system of claim 8 , wherein the plurality of map area identifiers and the corresponding second map area content represent data corresponding to one of map tiles or map cubes.
15 . A computer program product for generating map update data, comprising a non-transitory computer readable medium having stored thereon computer executable instruction which when executed by one or more processors associated with a data service, cause the one or more processors to carry out operations for updating a map database, the operations comprising: receiving, from a client device over a communications network, a map update request comprising a bloom filter and a bounding box identifying a region of a map, wherein the bloom filter encodes a plurality of first digests using at least one coding function on a plurality of map area identifiers of the bounding box and corresponding first map area content stored at the client device; obtaining second area map content based on the plurality of map area identifiers correspond to the bounding box; computing a plurality of second digests corresponding to the plurality of map area identifiers, using the at least one coding function on the plurality of map area identifiers and the second map area content; identifying a portion of the first area map content at the client device being outdated via determining that at least one of the plurality of second digests is not an element encoded in the bloom filter; generating the map update data for the region, wherein the map update data includes a portion of the second area map content corresponding to the at least one of the plurality of second digests; and transmitting, over the communications network, the map update data to the client device.
16 . The computer program product of claim 15 , wherein the map update request further comprises a content granularity level of the region, and the map area content includes data regarding roads, road objects, points of interest, traffic limits, or a combination thereof.
17 . The computer program product of claim 15 , wherein the bloom filter is a bit array of a number of bits, and the number of bits is based on a number of the at least one coding function and a number of the map area identifiers in the bounding box.
18 . The computer program product of claim 15 , wherein the map update data further includes one or more map area identifiers correspond to the portion of the second area map content.
19 . The computer program product of claim 15 , wherein the plurality of map area identifiers and the corresponding second map area content represent data corresponding to one of map tiles or map cubes.
20 . The computer program product of claim 15 , wherein the at least one coding function includes a hash function applied to each pair of the map area identifiers and the corresponding second map area content.

Description

TECHNOLOGICAL FIELD Example embodiments relate generally to navigation systems and more particularly relate to bloom filter enabled information exchange between a data service and a client for updating map data of a geographic region in a map version agnostic manner. BACKGROUND Generally, a mobile apparatus, such as a client, may submit a route request to a server, such as a system, a data service, or the like. This may trigger the server to generate the route and provide the route to the mobile apparatus. For example, the mobile apparatus may identify a starting segment and a target segment based on map data of a digital map stored in the mobile apparatus and provide the starting segment and the target segment to the server. The server receives the starting segment and the target segment, generates a route therebetween based on map data of a digital map stored in the server, and provides a list of segment identifiers to the mobile apparatus, where the segment identifiers correspond to the map data of the digital map stored by the server. However, problems can occur when the digital map stored by the mobile apparatus and the digital map stored by the server are different versions of the digital map. One solution is for the server to simply maintain multiple versions of the digital map. However, this solution is not viable for a digital map that updates frequently as the amount of memory needed to store and maintain all of the multiple versions of the digital map by the server is very large. Furthermore, performance and maintenance issues may arise due to the storage of a large number of map versions in the server. Additionally, this approach may not allow for rapid refreshing (e.g. weekly/daily updates) of the map data stored in the server. BRIEF SUMMARY OF SOME EXAMPLE EMBODIMENTS Various embodiments provide for generating map update data in a map version agnostic manner. Various embodiments provide for the generation of map update data of a region in a bandwidth efficient manner. In various embodiments, map update data is updated data of some or all segments of a route/region. Various embodiments provide for generating a map database update in response to receiving a client-side state of the map cache in a certain area using map area version agnostic identifiers and their corresponding map area content that are encoded into a bloom filter, such that the encoded identifiers and their corresponding map area content may be transmitted as a bit array to a data repository for further processing. In various embodiments, the identifiers may be map area identifiers and the bloom filter encodes map digests corresponding to each map area identifier. A map area may correspond to a partition of a map. Each map area may be identified by a unique map area identifier and each map area may or may not have its corresponding map area content (also referred to as “map content” or “content”). In some example embodiments, the map area may be a map tile (i.e. a two-dimensional partition), a map cube (i.e. a three-dimensional partition), or any other arbitrary partition of the digital map. Accordingly, the map area identifier may be referred to as TILE ID if the map area corresponds to a tile of the digital map or CUBE ID if the map area corresponds to a cube. The map area may include several map objects and features lying within its periphery. Accordingly, the map area content of a map area may include data regarding the map objects and features lying in the map area. For example, the map area content may include data regarding roads, road objects (such as road signs, dividers etc.), points of interest, traffic limits and the like. For example, a system may have a server version of a digital map stored in memory of the system. A user or an application executing on a client device (generally, a client) associated with the system may request for a route between a starting location and a target location. In various embodiments, the route may be determined as an ordered list or set of route segments to be traversed from the server version starting segment to the server version target segment. The route segments may span across one or several map regions. As such, each map area identifier may correspond to one or more segment identifiers. For example, the ordered list or set of route segments may comprise an ordered list of segment identifiers that identify the route segments in the mobile version of the digital map. The route segments of the ordered list or set of route segments define a route segment set. To be able to provide on-the-fly accurate navigation assistance for the requested route, a client device or client application associated with the system needs to have client-side map data equivalent to the server version of the map area content corresponding to each map area identifier. Therefore, the system generates map update data for updating the client-side version of the digital map. For example, the system may receive a