# A Search Efficient Privacy-Preserving Location-Sharing Scheme in Mobile Online Social Networks
## 6 Discussion
### Efficiency Analysis  
In previous studies such as [6; 10; 11; 12], their schemes also adopted the method of pseudo-IDs to protect the privacy of users' identities. When an issuing user \(U\) sends a request for querying friends' locations, the social network server (\(SNS\)) will send a certain number pseudo-IDs of the user's friends to the location server (\(LS\)), and then \(LS\) will operate the distance comparison function for each pseudo-ID sent from \(SNS\). Therefore, the number of pseudo-IDs sent from \(SNS\) not only can reflect the size of the communication traffic between \(SNS\) and \(LS\), but also can be a measure for the computational cost of \(LS\). Based on the times of operating the distance comparison function (i.e., \(dis(i,j)\)) in \(LS\), we compare the time complexity among our scheme and previous solutions. The comparison results are given in Table 2. Note that the time complexity focuses on the process of querying friends' locations. The time complexity of querying strangers' locations is related to the number of strangers' pseudo-IDs randomly selected by \(SNS\), so we omit it here. In Table 2, \(k\) is the number of pseudo-IDs for each user (i.e., \(PID_{list}\)), and \(f\) is the total number of an issuing user \(U\)'s friends. In addition, MobiShare, MLS, and CenLocShare do not consider attacks from friends (i.e., not consider the disclosure of privacy among friends), which means \(SNS\) has to send all the pseudo-IDs of \(U\)'s friends to \(LS\). However, the number of pseudo-IDs that \(SNS\) sends to \(LS\) is different in MobiShare, MLS, and CenLocShare. In MobiShare and CenLocShare, \(SNS\) directly sends all the pseudo-IDs of \(U\)'s friends to \(LS\), so the number of pseudo-IDs sent from \(SNS\) is \(kf\). In MLS, to prevent the location server side (i.e., \(LS\)) from getting the complete social network relationship of \(U\), the social network server (\(SNS\)) first divides all the pseudo-IDs of \(U\)'s friends into a certain number of subsets and then sends these subsets to multiple location servers separately. Herein, according to scheme MLS, we can assume that the number of subsets is \(w\), a subset is represented by \(S_{i}\) and the number of pseudo-IDs in subset \(S_{i}\) is \(f_{i}\). Therefore, the number of pseudo-IDs sent from \(SNS\) can be represented by \(\sum_{1}^{w}(S_{i}f_{i})\). In the schemes that do not consider attacks from friends, we can conclude that: (1) \(kf\leq\sum_{1}^{w}(S_{i}f_{i})\); and (2) \(kf~{}=~{}\sum_{1}^{w}(S_{i}f_{i})\) when \(w=1\) (i.e., when there is only one set which contains all the pseudo-IDs of \(U\)'s friends). From the above conclusions, it is easy to deduce that: (1) the time complexity of scheme MLS (i.e., \(\mathcal{O}(\sum_{1}^{w}(S_{i}f_{i}))\)) is usually greater than that of scheme MobiShare and CenLocShare (i.e., \(\mathcal{O}(kf)\)); (2) in terms of the size of the communication traffic between \(SNS\) and \(LS\), scheme MLS is usually bigger than MobiShare and CenLocShare; (3) in terms of the computational cost of \(LS\), MLS is usually bigger than MobiShare and CenLocShare. In Table 2, \(f_{1}\) means the number of \(U\)'s friends who agree to share their locations with \(U\)[10], and \(f_{2}\) indicates the number of \(U\)'s friends who locate in \(U\)'s associated grids and agree to share their \begin{table}
\begin{tabular}{c c} \hline \hline
**Scheme** & **Time Complexity** \\ \hline MobiShare [6] & \(\mathcal{O}(kf)\) \\ UDPLS [10] & \(\mathcal{O}(kf_{1})\) \\ MLS [11] & \(\mathcal{O}(\sum_{1}^{w}(S_{i}f_{i}))\) \\ CenLocShare [12] & \(\mathcal{O}(kf)\) \\ SELS (Our scheme) & \(\mathcal{O}(kf_{2})\) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Compared with previous solutions. Figure 7: Stranger query. locations with \(U\). Note that both \(f_{1}\) and \(f_{2}\) are usually not the total number of \(U\)'s friends.