DECODING A ROUTE ENCODED BY A PROBABILISTIC ENCODING DATA STRUCTURE

A mobile apparatus receives a route response including information identifying a starting location and a target location of a route and an encoding data structure encoding the route. The encoding data structure is a probabilistic data structure configured to not provide false negatives. The mobile apparatus uses the information identifying the starting and target locations to identify a decoded origin traversable map element (TME) and a decoded target TME of the mobile version of the digital map for the route; accesses map information for determining a cost value for TMEs of the digital map, wherein a TME that satisfies the encoding data structure is assigned a minimal cost value; determines a decoded route from the decoded starting TME to the decoded target TME based on the cost value assigned to the TMEs using a cost minimization route determination algorithm; and performs at least one navigation function using the decoded route.