# A Search Efficient Privacy-Preserving Location-Sharing Scheme in Mobile Online Social Networks
## 6 Discussion
### Efficiency Analysis
The reason is that user-defined privacy location-sharing system (UDPLS) proposed in paper [10] and our SELS both consider attacks from friends and design corresponding access control policy; that is, \(SNS\) only sends the pseudo-IDs of \(U\)'s friends that meet \(U\)'s privacy-preserving requirements to \(LS\). Therefore, if \(U\) uses the access control policy for preventing the disclosure of privacy among friends in UDPLS and our SELS, the number of pseudo-IDs sent from \(SNS\) in UDPLS and our SELS is bound to be less than that in schemes MobiShare, MLS, and CenLocShare. Through the above analysis, we can deduce that: (1) the time complexity of the schemes that do not consider attacks from friends is usually greater than that of the schemes that do; (2) in terms of the size of the communication traffic between \(SNS\) and \(LS\), the schemes that do not consider attacks from friends are usually bigger than the schemes that do; (3) in terms of the computational cost of \(LS\), the schemes that do not consider attacks from friends are usually bigger than the schemes that do. From Table 2, we know that the number of pseudo-IDs sent from \(SNS\) in UDPLS is \(kf_{1}\) and the number of pseudo-IDs sent from \(SNS\) in our SELS is \(kf_{2}\). Therefore, we can compare \(f_{1}\) and \(f_{2}\) to know the number of pseudo-IDs sent from \(SNS\) by setting \(k\) as a constant. In UDPLS, \(f_{1}\) means the number of \(U\)'s friends who agree to share their locations with \(U\), i.e., \(f_{1}~{}=~{}f-f_{3}\), where \(f\) represents the total number of \(U\)'s friends and \(f_{3}\) represents the number of \(U\)'s friends who do not agree to share their locations with \(U\) in the entire query area of the location-sharing system. In our SELS, \(f_{2}\) indicates the number of \(U\)'s friends who locate in \(U\)'s associated grids and agree to share their locations with \(U\), i.e., \(f_{2}~{}=~{}f-f_{4}-f_{5}\), where \(f_{4}\) represents the number of \(U\)'s friends who are not in \(U\)'s associated grids and \(f_{5}\) means the number of \(U\)'s friends who do not agree to share their locations with \(U\) in \(U\)'s associated grids. With the above description, we can know that: (1) when \(U\)'s associated grids are the entire query area of the location-sharing system, \(f_{4}~{}=~{}0\); and (2) when \(f_{4}~{}=~{}0\) and the number of \(U\)'s friends who do not agree to share their locations with \(U\) is set to be the same constant in UDPLS and SELS (i.e., \(f_{3}~{}=~{}f_{5}\)), then \(f_{1}~{}=~{}f_{2}\). In general, \(U\)'s associated grids are part of the entire query area of the location-sharing system, and the possibility that all \(U\)'s friends are in \(U\)'s associated grids is very small. Thus, it can be concluded that: (1) the time complexity of UDPLS (i.e., \(\mathcal{O}(kf_{1})\)) is usually greater than that of our SELS (i.e., \(\mathcal{O}(kf_{2})\)); (2) in terms of the size of the communication traffic between \(SNS\) and \(LS\), UDPLS is usually bigger than SELS; (3) in terms of the computational cost of \(LS\), UDPLS is usually bigger than SELS. Through the above analysis, we also can summarize that: (1) the time complexity of our scheme is lower than that of other solutions; (2) when \(k\) is set to be a constant, bigger \(f\) (i.e., the number of an issuing user's friends) requires more resources of location-sharing systems (i.e., the size of the communication traffic between \(SNS\) and \(LS\) and the computational cost of \(LS\)).