Anonymisation of geographical distance matrices via Lipschitz embedding

Abstract

Background: Anonymisation of spatially referenced data has received increasing attention in recent years. Whereas the research focus has been on the anonymisation of point locations, the disclosure risk arising from the publishing of inter-point distances and corresponding anonymisation methods have not been studied systematically.

Methods: We propose a new anonymisation method for the release of geographical distances between records of a microdata file--for example patients in a medical database. We discuss a data release scheme in which microdata without coordinates and an additional distance matrix between the corresponding rows of the microdata set are released. In contrast to most other approaches this method preserves small distances better than larger distances. The distances are modified by a variant of Lipschitz embedding.

Results: The effects of the embedding parameters on the risk of data disclosure are evaluated by linkage experiments using simulated data. The results indicate small disclosure risks for appropriate embedding parameters.

Conclusion: The proposed method is useful if published distance information might be misused for the re-identification of records. The method can be used for publishing scientific-use-files and as an additional tool for record-linkage studies.

Fig. 1

Illustration of step 3. The size parameter k is chosen equal to 3 and the elements of the reference sets are sampled at random from the administrative area of the United Kingdom. The coordinate $f_i(p)$ of the point p (black square) with respect to the random reference set $R_i=\{r_{i1},r_{i2},r_{i3}\}$ is given by the minimum distance from p to a point of this reference set. We have $d(p,r_{i1})=308.9$, $d(p,r_{i2})=262.3$ and $d(p,r_{i3})=162.7$, thus $f_i(p)=min\{308.9,262.3,162.7\}=162.7$. All distances are measured in kilometers

Fig. 2

Influence of Lipschitz embedding on two different data analysis tasks. The left plot shows the rate of correct nearest neighbour classifications depending on parameters d and k of the Lipschitz embedding. The right plot shows the Spearman correlation $\mathit{\rho }$ between original and approximated distances for different choices of d and k of all distances in the data files to two fixed points. The black lines refer to a fixed point in the centre of England whereas the grey lines refer to a fixed point in the north of England

Fig. 3

Target (left) and identification file (right) in the first scenario (English hospital data). Each data file consists of 400 geocoded hospitals and the truncated trust code as quasi-identifier. Different colours refer to different trust codes

Fig. 4

Target (left) and identification file (right) in the second scenario (simulated German population data). Each data file consists of 500 geocoded German addresses and sex and age as quasi-identifiers

Fig. 5

Results of the first experiment for $\mathit{\alpha }=0.1$ for the English hospital data

Fig. 6

Results of the first experiment for $\mathit{\alpha }=0.5$ for the English hospital data

Fig. 7

Results of the first experiment for $\mathit{\alpha }=0.9$ for the English hospital data

Fig. 8

Results of the second experiment for $\mathit{\alpha }=0.1$ for the English hospital data

Fig. 9

Results of the second experiment for $\mathit{\alpha }=0.5$ for the English hospital data

Fig. 10

Results of the first experiment for $\mathit{\alpha }=0.1$ for the German population data

Fig. 11

Results of the first experiment for $\mathit{\alpha }=0.5$ for the German population data

Fig. 12

Results of the first experiment for $\mathit{\alpha }=0.9$ for the German population data

Fig. 13

Results of the second experiment for $\mathit{\alpha }=0.1$ for the German population data

Fig. 14

Results of the second experiment for $\mathit{\alpha }=0.5$ for the German population data