# Differential privacy of identity query

I am trying to understand some of the papers that present identity query mechanisms that satisfies differential privacy, for example the compressive mechanism which uses what they call a universal mechanism. What I mean by identity query is: given a dataset the mechanism which returns dataset back with some noise added to it. The problem that I have is how can we define the sensitivity of such a query mechanism, $Q(D)=D$? If we look at neighboring datasets, $D'$, which differs by one entry, the sensitivity is defined as: $$\max(|D-D'|_1) \text{ over all possible } D'$$ But this is confusing because to me this is a nonsensical statement since $D$ and $D'$ are not in the same dimension ($D'$ has one less row than $D$) and we cannot compute the $L_1$ norm. Could you please explain to me what I am missing?

There are two ways to define "neighboring databases" in differential privacy. One version is the one you are thinking of: we start with $D$ which has $n$ data points in it (for example) and we look at $D' \subset D$ with $n - 1$ data points.
The other (and IMHO more common) version is to define $D$ and $D'$ as neighboring if they have the same number of elements and differ in a single element, so: $|D \cap D'| = n-1$ and $|D| = |D'| = n$. This is often written as $d_{H}(D,D') = 1$, where $d_H$ is the Hamming distance between the data sets: the idea being that if $D$ and $D'$ were both bit-vectors then "differing in a a single entry" corresponds to Hamming distance 1.
• well, actually replacing an element in a dataset can be written as a composition of one addition and one removal of a datapoint - hence it seems to hold in general that if algorithm is $(\varepsilon, \delta)$-DP under second adjacency definition (Hamming distance equals 1), it will also be $(\frac{1}{2}\varepsilon, \frac{1}{2}\delta)$ under first adjacency definition. – Dionysis M Jan 21 '20 at 19:06