US Patent 11562168 Clustering for K-anonymity in location trajectory data

An apparatus for providing anonymity in geographic data for probe devices in a geographic region for a location-based service includes at least a database, a clustering calculator and an anonymity controller. The database stores trajectory data based on sequences of sensor measurements of the probe devices. The clustering calculator clusters the trajectory data, according to a first iteration threshold, into clusters each defined by a cluster point and compares distance for a first cluster from the clusters to cluster points of other clusters of the clusters. The clustering calculator selects a second cluster from the clusters based on the comparison of distances and merges the first cluster and the second cluster into a merged cluster. The anonymity controller modifies the trajectory data to provide a predetermined level of anonymity to locations from the trajectory data in response to the merged cluster.