## 5 System Analysis
### Performance Analysis  
* **Utility:** In the same LBS, the accuracy of the query results is determined by whether or not the user's real location and real query content are submitted to the LBS server. Both REGP and L2P2 submit the user's real location and real query content, and the query results are unaffected. In this paper, although we do not submit the user's real location, we replace the real location with the other historical location in the same second-level grid where the real location is located. The loss in utility is acceptable, and is caused by this replacement. The reason is as follows. In the actual application, the result of the neighbor query is basically around the organization where the real location is located, and the historical location that replaces the real location is located in the same organization as the real location. So there is a small loss in utility. In addition, each query submits the real query content and the dummy query content, so the obtained query results contain the query results of the real query content.
* **Communication overhead:** The communication overhead the presented method primarily includes four aspects: i) The user submits _Area_ to the LBS server. The communication overhead of submitting _Area_ is \(O(1)\). ii) The LBS server sends \(G_{sub}\) to the user. \(G_{sub}\) contains no less than \(s\) different second-level grids, and each second-level grid contains approximately \(n\) records. The communication overhead of sending \(G_{sub}\) is \(O(s\times n)\). iii) The same as the existing methods, each query request submitted to the LBS server by the user contains \(k\) locations and \(k\) query content. This part of the communication overhead is \(O(k)\). iv) Assuming that each query returns \(m\) POI, the LBS server needs to return \(mk\) query results to the user, so the communication overhead of the query results is \(O(k^{\prime}\times m^{b})\). Compared with REGP and L2P2, our method has more communication overhead about _Area_ and \(G_{sub}\), which provides the historical locations for dummy generation.
* **Computational cost:** The computational cost mostly includes three aspects: (i) After receiving _Area_, the LBS server generates a historical location sub-dataset \(G_{sub}\), and the computational cost of this part is \(O(l)\); (ii) the user generates \(k-1\) dummy locations and \(k-1\) dummy query content according to the parameter \(<k,s,l>\), then the computational cost of generating dummies is \(O(k+m)\); (iii) The LBS server calculates and returns \(m\times k\) query results to the user, and the computational cost about query results is \(O(k^{4}\times m^{b})\). In terms of computational cost, our method is approximately equal to REGP and L2P2.
* **Storage overhead:** In this paper, the client stores a historical location sub-dataset \(G_{sub}\) to generate dummies, which contains approximately \(s\times n\) records, so the storage overhead is \(O(s\times n)\). We mainly consider the storage overhead \(G_{sub}\) on the client side. Besides, the LBS server stores the historical location dataset \(G\), which is about 1.6 GB and is negligible relative to the storage space of the server. Similarly, to defend against RSA, REGP needs to obtain and store the PLs on the map. The storage overhead is \(O(r\times r)\), whereas L2P2 does not need additional storage overhead.