Privacy Preservation for Location-Based Services Based on Attribute Visibility

Masanori Mano, Xi Guo, Tingting Dong, Yoshiharu IshikawaIMMoA 2012 · OpenReview

Introduction

In the landscape of location-based services (LBS), users frequently exchange personal data—such as location, age, and interests—for targeted benefits like mobile advertisements. While traditional privacy mechanisms like $k$-anonymity and spatial cloaking aim to hide a user within a digital crowd, they often overlook the physical reality of the user's environment. This paper introduces the concept of "attribute observability" to address the risk of visual identification in physical spaces.

The Visual Identification Gap

Existing anonymization methods treat all data attributes equally, failing to account for traits that are easily observable in the real world. For instance, if a system groups several users together to mask their identities, but only one user in that physical location matches a specific visible attribute (like being significantly older than the others), an adversary can easily link the data to the individual through simple observation.

Figure 2: An illustration of visual identification risk where a user with a distinct age attribute (u4, age 38) stands out among a group of younger peers.

As shown in the figure above, even if a group of five users is formed, the outlier in age ($u_4$) remains vulnerable to identification by a malicious observer who can see the physical crowd.

Methodology: Attribute Observability and Taxonomy

To mitigate this risk, the authors propose a framework mediated by a trusted "matchmaker." This system calculates the probability of a user being identified based on the "observability" of their traits. Central to this approach is an attribute taxonomy that allows for varying levels of data generalization.

Figure 4: A hierarchical taxonomy for the 'age' attribute, allowing data to be generalized from specific ranges to broader categories to preserve privacy.

Users define their own "disclosure level" and an "identification probability threshold." The system then attempts to form groups where every member's risk of being visually identified remains below their personal threshold. This personalized approach ensures that privacy is maintained without unnecessarily degrading service quality for less risk-averse users.

Grouping Strategies and Performance

The researchers evaluated several strategies for forming these privacy-preserving groups:

  • Naive: Outputs a group immediately upon meeting the minimum criteria.
  • Deadline-based: Waits to see if more optimal groups can be formed before a request expires.
  • Lazy: Delays grouping until the last possible moment to maximize the potential for high-quality clusters.

Experimental results using both synthetic and real-world road network data from Oldenburg revealed a significant trade-off between complexity and throughput. While sophisticated strategies like "Many-first" attempted to find the best possible matches, they suffered from computational delays under heavy traffic (50–100 requests per second). In contrast, the Lazy strategy emerged as the most effective, providing a robust balance between maintaining high data detail for advertisers and ensuring timely delivery for users.

Conclusion

By bridging the gap between digital anonymity and physical observability, this research highlights a critical vulnerability in traditional LBS privacy models. While strict privacy requirements remain a challenge in high-traffic scenarios, the introduction of attribute-based visibility provides a more realistic and personalized framework for protecting users in the physical world. Future work will focus on optimizing these algorithms to handle even denser traffic and more stringent privacy thresholds.

Summary updated

BibTeX
@inproceedings{mano2012privacy,
  author = {Masanori Mano and Xi Guo and Tingting Dong and Yoshiharu Ishikawa},
  title = {{Privacy Preservation for Location-Based Services Based on Attribute Visibility}},
  booktitle = {IMMoA},
  year = {2012},
  url = {https://openreview.net/forum?id=73FxdinayZez},
}
Figure