Sanitization of Call Detail Records via Differentially-private Summaries

Mohammad Alaggan, Sébastien Gambs, Stan Matwin, Eriko Souza, Mohammed Tuhin

TL;DR

This paper introduces a novel method for sanitizing Call Detail Records (CDRs) by summarizing them into differentially-private Bloom filters. This allows for the analysis of human mobility patterns while protecting individual privacy, achieving utility comparable to non-private methods.

What Problem Does This Paper Address?

Call Detail Records (CDRs) are a rich source of information for understanding human mobility, which can be invaluable for urban planning, disease spread modeling, and other societal benefits. However, CDRs contain sensitive location data that can easily lead to the re-identification of individuals, posing significant privacy risks. Existing anonymization techniques are often insufficient, and directly publishing CDRs is not feasible. The challenge is to extract meaningful mobility insights from CDRs without compromising individual privacy.

Methods

The core of this paper's contribution lies in its novel approach to sanitizing CDRs. Instead of directly publishing raw or anonymized CDRs, the authors propose summarizing them into differentially-private Bloom filters.

Here's a breakdown of their method:

  • Bloom Filters for Summarization: Bloom filters are used as a compact data structure to represent the set of users present in a particular geographic area (e.g., served by a cellular tower) during a given time period. The advantage of Bloom filters is their space efficiency and ability to handle updates incrementally.
  • BLIP for Differential Privacy: To ensure privacy, the Bloom filters are then "flipped" using the BLIP (Bloom-then-Flip) mechanism. This involves randomly flipping bits in the Bloom filter with a certain probability, which is directly tied to the privacy parameter ($\epsilon$). This process ensures that an adversary cannot easily determine the presence or absence of a specific user in the original set by observing the flipped Bloom filter.
  • Private Intersection Computation: The paper extends existing work on estimating set intersections from Bloom filters to the differentially-private setting. They propose a method to compute the size of the intersection between two differentially-private Bloom filters, which is crucial for understanding movement patterns between different regions. This involves a novel estimator derived from the inner product of the flipped Bloom filters.
  • Extension to Three Sets: The authors also propose a method for estimating the intersection of three sets using flipped Bloom filters, leveraging random forest regression.

What's new here is the combination of differentially-private Bloom filters with techniques for estimating set intersections, specifically addressing the privacy concerns of CDR analysis.

Datasets

The authors evaluated their approach using:

  • A real-life CDR dataset: This dataset was obtained from a phone operator and provided coarse-grained location data (up to district level) and call times (up to 10-minute granularity).
  • Synthetic data: While not explicitly detailed as a separate benchmark, the paper mentions experiments with synthetic data to complement their findings.

Key Insights and Ideas

  • Privacy-Utility Trade-off is Manageable: The paper demonstrates that it's possible to achieve a good balance between strong privacy guarantees (differential privacy) and the utility of the data for mobility analysis.
  • Bloom Filters are Surprisingly Robust for Privacy: Even with the inherent possibility of false positives in Bloom filters, the addition of differential privacy through BLIP allows for meaningful privacy-preserving summarization.
  • Intersection Estimation is Key for Mobility: The ability to privately estimate the intersection of user sets between different regions is a fundamental building block for understanding movement patterns and is a core contribution of this work.
  • Small Datasets/Intersections Require More Privacy Budget: The experiments highlight that when dealing with smaller user sets or smaller intersections between regions, a higher privacy budget (lower $\epsilon$) is needed to maintain accuracy, suggesting that privacy protection comes at a cost in these scenarios.

Key Results

  • Comparable Utility to Non-Private Methods: In most cases, the proposed differentially-private method achieved a Mean Relative Error (MRE) comparable to a non-private Linear Counting Sketch (LCS) for estimating set intersections.
  • Accuracy Varies with Data Characteristics: For large districts or large intersections, the MRE was consistently low (under 12%). However, for small districts or small intersections, the MRE was higher, indicating a greater impact of privacy on utility in these cases.
  • Privacy Parameter ($\epsilon$) Impact: Lower privacy guarantees (higher $\epsilon$) generally led to better utility (lower MRE), as expected. For instance, with $\epsilon = 11$, utility improved compared to $\epsilon = 3$.
  • Neighboring Districts Show High Accuracy: When analyzing neighboring districts with naturally higher intersections, the method demonstrated very accurate results, with MREs ranging from 20% to 40% and standard deviations below 0.04 for $\epsilon = 3$.
  • Intersection of Three Sets: The method for estimating the intersection of three sets also showed promising results, with an MRE of 0.53 (median 0.26) for $\epsilon = 3$.

Limitations and Future Work

  • Higher Error for Small Datasets/Intersections: The authors acknowledge that the utility (accuracy) of their method is lower for small districts or small intersections. They attribute this to the fundamental nature of differential privacy, which limits the information contributed by individual users, making it harder to preserve privacy while maintaining high accuracy in sparse data scenarios.
  • Future Work:
    • More Complex Data Mining Tasks: Extending the differentially-private summary approach to support more sophisticated data mining operations beyond intersection estimation, such as trajectory analysis and mobility model building.
  • Social Aspect Integration: Developing new data structures that can capture social ties and relationships from CDRs while preserving privacy.
  • Application to Gathering Prediction: Investigating the use of these differentially-private summaries for tasks like predicting people's gatherings, as mentioned in the application section.

Summary updated

Abstract

In this work, we initiate the study of human mobility from sanitized call detail records (CDRs). Such data can be extremely valuable to solve important societal issues such as the improvement of urban transportation or the understanding on the spread of diseases. One of the fundamental building block for such study is the computation of mobility patterns summarizing how individuals move during a given period from one area e.g., cellular tower or administrative district) to another. However, such knowledge cannot be published directly as it has been demonstrated that the access to this type of data enable the (re-)identification of individuals. To answer this issue and to foster the development of such applications in a privacy-preserving manner, we propose in this paper a novel approach in which CDRs are summarized under the form of a differentially-private Bloom filter for the purpose of privately counting the number of mobile service users moving from one area (region) to another in a given time frame. Our sanitization method is both time and space efficient, and ensures differential privacy while solving the shortcomings of a solution recently proposed to this problem. We also report on experiments conducted with the proposed solution using a real life CDRs dataset. The results obtained show that our method achieves - in most cases - a performance similar to another method (linear counting sketch) that does not provide any privacy guarantees. Thus, we conclude that our method maintains a high utility while providing strong privacy guarantees.
BibTeX
@misc{alaggan2014sanitization,
  author = {Mohammad Alaggan and Sébastien Gambs and Stan Matwin and Eriko Souza and Mohammed Tuhin},
  title = {{Sanitization of Call Detail Records via Differentially-private Summaries}},
  year = {2014},
  eprint = {1412.8412},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1412.8412},
}
Figure