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, said map area having at least one map area identifier and sending, to a data service, a request for at least one categorized link. The method may further include receiving, from the data service, at least one bloom filter, said 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 at least one map area and associating, at least one 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.