Abstract: Abstract: Privacy-preserving location data collection is an important problem that has attracted much research attention. The state-of-the-art for this problem is local differential privacy （LDP）， which has been established as a strong and rigorous privacy scheme for collecting sensitive information from users. However， existing LDP-based solutions are either limited by poor overall result utility or suffer from large deviation between perturbed and true locations. Motivated by this， we propose CFM， an accurate and efficient method for location data collection and analysis. It generates a safe region based on the overall user’s needs， narrowing down the perturbation output domain and thus enhancing data utility. To make the perturbed location as close to the true location as possible， we devise a novel multi-granularity perturbation strategy by exploiting the proximity between locations. The determination of the optimal range with different granularities is challenge， and CFM accomplishes this through analyzing mutual information. Furthermore， the proposed method integrates probability transition matrices with perturbed location distribution information to estimate the true location frequency distribution. Extensive experiments conducted on real-world datasets demonstrate the effectiveness of our proposed method and its advantages over existing solutions.

Key words: Key words: location privacy, frequency estimation, privacy protection, local differential privacy