Trading Optimality for Performance in Location Privacy
This work addresses performance bottlenecks for location-based services, offering a more scalable solution for privacy protection, though it is incremental as it builds on existing probabilistic methods.
The paper tackles the computational infeasibility of optimal location privacy mechanisms by reducing constraints from O(n^3) to O(n^2), sacrificing perfect optimality but showing acceptable utility loss and significant performance gains in practical scenarios.
Location-Based Services (LBSs) provide invaluable aid in the everyday activities of many individuals, however they also pose serious threats to the user' privacy. There is, therefore, a growing interest in the development of mechanisms to protect location privacy during the use of LBSs. Nowadays, the most popular methods are probabilistic, and the so-called optimal method achieves an optimal trade-off between privacy and utility by using linear optimization techniques. Unfortunately, due to the complexity of linear programming, the method is unfeasible for a large number n of locations, because the constraints are $O(n^3)$. In this paper, we propose a technique to reduce the number of constraints to $O(n^2)$, at the price of renouncing to perfect optimality. We show however that on practical situations the utility loss is quite acceptable, while the gain in performance is significant.