Abstract: Most of the existing methods are realized by temporal and spatial cloaking techniques. However, these cloaking-based methods are disadvantageous due to their high computation loads and long response delays, which lowers service quality. To address these problems, a novel technique, anatomy and reconstruction, was proposed. This technique first partitions the LBS query set into several equivalence classes, making sure that each equivalence class satisfies the given anonymity constraints. Then it reconstructs the LBS queries in each equivalence class according to the predefined strategies separately, and generates a new set of anonymous queries. Considering various privacy requirements, a series of anonymity models were proposed, and a unified anonymization algorithm MBFAA was introduced to realize these models. Experimental results show that the proposed method can effectively implement all the anonymity models.

Key words: k-anonymity, location l-diversity, query m-diversity, anatomy and reconstruction