A computer-implemented method for reducing a size of at least one incremental update package sent to a navigation device and useable to update a first navigation database stored at the navigation device, the method comprising: for at least one second navigation database comprising multiple navigable road links arranged in clusters, each cluster including road links with similar historic speed profiles, determining a first cluster set associated with the at least one second navigation database at a first time period and a second cluster set associated with the at least one second navigation database at a second time period, wherein the first cluster set and the second cluster set each include a plurality of clusters of road links and each cluster within each cluster set has a name within that cluster set, and wherein the first navigation database stored at the navigation device comprises information from the first time period including the first cluster set; causing a computation of a minimal matching between the first cluster set and the second cluster set, wherein the minimal matching matches each of a plurality of clusters of the first cluster set with a respective cluster of the second cluster set such that the sum of the differences between the two clusters in each matched cluster pair and of penalties assigned to any unmatched clusters is minimized; for each matched cluster pair where the two clusters have different names, causing a renaming of the cluster from the second cluster set so that the two clusters have the same name; causing a creation of at least one incremental update package useable to update the first cluster set in the first navigation database stored at the navigation device to the second cluster set, wherein the at least one incremental update package is created using the first and second cluster sets with the renamed clusters so that it comprises a minimal number of update, deletion and addition operations required to transform the first cluster set into the second cluster set, thus allowing for a smaller update package size than with the originally-named clusters; and sending the at least one incremental update package to the navigation device. for at least one second navigation database comprising multiple navigable road links arranged in clusters, each cluster including road links with similar historic speed profiles, determining a first cluster set associated with the at least one second navigation database at a first time period and a second cluster set associated with the at least one second navigation database at a second time period, wherein the first cluster set and the second cluster set each include a plurality of clusters of road links and each cluster within each cluster set has a name within that cluster set, and wherein the first navigation database stored at the navigation device comprises information from the first time period including the first cluster set; causing a computation of a minimal matching between the first cluster set and the second cluster set, wherein the minimal matching matches each of a plurality of clusters of the first cluster set with a respective cluster of the second cluster set such that the sum of the differences between the two clusters in each matched cluster pair and of penalties assigned to any unmatched clusters is minimized; for each matched cluster pair where the two clusters have different names, causing a renaming of the cluster from the second cluster set so that the two clusters have the same name; causing a creation of at least one incremental update package useable to update the first cluster set in the first navigation database stored at the navigation device to the second cluster set, wherein the at least one incremental update package is created using the first and second cluster sets with the renamed clusters so that it comprises a minimal number of update, deletion and addition operations required to transform the first cluster set into the second cluster set, thus allowing for a smaller update package size than with the originally-named clusters; and sending the at least one incremental update package to the navigation device.