We are experiencing the expanding use of location-based services such as AT&T’s TeleNav GPS Navigator and Intel’s Thing Finder. Existing location-based services have collected a large amount of location data, which has great potential for statistical usage in applications like traffic flow analysis, infrastructure planning, and advertisement dissemination. The key challenge is how to wisely use the data without violating each user’s location privacy concerns. In this article, we first identify a new privacy problem, namely, the inference-route problem, and then present our anonymization algorithms for privacy-preserving trajectory publishing. The experimental results have demonstrated that our approach outperforms the latest related work in terms of both efficiency and effectiveness.