HUT: Enabling High-UTility, Batched Queries
under Differential Privacy Protection for Internet-of-Vehicles

Internet-of-Vehicles (IoV) is considered a promising solution to resolve the limited computational power of a single vehicle. IoV centralizes statistics from edge vehicles in a power server for computation. However, the centralizations of these statistics may contain sensitive data, and substantially requires privacy protections in practice [1, 2, 3, 4, 5, 6]. Differential Privacy (DP) [7], as the dominant mechanism for privacy-preserving computation, provides strong guarantees over sensitive data by statistically adding noises. Though DP is a promising solution for the privacy concerns in IoV, directly applying DP for IoV incurs significant challenges in terms of both data utility and effective protection.

We address the key issue behind applying DP for IoV: how to synergistically combine DP with special characteristics of IoV, whose query sequences are usually formed as unbalanced batches in practice. The unique characteristic of IoV is the unbalanced sequence of requests (denoted as batches). These batches are formed due to a practical issue: vehicles require frequent queries of relevant data for in-time decision-makings [8]. Hence, how to strike a balance between privacy protection and data utility is a major challenge for applying DP for IoV [9]. This is because privacy over-protection can cause low data utility.

Prior works aim to balance the tradeoffs between data utility and privacy protection, but fail to address the issues of batches within IoV. [10] introduces Constraint Inference, which applies a constraint on the order of a sorted data set to decrease unnecessary noise; [11] introduces Micro-Aggregation, which uses a fixed-size cluster to cluster data set before adding noise, to reduce the information loss; and [12] introduces K-aggregation, which aggregates small-value data to form new data when the summation of small-value data exceeds a certain threshold. The ignorance prohibits DP to be applied effectively in the context of IoV, which demands new insights for bridging DP with IoV.

We propose HUT, a new algorithm to enable High UTility for DP-enabled protection in the context of IoV. Our key insight is to take advantage of the fact that, the interactions between centralized servers and edge vehicles are usually frequent and fine-grained, which are combined into a series of unbalanced batches. To exploit the characteristic, our key idea is to aggregate local batches and apply Order Constraints, so that information loss from DP protection can be mitigated.

We quantitatively evaluate the effectiveness of HUT against the state-of-the-art DP protection mechanism. Our results show that HUT can provide much lower information loss by 95.69% and simultaneously enable strong mathematically-guaranteed protection of sensitive data. Meanwhile, HUT does not influence the strong guarantee of DP design, which ensures effective protection of sensitive data from users.

We give an overview of our HUT design for ensuring DP protection with high data utility. HUT consists of three steps: 1) we leverage Micro-aggregation and K-means algorithm to group small-value batches together so that we can mitigate the negative effects of uniform DP protection; 2) we deploy Differential Privacy (DP) to preserve the privacy of the pre-processed data; 3) we exploit Order Constraint (OC) to re-sort DP-protected data so that we can achieve high data utility. Figure 1 compares HUT with two other state-of-the-art DP protection methods, and we elaborate the differences in details as follows.

Compared with [11], HUT effectively reduces the sensitivity and variations of small-value data as they are upper bounded by the centroid of the respective cluster. In [11] (shown as ➋ in Figure 1), a fixed-size clustering method is applied and this results in a consistent distance function on a total order relation but incurs large bias on the dataset which has highly uneven data distribution. Such bias on unevenly distributed data could harm the integrity of the dataset, leading to additional information loss. Thus, on the contrary, we leverage the K-means clustering algorithm to perform the clustering to mitigate the bias.

The above-randomized function is commonly realized by adding Laplace Distributed Noise $\epsilon$, which is inversely proportional to the noise magnitude (If $\epsilon$ is smaller, the magnitude of the noise is larger). In HUT, we try out various $\epsilon$ settings to testify the proposed method feasibility in different protection scales.

$\bullet$ Selected Dataset: We use BROOK dataset [14]. BROOK dataset is a multi-modal dataset with facial videos and 11 dimensions of biosignal/contextual data from 34 drivers’ driving experiences. In our experiments, we specifically handcraft a dataset that contains drivers’ facial images and the corresponding vehicle speeds, as a proof-of-concept. Figure 2 demonstrates an example of our handcrafted dataset.

We compare HUT with the state-of-the-art DP algorithms to examine its effectiveness of data utility. Since the average information loss of method ➋ and ➌ in Figure 1 are highly similar under all experiment conditions, we select the overall best performer ➌ to compare its information loss with the information loss of HUT.

The results of the simple query and counting query in different $\epsilon$ values with fixed k clusters and threshold portions are presented in Figure 3 and Figure 4. Both figures prove the effectiveness of Micro-aggregation in increasing SNR for small-value data and mitigating the negative effects of DP protections, in a common setting (simple query) and challenging setting (counting query). For simple query, our method achieves a maximum of 98% (when $\epsilon$=0.008) and a minimum of 79% (when $\epsilon$=0.05) reduction information loss reduction compared to the state-of-the-art, with k=10 and 30% threshold. For the counting query, the max information loss reduction percentage is 65% (when $\epsilon$=0.008) and the minimum percentage is 27% (when $\epsilon$=0.05). We note that when the noise magnitude grows (i.e. $\epsilon$ values decreases), the performance of our algorithm degrades in a simple query, but improves in counting query. The opposite trend in two query settings proves two things: 1) Applying DP on raw data could significantly harm normal data utility, as simple query, a primary indexing operation could cause relatively severe information loss; 2) Aggregation, as one kind of counting operations, could effectively avoid over-protection in extreme conditions, but is less effective when data is not over-protected.

Figure 5 and Figure 6 presents the information loss of simple query and counting query in different K settings, when $\epsilon$ and threshold are fixed at 0.02,35%. We obtain the key observations that an effective choice of the number of clusters for K-mean clustering falls in the range between 5 and 15, which have the optimal information loss reduction. In addition, our empirical study shows that any reasonable threshold values would incur negligible perturbations on the information loss, as different threshold values cause a maximum 1% variance for simple query and 6% for counting query.

Table 1 reports the best percentage of average information loss compared to the state-of-the-art mechanism in both simple query and counting query for each $\epsilon$ value when the number of clusters k and threshold for aggregation varies for each selected $\epsilon$. We believe exploiting the mitigation of DP’s negative effects in different $\epsilon$ settings is essential, as a small scale of $\epsilon$ changes could cause relatively large fluctuations in the information loss.

We present HUT, a new algorithm to enable High UTility for DP-enabled protection in the context of IoV. Our key insight is to take advantage of the fact that, the interactions between centralized servers and edge vehicles are usually frequent and fine-grained, which are combined into a series of unbalanced batches. We evaluate the effectiveness of HUT against the state-of-the-art DP protection mechanism, and the results show that HUT can provide much lower information loss by 95.69% and simultaneously enable strong mathematically-guaranteed protection of sensitive data.

Our future works aim to explore the scalability and robustness of HUT. For scalability, we expect to examine whether HUT can be applied for data with broad range or unevenly distributed datasets; as for robustness, HUT still suffers from the instability of the K-mean clustering method, which can produce query results with relatively large variance. Therefore, we can expect a trade-off between different clustering algorithms, in terms of the robustness of HUT.