Lowering the cost of anonymization

4.2.4 Accuracy ✿

In this section, we explore the accuracy of our system by running numerical experiments and provide analytical reasoning about the relationship between accuracy and various parameters.

Experimental accuracy

We assess accuracy experimentally using TPC-H [87], an industry standard SQL benchmark. The TPC-H benchmarks contains a dataset schema and queries that are similar to those used by analysts of personal data at real-world organizations. In addition, the queries contain interesting features such as joins and a variety of aggregations. We generate a TPC-H dataset with the default scale factor of $1$ . We treat suppliers or customers as “users”, as appropriate. Our metric for accuracy is median relative error, the same one used in [209]; a smaller median relative error corresponds to higher utility.

We compute the median relative error of 1,000,000 runs for our model over TPC-H Query 1 using three different aggregation functions and $ε = 0.1$ in Table 4.4. We compare our results to 1,000,000 runs of Flex over the same query, and 10,000 runs (due to performance considerations) of PINQ over the same query. To present a fair comparison, we disabled $τ$ -thresholding and compared only one result record to remove the need for $κ$ stability bounding. In addition, each run of the experiment was performed using a function of fixed sensitivity, controlled by supplying the function with a lower bound of $0$ and an upper bound of the value in the $Δ_{u}$ Q1 column. The bounds were fixed to minimize accuracy loss from contribution clamping.

Function	$Δ_{u}$ Q1	Our model	PINQ	Flex
$ε$ -COUNT(*)	$373$	$0.00175$	$0.00179$	$0.0197$
$ε$ -AVG(l_extendedprice)	$100000$	$0.00181$	$0.00181$	¹
$ε$ -MEDIAN(l_extendedprice)	$100000$	$0.00189$	$0.00349$	¹
$ε$ -COUNT(*)	$1$ ²	$0.993$	$4.727 \times 1 0^{- 6}$	$2.70 \times 1 0^{- 5}$

¹ Unsupported functions

² Intentionally incorrect sensitivity to demonstrate contribution bounding

Table 4.4: TPC-H Query 1 errors comparison with others (

ε = 0.1

)

For our experiments with PINQ and Flex, we also set sensitivity to our previously determined $Δ_{u}$ Q1 listed in Table 4.4. The results are close to our model’s results, but because neither PINQ nor Flex can enforce contribution bounds for datasets with multiple contributions per user, incorrectly set sensitivity can result in query results that are not differentially private. Such incorrectly set bounds can be seen in experiments in Johnson et al. [209] and McSherry’s analysis [276], and in the last row of Table 4.4, where PINQ and Flex report errors far below what are required to satisfy the $ε$ -DP predicate.

With correctly set sensitivity bounds our model’s results are comparable to PINQ’s results for count and average. Implementation differences in our median function mean that our error is lower by a factor of 2. Both PINQ and our model outperform Flex’s result for count by around an order of magnitude. We do not report errors for average and median for Flex because Flex does not support those functions.

We also ran our system over a selection of TPC-H queries containing joins, the experimental results are presented in Table 4.5. Similarly, we report the median relative error of 1,000,000 runs for each query using $ε = 0.1$ . We report the impact of $τ$ -thresholding (the ratio of suppressed records), suggesting that our model is $(ε, δ)$ -DP. $δ$ was set with $δ = n^{- ε ln n}$ , where $n$ is the number of distinct users in the underlying dataset: either customers or suppliers, depending on the query.

Query	$Δ_{u}$ Q	$κ$	Experimental error	$τ$ -thresholding rate	$δ$
Q4	$5$	$5$	$0.0339$	$5.40 \times 1 0^{- 5}$	$6.78 \times 1 0^{- 7}$
Q13	$1$	$1$	$0.00677$	$0.309$	$6.78 \times 1 0^{- 7}$
Q16	$1$	$5$	$11.3$ ¹	$0.9999606$	$2.07 \times 1 0^{- 4}$
Q21	$1$	$1$	$1.60$ ¹	$0.999796$	$2.07 \times 1 0^{- 4}$

¹ Results uninterpretable due to high levels of $τ$ -thresholding

Table 4.5: Selected TPC-H join query results (

ε = 0.1

)

Q4 represents how our system behaves when very little $τ$ -thresholding occurs. Q16 and Q21 demonstrate the opposite, both queries exhibit a very large error that differs from the theoretical error due to most partitions being removed by the threshold because of their small user count. Indeed, this is by design: as partition user counts approach 1, the ratio of $τ$ -thresholding approaches ${(1 - δ)}^{1 ∕ κ}$ . Finally, Q13 represents a more typical result, a query containing mostly medium user count partitions with a long tail of lower count partitions. A moderate amount of $τ$ -thresholding occurs which increases error compared to Q4, but the results are still quite accurate.

Impact of parameters on utility

In this section we explore the relationship between utility and various parameters, which must be adjusted to balance privacy and utility [13].

Impact of $ε$

First, let us discuss the effect of $ε$ on the accuracy of the query results. Note that $ε$ is inversely proportional to the Laplace scale parameter used by differentially private aggregators to add noise. Hence, an increase in $ε$ leads to a decrease in utility.

Proposition 30. The median error from Laplace noise of scale $Δ_{u} ∕ ε$ is $\frac{ln (2) Δ_{u}}{ε}$ .

