Abstract: The rise of mobile social networks as well as mobile intelligent terminal has generated a lot of spatial-temporal trajectory data, publishing and analyzing such data is essential to improve transportation, to understand the dynamics of the economy in a region, etc. However, it will be a serious threat to the user's privacy, if adversary is able to identify user's identity corresponding to the trajectory. While calculating similarity of trajectories, the existing methods consider only locations proximity of the sampling point in the trajectory, and ignore the dynamic proximity of locations in the trajectory. So the produced trajectory anonymity set has a low utility. To solve this problem, we first present the concept of neighborhood similarity and neighborhood distortion density to fully consider the dynamics proximity of locations in the trajectory, and then propose two algorithms, i.e., trajectory anonymity algorithm based on neighborhood similarity and trajectory anonymity algorithm based on trajectory neighborhood distortion density. The former one only considers the dynamics proximity of locations in the trajectory, while the latter one also reduces information loss of anonymous collection by minimizing neighborhood distortion density during the clustering process. Finally, experimental results on a synthetic data set and a real-life data set demonstrate that our method offers better utility than comparable previous proposals in the literature.