An apparatus, a method and a computer program product are provided for updating link information on a client device. The method may include determining at least one map area comprising one or more links, the map area having at least one map area identifier, Sending to a data service, a request for at least one categorized link. Receiving, from the data service, at least one bloom filter, the at least one bloom filter encoding the at least one categorized link, determining one or more link identifiers for the one or more links in the map area and associating candidate link of the one or more links to the at least one categorized link, based on the link identifier of the at least one candidate link satisfying the at least one received bloom filter, to update the link information on the client device.