Users are vulnerable to privacy risks when providing their location information to location-based services (LBS). Existing work sacrifices the quality of LBS by degrading spatial and temporal accuracy for ensuring user privacy. In this paper, we propose a novel approach, Complete Bipartite Anonymity (CBA), aiming to achieve both user privacy and quality of service. The theoretical basis of CBA is that: if the bipartite graph of k nearby users’ paths can be transformed into a complete bipartite graph, then these users achieve k-anonymity since the set of “end points connecting to a specific start point in a graph”is an equivalence class. To achieve CBA, we design a Collaborative Path Confusion (CPC) protocol which enables nearby users to discover and authenticate each other without knowing their real identities or accurate locations, predict the encounter location using users’ moving patt information, and generate fake traces obfuscating the real ones. We evaluate CBA using a real-world dataset, and compare its privacy performance with existing path confusion approach. The results show that CBA enhances location privacy by increasing the chance for a user confusing his/her path with others by 4 to 16 times in low user density areas. We also demonstrate that CBA is secure under the trace identification attack.