Neighboring Datasets

Two datasets D and D' are considered neighbors if they differ by the presence or absence of a single record. This is the strictest definition, often called unbounded differential privacy or add/remove adjacency.

• Unbounded DP: D' is created by adding or removing one row from D.
• Bounded DP: D' is created by changing one row in D, keeping the total size constant.
• The choice of adjacency definition directly impacts the sensitivity of queries and the scale of noise required.

A randomized algorithm M satisfies (ε, δ)-differential privacy if for all neighboring datasets D and D', and all subsets of outputs S:

Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D') ∈ S] + δ

This inequality ensures the output distribution is nearly indistinguishable whether or not any single individual opts into the dataset. The ratio of probabilities is bounded by e^ε, limiting the information leakage about any one record.

The global sensitivity of a query f is defined as the maximum difference in its output over all possible neighboring datasets:

Δf = max ||f(D) - f(D')||

• For a counting query, sensitivity is exactly 1 under add/remove adjacency.
• For a sum query over a bounded column [0, B], sensitivity is B.
• Sensitivity directly scales the noise magnitude in the Laplace and Gaussian mechanisms. A higher sensitivity requires more noise to achieve the same privacy guarantee.

The neighboring dataset concept naturally extends to group privacy, which protects coalitions of individuals. If two datasets differ by k records, the privacy guarantee degrades gracefully:

Pr[M(D) ∈ S] ≤ e^(k·ε) · Pr[M(D') ∈ S]

This means a mechanism that is ε-differentially private for a single record provides k·ε privacy for a group of size k. This is a worst-case bound and motivates keeping the per-record privacy budget small when protecting families or organizations.

Neighboring datasets enable a powerful operational interpretation of differential privacy. An adversary trying to distinguish between D and D' from the output of M faces a hypothesis test with:

• False Positive Rate (FPR): α
• False Negative Rate (FNR): β

Under (ε, 0)-DP, the trade-off is bounded by: α + e^ε · β ≥ 1 and e^ε · α + β ≥ 1. This means no attacker can be simultaneously confident and correct in determining whether a specific record was included, providing a concrete, game-based security guarantee.

The most common definition: two datasets D and D' are neighbors if D' can be obtained by adding or removing a single record from D.

• Mechanism: This directly models an individual's choice to opt-in or opt-out of a study.
• Impact on Sensitivity: For a counting query, the sensitivity is exactly 1. The output changes by at most 1 regardless of the dataset size.
• Example: A medical survey where one patient's entire record is either present or absent.

Two datasets are neighbors if one can be derived from the other by replacing a single record with a fixed, arbitrary 'null' or 'zero' record.

• Mechanism: This is functionally equivalent to add/remove for many queries but aligns better with bounded DP where the dataset size is fixed.
• Impact on Sensitivity: For a summation query, the sensitivity is bounded by the maximum possible value of a single record.
• Example: A fixed-size census table where one respondent's income is swapped for a value of $0.

The definition of a 'single record' is flexible and defines the unit of privacy.

• Event-Level: Neighbors differ by a single action or event. Protects individual clicks but not a user's entire behavioral history.
• User-Level: Neighbors differ by the entire contribution of one user. This is a much stronger guarantee requiring higher noise.
• Example: In a messaging app, event-level protects a single message; user-level protects a user's entire message history.

This formalizes the relationship between the two neighboring dataset definitions.

• Unbounded DP: Uses the add/remove definition. The total number of records n is unknown to the adversary.
• Bounded DP: Uses the substitution definition. The adversary knows the exact size n of the dataset.
• Conversion: A mechanism that is (ε, δ)-DP in the unbounded sense is (2ε, 2δ)-DP in the bounded sense, and vice versa.

If two datasets differ by k records, they are k-neighbors. A standard ε-DP guarantee implies kε-group privacy.

• Mechanism: By the composition theorem, protecting a group of size k degrades the privacy parameter linearly.
• Implication: A mechanism with ε=0.1 for individuals provides only ε=1.0 for groups of 10.
• Mitigation: To protect large groups, the base ε must be extremely small, requiring significantly more noise.

A generalization of neighboring datasets for location privacy where the distance between datasets is a geographic radius r.

• Mechanism: Instead of a binary neighbor relation, privacy loss scales with the Euclidean distance between two locations.
• Guarantee: An adversary cannot distinguish the user's true location from any other location within radius r by a factor of e^(εr).
• Example: A ride-sharing app hiding a user's precise pickup point within a 500-meter radius.