Proof. Let $x$ be the median noise. By symmetry, we have:

\begin{matrix} \frac{1}{4} & = {CDF}_{Laplace} (x) - {CDF}_{Laplace} (0) = (1 - \frac{1}{2} e^{\frac{- x ε}{Δ_{u}}}) - \frac{1}{2} \end{matrix}

and thus:

\begin{matrix} x_{count} & = \frac{ln (2) Δ_{u}}{ε} . \end{matrix}

□

Similarly, the effect of the number of aggregations is straightforward. When a single query contains $N$ aggregations, the privacy budget is split equally among them: each aggregation will satisfy $(ε ∕ N)$ -differential privacy, so the median error degrades inversely with the number of aggregations.

Changing the value of $ε$ also impacts partition selection: recall that the threshold $τ$ was defined in Theorem 12 as

τ = 1 - \frac{κ ln (2 - 2 {(1 - δ)}^{1 ∕ κ})}{ε} .

In particular, if all other parameters are fixed, $τ = Θ (\frac{1}{ε})$ : multiplying $ε$ by two means that we will be able to keep partitions with approximately half as many users.

Impact of $δ$

What is the effect of varying $δ$ for a fixed $ε$ ? This causes the threshold $τ$ to change, which changes the number of records dropped due to thresholding. Similarly, changing $κ$ modifies the number of records dropped due to contribution bounding. We first perform experiments on TPC-H Query 13 with $ε = . 1$ and varying $δ$ to quantify the impact on partitions returned; Figure 4.10 displays the results. The figure shows that as $δ$ increases exponentially, the proportion of partitions thresholded decreases somewhat linearly.

−−−−8765
11110000δP0000.2.3.3.3r824oportions of partitions thresholded — Figure 4.10: Partition thresholding rates on Q13 induced by various $δ$ .

Impact of $κ$

Next, we analyze the effect of $κ$ for a specific artificial query. Consider the following query after rewriting.

SELECT ANON_COUNT(*) 
FROM (SELECT uid, ROW_NUMBER() as rn 
      FROM Table 
      GROUP BY uid, rn) 
TABLESAMPLE RESERVOIR 
    ( $κ$  ROWS PARTITION BY uid)

Listing 4.9: Anonymization query after rewriting, showing the effect of

κ

Suppose that there are $n$ users in the database. Suppose each user appears in a number of partitions distributed according to a fixed probability distribution $θ$ , and call $X_{i}$ the (random) number of partitions in which user $i$ appears. Then the proportion $p_{κ}$ of partitions dropped due to reservoir sampling is:

p_{κ} = \frac{\sum_{i = 1}^{n} max (X_{i} - κ, 0)}{\sum_{i = 1}^{n} X_{i}} .

Figure 4.11 shows the effect of $κ$ on $p_{κ}$ with $n = 1000$ and various distributions $θ$ . All distributions have similar behavior as $κ$ increases, but the median percent error declines at different speeds based on distribution shape.

Normal (μ = 100, σ = 50)
Uniform (on [50,150])
05112000001κM0050....e0002468diDainrarcela(μtiv=e1e0rr0o)r — Figure 4.11: Median relative error induced by $κ$ for various distributions centered at 100.

Finally, we analyze the effect of clamping on accuracy using model input distributions. Since clamping occurs at the $ε$ -DP aggregation level, we focus on input sets that have at most one row per user.

Consider finding ANON_AVG(col, L, U), where there are $n$ values of col uniformly distributed on $[a, b]$ . If the input distribution is symmetric, symmetric clamping will not create bias, so we clamp only one end: consider clamping bounds $L$ and $U$ such that $L = a$ and $a < U < b$ . We analyze expected error since median error is noisier when running experiments, and the behavior of both metrics are similar.

We plot the impact of the upper clamp bound on total expected error for uniform col with $(a, b) = (50, 150)$ in Figure 4.12, using $L = - 200$ , $n = 100$ , and various values of $ε$ . The optimal point on each curve is marked with a circle. To maximize accuracy, overestimating the spread of the input set must be balanced with restricting the sensitivity. Analysis with the other aggregation functions yields similar results.

𝜀 = 0.25

𝜀 = 0.5
681111120000UE00024680...px000000246ppee𝜀rct=celad1m rpelabtoivuenderror — Figure 4.12: Expected relative error depending on the upper clamp bound for a uniform distribution on $[50, 150]$ , using a lower clamp of $- 200$ , $n = 100$ , and various values of $ε$ . We highlight the optimal point on the curve, with the least expected error.

Note that overestimating the spread of the input set creates less error than underestimating it; the curves in Figure 4.12 do not grow very fast after the optimal point. This can be explained analytically: the unclamped expected mean of col is $\frac{a + b}{2}$ ; for col clamped between $L$ and $U$ , it is:

\frac{(2 a U - a^{2} - U^{2})}{2 (b - a)}

so the expected error of the clamped mean is

\frac{{(b - U)}^{2}}{2 (b - a)} .

Compare the expected error to the median noise added by ANON_AVG(col, L, U), which is approximately $\frac{ln (2) (U - L)}{n ε}$ . The clamping error grows quadratically with $b - U$ , while the noise error only grows linearly with $U - L$ . The behavior for other distributions is similar.

LINKPREV LINKUP LINKNEXT