中文摘要：

Mobile devices with global positioning capabilities allow users to retrieve points of interest (POI) in their proximity. Due to the nature of spatial queries, location-based service (LBS) needs the user position in order to process requests. On the other hand, revealing exact user locations to LBS may pinpoint their identities and breach their privacy. Spatial K-anonymity (SKA) exploits the concept of K-anonymity in order to protect the identity of users from location-based attacks. However, existing reciprocal methods rely on a specialized data structure. In contrast, a reciprocal algorithm was proposed using existing spatial index on the user locations. At the same time, an adjusted median splits algorithm was provided. Finally, according to effectiveness (i.e., anonymizing spatial region size) and efficiency (i.e., construction cost), the experimental results verify that the proposed methods have better performance. Moreover, since using employ general-purpose spatial indices, the proposed method supports conventional spatial queries as well.

英文摘要：

Mobile devices with global positioning capabilities allow users to retrieve points of interest （POI） in their proximity. Due to the nature of spatial queries, location-based service （LBS） needs the user position in order to process requests. On the other hand, revealing exact user locations to LBS may pinpoint their identifies and breach their privacy. Spatial K-anonymity （SKA） exploits the concept of K-anonymity in order to protect the identity of users from location-based attacks. However, existing reciprocal methods rely on a specialized data structure. In contrast, a reciprocal algorithm was proposed using existing spatial index on the user locations. At the same time, an adjusted median splits algorithm was provided. Finally, according to etTectiveness （i. e., anonymizing spatial region size） and efficiency （i. e. , construction cost）, the experimental results verify that the proposed methods have better performance. Moreover, since using employ general.purpose spatial indices, the proposed method supports conventional spatial queries as well.