# An Efficient Approach for LBS Privacy Preservation in Mobile Social Networks
## 5 Algorithm Design
### Filtering Aggregation Protocol  
According to the given security parameters \(th_{k}\) and \(th_{l}\) in a region, when a clustering group has already met the condition \(th_{k}\) but not met \(th_{l}\). If the success of this clustering group (i.e., meet the conditions \(th_{k}\) and \(th_{l}\)) needs to be promoted, the clustering group should make the new users who want to join in the clustering group have different kinds of service category rather than those kinds of service category that the clustering group already has. Therefore, the purpose of our filtering aggregation protocol is to choose new users selectively. There are two reasons for adopting this method: Firstly, it is no use for increasing the success probability of the clustering group when the new users have the same kinds of service category as the clustering group already has, on the contrary, it just increases the load of the clustering group. For example, suppose that the \(th_{k}=8\) and \(th_{l}=5\) in a region, and a clustering group now under the conditions that \(k=8\) and \(l=3\). Assume that the clustering group meets the conditions \(th_{k}\) and \(th_{l}\) finally, \(k=15\) and \(l=5\) may be the final result of the clustering group, which obviously generates more traffic and computation load than the result \(k=10\) and \(l=5\) by using our filtering aggregation protocol. And it is more effective especially when users' kinds of service category in LBS query are similar or even identical under a certain time and space, which will be proved in the Section 6. Secondly, it will influence the global success rate of clustering groups in this region. In the condition of the same \(th_{k}\) and \(th_{l}\), if a clustering group contains too many users, obviously, other clustering groups cannot cluster successfully due to lack of users. From the variety judgment protocol, we can know the number of \(l\) and \(k\) in \(PID_{1}^{CP1}\). Assume that the case is \(k\geq th_{k}\) and \(l<th_{l}\), when a new user \(PID_{new}\) wants to join in \(PID_{1}^{CP1}\). The representative \(PID_{1}^{R}\) firstly gives his \(pk_{1}\) and \(pk_{1}(SL_{i})\) to \(PID_{new}\). Then \(PID_{new}\) uses \(pk_{1}\) to encrypt his kind of service category \(L_{i}^{new}\) and obtains the intermediate result \(pk_{1}^{inter}(SL_{i})=pk_{1}(SL_{i})+pk_{1}(L_{i}^{new})\). Finally, \(PID_{new}\) returns \(pk_{1}^{inter}(SL_{i})\) to \(PID_{1}^{R}\), and \(PID_{1}^{R}\) recalculates the current value of \(NSC\), which is symbolized by \(NSC^{inter}\). If \(NSC^{inter}>NSC\), we know the new user's kind of service category is different from the kinds of service category that \(PID_{1}^{CP1}\) already has, and it is helpful to promote the success of \(PID_{1}^{CP1}\). Therefore, the representative \(PID_{1}^{R}\) allows the new user \(PID_{new}\) to join. Otherwise, \(PID_{1}^{R}\) refuses \(PID_{new}\). Finally, if the current \(l\geq th_{l}\), the clustering process is a success, or else \(PID_{1}^{CP1}\) waits for more new users to join. Algorithm 3 describes the pseudo code of the filtering aggregation protocol. **Security analysis:** It will be explained from two sides in the clustering process. 1. From the perspective of the single newly-joining user who wants to join in \(PID_{1}^{CP1}\): Because \(PID_{1}^{R}\) sends the encrypted result \(pk_{1}(SL_{i})\) to the single newly-joining user \(PID_{new}\), \(PID_{new}\) cannot infer the existing kinds of service category contained in \(PID_{1}^{R}\) unless he can decrypt \(pk_{1}(SL_{i})\). 2. From the perspective of the clustering group: If the user \(PID_{new}\) submits the kind of service category which is different from those kinds of service category that \(PID_{1}^{CP1}\) already has (i.e., \(NSC^{inter}>NSC\)), the representative \(U_{1}\) cannot know the exact kind of service category because of the different \(L_{i}\).