# An Efficient Approach for LBS Privacy Preservation in Mobile Social Networks
## 1 Introduction
A personalized spatial cloaking scheme named TTcloak was proposed in paper [7], users' location privacy and preference privacy were protected by k-anonymity and l-diversity respectively in Mobile Social Networks. Currently, most of the existing works concerning the LBS query mainly focus on the security of users' privacy with little consideration of service efficiency. Based on k-anonymity and l-diversity, some current research work, such as paper [8], solved the problem that how to calculate the number of l-diversity without a trusted anonymizer server under a distributed architecture. But the algorithm, proposed to protect preference privacy in the clustering process, has a high degree of complexity. The authors [9] mentioned that users' service should be classified to different service categories, but did not consider how to identify the classified service categories, and it is inevitable to incur a huge time cost if using the way of semantic recognition. Therefore, under the system of distributed architecture, how to identify and calculate l-diversity securely and efficiently in the clustering process is still a challenge. As far as we know, there is no research on this problem. Furthermore, in real applications, it is unreasonable to judge the attribute of a user's location in LBS query from a traditional and static  
Figure 1: Privacy preservation by k-anonymity and \(l\)-diversity. viewpoint. For example, restaurants and schools are often seen as sensitive or dense locations because of the dense population from the traditional point of view [5; 9]. However, as we all know, if the time is not for meal or school day, it is unreasonable for restaurants and schools to be classified as sensitive or dense locations. Thus, the schemes based on the static viewpoint are not very practical. In this paper, aiming at addressing the above challenges, we propose service category table based (SCTB) algorithm to improve clustering efficiency while protecting users' preference privacy. Therefore, under the system of distributed architecture, we rigorously explore the calculation procedure of l-diversity in LBS query, and introduce the service category table into our SCTB algorithm to make SCTB algorithm not only suitable for a single request but also for continuous request. Different from previous solutions based on the straightforward static scenario (e.g., a restaurant is unified as sensitive or dense locations), the scheme in this paper focuses on the process of security and efficient clustering from a dynamic and global perspective. The main contributions of this paper are as follows. 1. To overcome the vulnerabilities of preference privacy in LBS query, we introduce the service category table to represent different kinds of preference privacy so that the process of identifying the kinds of l-diversity can be fast, secure, and computationally inexpensive. 2. Unlike previous works that focus on location privacy and preference privacy independently, we firstly study the relationships between \(k\) and 1 in the clustering process. Then based on the relationships, the concepts of relatively dense scenario and relatively sparse scenario from a dynamic perspective are proposed. Finally, according to different scenarios mentioned above, we give the corresponding algorithm to improve the success rate of clustering from a global perspective. 3. We propose service category table based (SCTB) algorithm which includes request aggregation protocol, variety judgment protocol, filtering aggregation protocol, and representative aggregation protocol to reduce the time cost of clustering process and improve the success rate of clustering groups while protecting preference privacy of users. We also study the circumstance when users' preferences in the clustering process have similarities. 4. We carry out extensive simulations to evaluate the performance of our SCTB algorithm.