Detecting geographical differencing problems in the context of spatial data dissemination

Abstract

Statistical disclosure control aims neither at revealing the identity of an individual, nor at revealing characteristics of individuals, households or companies that are confidential or personal. Primary statistical secrecy concerns information one can directly assess, whereas secondary statistical secrecy concerns information that a user could deduce indirectly by recombining and crosschecking all the disseminated data.

In the case of spatial data disseminated according to several geographical partitions, it is possible to combine and intersect the geographical areas in order to derive information on new and smaller areas. The differencing technique, which consists in subtracting the value of two overlapping areas, can lead to a breach of confidentiality.

We have developed a method for dealing with geographical differencing problems by detecting individuals located in small overlapping areas and whose personal information can therefore be disclosed. Modelling the data into a graph structure enables focusing on relevant geographical regions. The originality of the method resides in reducing the graph size and complexity. We applied the method to French income tax data composed of 27 million households dispatched on the 150 000 square cells and on the 35 000 administrative units. The results show that 10 000 households are at risk for disclosure.

Keywords

Geo-differencing disclosure control grid data overlapping areas

,88avenueVerdier,92120,Montrouge,France.Tel.:+33680342070;E-mail:vianney.costemalle@insee.fr.

1. Introduction

The French National Institute of Statistics and Economic Studies (Insee) disseminates very small-scale spatial data. For example, statistics on households income and demographic structure are provided both through a regular 200 m-squares grid and through administrative units. There are about 35.000 municipalities in France and the metropolitan territory is covered by 2.3 millions of 200 m square cells. Statistical Disclosure Control (SDC) is, in this context, a major issue since the two datasets, one for municipalities and the other for the regular grid lead to aggregation of the sames variables on different overlapping areas. This could lead to households identification, either directly because the number of households involved in the considered aggregate is below some threshold or indirectly, by linear combination of published aggregates. Broadly speaking, there are two major classes of methods in order to avoid disclosure of confidential information: one, called perturbative methods, consists in adding a random noise or randomly exchanging households characteristics at the level of micro data and then, computing aggregates; the second class of methods consist in identifying and suppressing or aggregating at-risk cells. Usually, SDC adopts some ad-hoc measures of risk of the published information with respect to a given involved household, such as (n,k)-dominance[1]: n or fewer households constitute greater than k percent of the total cell value, for example. In this paper, we adopt a much simpler approach of risk: an aggregate is assumed problematic when the number of households involved is below a conventional threshold. This threshold is a parameter of the algorithm. The paper is centered on indirect SDC in the specific case of spatial differencing.

For this indirect SDC, we need to monitor all possible ways of combining regular grid and municipalities data in order to check where theses combination finally lead to reveal some information about aggregates of households whose size is less than the previously mentioned threshold. The level of the task, while scanning all possible combinations, is completely intractable by a computer: the magnitude of the number of combinations is typically $2^{N}$ , where N is 35.000 for municipalities and 2.3 millions for the 200 m square cells.

Many authors have shown the connection between SDC, linear programming and graph theory in the identification of (indirect) at-risk cells[1, 2, 3, 4, 5], among others, have developed algorithms based on graph theory in order to detect at-risk cells in different contexts. Our work is based on these ideas but applied in the specific context of spatial data where graph theory tracing linear combination of data may be nicely complemented by geographic proximity in order to reduce dramatically the complexity of the detection of at-risk cells.

Because people want to know what is happening locally, there is a growing demand for spatial information. To this end, NSIs will release an increasing quantity of data which are geographically located. Eurostat emphasized “the need to enhance the use of the spatial dimension during the collection, processing and dissemination of statistics has been acknowledged by the EU and its Member States for almost two decades”.

The grid system, consisting of regular, usually square-shaped, cells, has proven useful to disseminate spatial data in a harmonized way and get rid of administrative boundaries. Several NSIs have already released grid data, from census data or business data. It is then expected that confidentiality issues regarding spatial data and grid data in particular will have a growing importance for NSIs. In the context of SDC, geographic information is not like any other information because it is highly identifying information (such as the name or the address). One is expected to know his neighbours better than random people [6]. Moreover, there is an increasing supply of detailed and open geospatial data, such as the ones provided by Open Street Map or Google Earth, which can help identify buildings and dwellings in some given areas. Therefore, some special treatments must be considered when dealing with the confidentiality of spatial data.

To prevent geospatial data from disclosure, perturbation methods, such as targeting record swapping [7, 6], have been explored. But indirect SDC is clearly a much more complicated and significant issue here: by subtracting a zone composed of squares of the grid data to a zone composed of municipalities, one can discover information on an area containing very few statistical observations (households, companies, individuals, etc.). The operation is called geographical differencing.

Duke-Williams and Rees have already developed a method to detect differencing issues, but restraint to a special case, the most simple one, consisting of regions composed of only one area of either of the two zonings. These authors explained that testing differencing on aggregation of areas, and not only on a single area, was “beyond the scope” of their software [8]. It remains very difficult to detect all the differencing issues arising from a database disseminated according to two different, non-nested, zonings. The reason is that the number of regions that can be differenced increases exponentially with the number of geographical areas. The purpose of the work presented in this paper is to provide a framework as well as a method to detect observations which are at risk because of the geographical differencing. It is thus an attempt to bring some new tools to better tackle secrecy hacking in the context of spatial data.

2. The geographical differencing technique, and why the computations may be exponential

2.1 The differencing technique

The differencing technique can be used when the disseminated data are additive, which means that these data can be added together or subtracted from each other. For instance, the population’s total income is additive whereas the median income is not. The principle of the geographical differencing technique is quite simple: it consists in making the difference, on additive data, between the data disseminated in an encompassing area $A$ and the data disseminated in an encompassed area $B$ . One can then deduce the value of the additive variable on the complementary region of B within A, noted $A\backslash B$ and named the differenced area (see Fig. 1). If the differenced area contains less observations than a given confidentiality threshold, privacy is jeopardized. The difficulty of finding regions $A$ and $B$ which leads to a confidentiality issue lies in the fact that regions $A$ and $B$ can be relatively complex in terms of being composed of multiple smaller areas. Differencing technique, if used by an ill-intentioned person, can lead to a breach of statistical confidentiality. Indeed, differencing makes it possible to deduce information on areas smaller than those which were originally planned.

Figure 1.

Diagram of the principle of the geographical differencing. Note: The area $C$ which is the complementary zone of $B$ within $A$ is named the differenced zone. It is the area on which information is derived.

2.2 An example

Lets first consider an educational example. Figure 2a displays a map representing 23 statistical observations located on 4 administrative ( $A1$ , $A2$ , $A3$ and $A4$ ) units and 7 square cells ( $B1$ , $B2$ , $B3$ , $B4$ , $B5$ , $B6$ and $B7$ ). The administrative units and the grid can be seen as two territorial classifications, or zonings, representing two partitions of the same population. For the example the confidentiality threshold is considered to be 3. That is to say every information describing 1 or 2 observations is regarded as unsafe and therefore cannot be released. Each of the 4 administrative units and the 7 cells containing at least three observations, one can disseminate aggregated data according to both zonings (units or cells). In other words, the direct SDC is verified. Now let’s deal with the indirect SDC. In fact, if one makes the difference between the region composed of the areas $A1$ and $A3$ (named $A1-A3$ ) and the region composed of the cells $B1$ , $B2$ , $B4$ and $B6$ (named $B1-B2-B4-B6$ ), he deduces information over two observations (the ones located at the intersection between $B3-B5$ and $A3$ ), which is smaller than the confidentiality threshold (see Fig. 2b). If, for instance, standard of living is disseminated according to the two zonings (by summing up this variable over the areas), one can therefore knows what is the sum of the standard of living of two households. This represents a privacy disclosure according to the confidentiality threshold in force. Here cells have been subtracted to administrative units, but the opposite can also be done by subtracting administrative units to cells. In fact, the two zonings have a symmetrical function. Moreover, for each region composed of administrative units, two kind of differencing are possible:

the internal differencing: cells fully included (in terms of observations) inside the region are subtracted from the region (see Fig. 2b).

the external differencing: the region is subtracted from all the cells intersecting it, those fully included as well as those half included (see Fig. 2c and d).

Figure 2.

Educational example to illustrate the differencing issue.

To be able to discriminate between fully included cells (like $B4$ , $B6$ and $B7$ ) and half included cells (like $B1$ , $B2$ , $B3$ and $B5$ ), a user of the data must know the empty intersections between cells and administrative units. This is where the geographical matter of the problem plays an important role. The user, because he can overlay geospatial data, from Open Street Map or Google Map for instances, to assess were the statistical observations are located (buildings or dwellings). In the example of Fig. 2 three possible geographical differences are presented corresponding to Fig. 2b–d. But there are many other possible differences. On one side, one should check all the differencing, external and internal, related to regions composed of administrative units. And symmetrically on the other side, one should check all the differencing related to regions composed of cells. There are $2^{4}=$ 16 possible combinations of administrative units and $2^{7}=$ 128 possible combinations of cells. But the symmetry of the problem allows us to choose only one side among the two: in this case, it appears more relevant to compute the differences on regions composed of administrative units. This is where the symmetry is broken in the method. Table 1 gives the results of the differencing, internal as well as external, that can be achieved on the 16 combinations of administrative units. Four of these differencing lead to disclosure (regions 3, 7, 10 and 14 in Table 1). But, all those four differencing lead to the same set of two observations (the ones targeted in Fig. 2b). The rest of the paper is devoted to formalize these ideas in order to reduce the number of combinations that have to be checked, going from an intractable problem of $2^{35000}$ possible differencing combinations into a much smaller and tractable one.

Table 1

All the possible differencing, internal and external, related to the example of Fig. 1

Combination	Number of units	A1	A2	A3	A4	Internal difference	External difference	Connected areas
1	0	$-$	$-$	$-$	$-$	0	0	No
2	1	$\bullet$	$-$	$-$	$-$	3	3	Yes
3	1	$-$	$\bullet$	$-$	$-$	5	2	Yes
4	1	$-$	$-$	$\bullet$	$-$	5	8	Yes
5	1	$-$	$-$	$-$	$\bullet$	0	0	Yes
6	2	$\bullet$	$\bullet$	$-$	$-$	8	5	No
7	2	$\bullet$	$-$	$\bullet$	$-$	2	5	Yes
8	2	$\bullet$	$-$	$-$	$\bullet$	3	3	No
9	2	$-$	$\bullet$	$\bullet$	$-$	3	3	Yes
10	2	$-$	$\bullet$	$-$	$\bullet$	5	2	No
11	2	$-$	$-$	$\bullet$	$\bullet$	5	8	No
12	3	$\bullet$	$\bullet$	$\bullet$	$-$	0	0	Yes
13	3	$\bullet$	$\bullet$	$-$	$\bullet$	8	5	No
14	3	$\bullet$	$-$	$\bullet$	$\bullet$	2	5	No
15	3	$-$	$\bullet$	$\bullet$	$\bullet$	3	3	No
16	4	$\bullet$	$\bullet$	$\bullet$	$\bullet$	0	0	No

Note: Each line represents a region on which differencing is applied. A dot $\bullet$ indicates that the units is included in the combination whereas a dash $-$ indicates that it is not part of the combination.

3. A new method for detecting geographical differencing problems

3.1 Modelisation

Lets consider a geocoded database with $n$ statistical observations for which an additive variable is disseminated according to two non-nested territorial classifications (zonings) $M_{A}=\{A_{1},\ldots,A_{N}\}$ and $M_{B}=\{B_{1},\ldots,B_{M}\}$ . The $A_{k}$ and $B_{l}$ are named the elementary zones (one can think of administrative units and square cells). For a given geographic zone $Z$ , we denote $n(Z)$ the number of observations located in $Z$ . Lets $t$ be the confidentiality threshold. Suppose that $N<M$ , so that we considered regions composed of elementary zones of $M_{A}$ instead of regions composed of elementary zones of $M_{B}$ (according to the previous remark on symmetry of the problem). A region $A$ is an area composed of $P$ elementary zones of $M_{A}$ , $A=A_{k_{1}}\cup\ldots\cup A_{k_{P}}$ , where $P\leqslant N$ . The internal region of $A$ is the region of $B$ whose elementary zones are fully included in $A$ . For example the internal region of $A_{1}\cup A_{3}$ in the example of Fig. 2 is the region $B_{\textit{intern}}=B_{1}\cup B_{2}\cup B_{4}\cup B_{6}$ . The external region of $A$ is the region of $B$ whose elementary zones are fully included or half included in $A$ . In Fig. 2, the external region is $B_{\textit{extern}}=B_{1}\cup B_{2}\cup B_{3}\cup B_{4}\cup B_{5}\cup B_{6}$ . Two elementary zones of $M_{A}$ , $A_{k_{1}}$ and $A_{k_{2}}$ , are said connected if there is an elementary zone $B_{l}$ of $M_{B}$ whose observations are both located in $A_{k_{1}}$ and $A_{k_{2}}$ . For instance in Fig. 2, $A_{2}$ and $A_{3}$ are connected through $B_{3}$ or $B_{5}$ , but $A_{2}$ and $A_{4}$ are not connected even if these areas shared a common border. With this definition, connected zones does not necessary shared a common boarder (some big square cells for example can connect non-touching administrative units), but with our data this is most often the case.

By definition, for a given region $A$ , if the internal or external difference is under the threshold but greater or equal to 1 ( $1\leqslant n(A\backslash B_{int})<t$ or $1\leqslant n(A\backslash B_{ext})<t)$ , the statistical observations located in the differenced area are at risk. Our purpose is to detect all statistical observations which are at risk according to this definition. To this end, as it has been noticed on the example, some simplifications can be undertaken in order to reduce the number of combinations. We will now present the method allowing to reduce this number, as well as some mathematical explanations that show the method actually works.

3.2 The connected areas and the graph representation

As we have noticed on example of Fig. 2, some combinations lead to the same subset of at-risk observations (e.g. combinations 3, 7 and 10 and 14 in previous example). In the example, computing the differences on the group $A_{1}-A_{3}$ , $A_{2}-A_{4}$ or $A_{1}-A_{3}-A_{4}$ is useless because it is the same as computing the differences on $A_{2}$ . This is the case because $A_{2}$ and $A_{4}$ are not connected and because $A_{1}-A_{3}$ is the complementary zone of $A_{2}-A_{4}$ .

The first idea is then to restrict the search on encapsulating regions $A$ whose elementary zones $A_{k}$ are connected. Suppose region $A$ has two non-connected sub-regions $A^{1}$ and $A^{2}$ . Lets consider the internal zone $B$ of $A$ . The elementary zones of $B$ are either fully included in $A^{1}$ or fully included in $A^{2}$ (because $A^{1}$ and $A^{2}$ are not connected, none of the elementary zones of $B$ can be half in $A^{1}$ and half in $A^{2}$ ). $B$ can thus be written as $B=B^{1}\cup B^{2}$ where $B^{1}$ is fully included in $A^{1}$ and $B^{2}$ fully included in $A^{2}$ . Therefore, $n(A\backslash B)=n(A^{1}\backslash B^{1})+n(A^{2}\backslash B^{2})$ . So if $1\leqslant n(A\backslash B)<t$ this implies that $0\leqslant n(A^{1}\backslash B^{1})<t$ and $0\leqslant n(A^{2}\backslash B^{2})<t$ and either $n(A^{1}\backslash B^{1})\geqslant 1$ or $n(A^{2}\backslash B^{2})\geqslant 1$ . As a consequence, if one looks for differencing issues according to an increasing size of encapsulating zones, there is no need to compute $n(A\backslash B)$ if $n(A^{1}\backslash B^{1})$ and $n(A^{2}\backslash B^{2})$ have already been computed. According to the orientation of inclusion, if observations are at risk in $A\backslash B$ , there are at risk in $A^{1}\backslash B^{1}$ or in $A^{2}\backslash B^{2}$ . And observations may be at risk in $A^{1}\backslash B^{1}$ or in $A^{2}\backslash B^{2}$ and not in $A\backslash B$ .

With this consideration it is sufficient to check differences on regions whose elementary zones are connected. We can deal more easily with this result by representing the data within a graph structure. The nodes of the graph are the elementary zones of the first zoning $M_{A}$ (the administrative units in our example), and two of these nodes are connected by an edge if the two corresponding zones are connected (see Fig. 3). In this way we can easily know on which encapsulating regions we have to restrain the searches, because these regions correspond to the connected subgraphs 1.

Figure 3.

Graph representation.

To summarize:

each connected subgraph of the graph corresponds to an encapsulating zone which can potentially lead to a differencing problem;

in order to know if there really is a confidentiality issue, the number of observations located in the differenced area, noted $n(A\backslash B)$ , must be computed;

if $1\leqslant n(A\backslash B)<t$ , the observations located on the differenced zone $A\backslash B$ are tagged and said to be “at risk of differencing”.

This approach enables to substantially reduce the number of differences to compute. In our example, it is only necessary to compute 7 differences (corresponding to the 7 connected subgraphs, see Fig. 3b) instead of the initial 16 differences. In many cases the number of connected subgraphs of the initial graph can be too important to check them all. For France, for instance, the graph has 35 000 nodes each having on average 6 neighbours. In that case there are billions of possible subgraphs. For that reason we developed a method which allows to reduce the number of connected subgraphs to test, without missing any observations at risk. It consists of “reducing” the size of the initial graph.

3.3 Reducing the graph

We present two ways of dealing with a large graph for the problem of detecting the connected subgraphs which lead to a differencing problem. The first technique is to merge nodes that we know must be in the same subgraph. By repeating this merging technique as much as possible, it enables the size of the graph (i.e. the number of nodes) to be considerably diminished. The second technique is to split the graph into many components and to consider these components separately. Once again this reduces the number of subgraphs to test.

Figure 4.

Diagram of the part of the graph taht links the node $a_{1}$ to $a_{2}$ . Note: The labels on the edges represent the number of observations located on the intersection between the binding area and the area represented by the source node.

Figure 5.

Diagram of the splitting of the graph. Note: The node $a$ in dark is the only link between the three connected components $G_{1}$ , $G_{2}$ and $G_{3}$ .

Let $A_{1}$ and $A_{2}$ be two connected nodes of the graph, and lets $B_{c}$ be the union of the elementary zones of $M_{B}$ connecting $A_{1}$ and $A_{2}$ . Let $e_{1}$ (reps. $e_{2}$ ) be the number of observations located in the intersection between $A_{1}$ and $B_{c}$ (resp. between $A_{2}$ and $B_{c}$ ). For example, in Fig. 2a if we consider $A_{2}$ and $A_{3}$ , $e_{1}=5$ and $e_{2}=2$ .

If we consider a connected subgraph containing the zone $A_{1}$ but does not contain the zone $A_{2}$ , it implies that the internal differenced area contains the observations that are at the intersection of $A_{1}$ and $B_{c}$ (because $B_{c}$ is not fully included in $A_{1}$ ). As a result, every subgraph containing $A_{1}$ and not containing $A_{2}$ will have at least $e_{1}$ observations in the internal differenced area. Similarly, every subgraph with $A_{2}$ and without $A_{1}$ will have at least $e_{2}$ observations in the internal differenced area.

Consequently, if $e_{1}\geqslant t$ and $e_{2}\geqslant t$ , we know, without any computations, that every subgraph containing one, and only one, of the two nodes $A_{1}$ and $A_{2}$ will not lead to a differencing problem. In others words, it is not necessary to consider $A_{1}$ and $A_{2}$ as two different zones. Thus we can merge these two zones in one, resulting in the merging of the corresponding nodes in the graph. By doing so, we reduce the size of the graph by one.

Moreover, if $e_{1}<t$ (or $e_{2}<t$ ), there is a more subtle way to determine if $A_{1}$ and $A_{2}$ can still be merged. It consists in considering all the other paths that connect $A_{1}$ and $A_{2}$ . A path can be viewed as a succession of connected nodes $\textit{path}=\{A_{1},U_{1},\ldots,U_{h},A_{2}\}$ . We denote by $f_{0}$ the number of observations located in the intersection of $A_{1}$ and the binding region between $A_{1}$ and $U_{1}$ , $f_{i}$ the number of observations between $U_{i}$ and $U_{i+1}$ and $f_{h}$ the number of observations between $U_{h}$ and $A_{2}$ (see Fig. 4). As previously, lets consider a subgraph $g$ containing $A_{1}$ and not containing $A_{2}$ . Because $A_{1}$ is in $g$ and $A_{2}$ is not, there exists a node in path such that it is in $g$ but its successor is not (one can easily see that by a proof by contradiction). The number of observations that are between this node and its successor is one of the $f_{i}$ ’s ( $i$ between $0$ and $h$ ). Thus, we show that for every subgraph containing $A_{1}$ and not containing $A_{2}$ , the internal differencing will lead to infer information on at least $f_{i}+e_{1}$ observations (where $i\in[\!\![0,h]\!\!]$ ). Therefore if $f_{i}\geqslant t-e_{1}$ for all $i$ , and similarly we have the same result with a path from $A_{2}$ to $A_{1}$ , we can then merge $A_{1}$ and $A_{2}$ .

The last idea we developed is to split the resulting reduced graph into several smaller graphs. Lets consider one node $a$ of this graph such that when $a$ is removed, the graph is split into several connected components (meaning that the only link between those components is through the node $a$ ). We note these $p$ components $\{G_{1},\ldots,G_{p}\}$ (see Fig. 5).

Another important fact is that if there is a differencing problem over an area $A$ , symmetrically there is a differencing problem over the complementary region of $A$ , noted $A^{C}$ (see for example Fig. 2b and c). Lets now consider a connected subgraph $g$ containing the node $a$ . Because of the latter result, testing if there is a differencing problem over $g$ is the same as testing if there is a differencing problem over the complementary subgraph of $g$ , denoted $g^{C}$ . This subgraph does not contain the node $a$ . As a consequence, either $g^{C}$ is included into one of the connected components $G_{i}$ , either its nodes are on several $G_{j}$ . In that latter case, $g^{C}$ is not a connected subgraph but is composed of several connected subgraphs each of them included in one of the $G^{j}$ (because the $G^{j}$ are only connected through the node $a$ which is not in $g^{C}$ ). In any case, $g^{C}$ can be viewed as a set of connected subgraphs each of them included in one of the $G_{i}$ ( $i\in[\!\![1,p]\!\!]$ ).

Table 2

Number of differencings which lead to a confidentiality problem, according to the size of the area on which the differencing is done and according to the number of observations the differencing puts at risk

		Number of municipalities composing the area
		1	2–5	6–9	10–49	50–99	100 or more
Nb. of obs. at risk	1	430	231	38	50	3	6
	2–5	623	333	41	52	6	7
	6–10	434	196	30	43	3	4

Figure 6.

Two examples of regions composed of multiple municipalities (colored area) leading to a differencing problem. Note: The figures represent the number of observations at the intersection between grid and municipalities. The bright area containing only 1 observation highlights the differenced area where the observations at risk are located.

Thus, if we test for a differencing problem over all the subgraphs which are included in one of the $G_{i}$ , we will test for all the possibilities. To understand this point, let $g$ be any connected subgraph. If $g$ is included in one of the $G_{i}$ , $g$ has been tested. Otherwise $g$ is spread over multiple $G_{i}$ , and because $g$ is connected it means that $g$ contains the node $a$ . Consequently, in light of what has previously been said, it appears that we tested the complementary of $g$ , so we also tested $g$ . To summarize, it is possible to reduce the number of differencings to compute by:

merging nodes of the graph, and so reducing the size of the graph;

spliting the graph into smaller connected components, and then reducing the number of connected subgraphs to test.

4. Real case study

We apply the proposed method to the case of the French income tax database, in order to detect the households at risk. The database contains information on the 27 million households living in France, including the standard of living which is a confidential variable. These information are disseminated according to an administrative zoning (the 35 000 municipalities) and according to a grid squares resulting from the quadtree method (150 000 cells). The squares size varies between 200 m and 32 km depending on the population density. They are designed in such a way that no cell contains fewer than 11 households, which is the confidentiality threshold for this source. In that case, differencing problems may arise between municipalities and cells. The whole process took 5 h 30 to run. Around 10 000 households at risk have been detected, that is 0.04% of the total number of households. There are 2 530 areas composed of municipalities which can potentially lead to a confidentiality issue when using the differencing technique. The larger area is composed of 345 municipalities, but most of the areas contain few municipalities. Almost 60% of them are composed of one municipality and 95% of fewer than 14 municipalities. Table 2 gives the number of differencing problems according to the number of observations at risk located in the differenced area. For example, 50 regions made up of a number of municipalities between 10 and 49 will give information on only one household. Some very complex regions lead to deduce information on only one household (6 regions made up of more than 100 municipalities – Table 2). Figure 6 gives two examples of differencing problems. Figure 6a shows an area (colored in pink) composed of 5 municipalities. When difference between those 5 municipalities and the inside squares (colored in blue) is computed, one deduces information on the household highlighted in yellow. Figure 6b displays a more complex example of differencing problem involving 16 municipalities.

To allocate one household to a specific cell, the exact location of the household is needed (i.e. the coordinates of the point representing the household). In the case of the French income tax database the coordinates are retrieved through the cadastral plan, using the fact that each household is linked to a specific cadastral plot. The retrieved coordinates may not always match perfectly with the localisation of the house, and in the case of big housing estate, there is only one point representing all the building even if it spread over a large area. Because the grid square cells is computed with those locations, the differencing problems will also arise based on those locations no matter how imperfect they are. The number of households being disseminated according to the two zonings, an external user can precisely know the number of observations in any differenced area. So an external user, even if he doesn’t know the exact locations of the households can assess if a particular difference leads to a breach of confidentiality or not.

An important point is that an external user cannot applied the propose method to detect all the risky households without knowing the exact locations of the households. Nevertheless, it is not impossible to estimate those locations thanks to satellite imagery or open source geographical information. The deduced graph from those estimated locations may not be exactly the same as the proper graph but it can be close enough to allow to target some truly risky households.

5. Conclusion

We developed a new method which can handle complex geographical differencing problems and which is able to run quite rapidly. Nevertheless, our method has some limitations. It is intended to work only on data being disseminated on two, and only two, zonings. It won’t work if the data are disseminated over three or more zonings (even though one can detect observations at risk by considering all the couples of zonings, but it will not ensure that all the risky observations have been detected). Moreover to be applied properly, the method needs some assumptions on the data which are being disseminated. The first assumption is that the same data are disseminated over the two zonings, otherwise it won’t make sense to difference the zonings. If the data are not exactly the same, but are very correlated (for example if a variable X, before being disseminated in the second zoning has been processed in some way), our method is still of use, but it won’t be able to distinguish between the differencings which will lead to infer true information and the differencings which will lead to infer only approximate information (because of the non strict equality of the X’s over the two zonings). Furthermore, differencing can jeopardize statistical secrecy if the data underlying the dissemination of information are comprehensive. If the values disseminated over the different zones are the result of an estimation from a sample, the method cannot determine which differencing will lead to some confidentiality leak. Finally this method does not take other confidentiality risks into account.

It can be argued that pertubative methods such as randomly swapping observations or adding some random noise to the data provide enough protection even for the differencing problems. But this is not so easy to assess. Some perturbative methods add noise only to specific observations that are targeted “at risk” before the data dissemination. If the differencing risk is not taken into account in that global risk, one may not consider that the perturbations are protecting the observations from differencing. So in that case it remains important to target the risky observations because of the differencing technique. Moreover, even if some random noise is adding to all the observations, one cannot infer the level of protection it provides to observations at risk because of differencing. It may be a good enough protection as well as it may be under the security expectations. In any cases, it seems useful to target the observations at risk because of differencing in order to assess their level of protection.

5.1 The diffman R package

An R package, named diffman, has been developed to implement the proposed methodology. The main function of this package takes as an input a database with all the observations with two variables: one indicating in which area of the first zoning the observation belong and the other one indicating the area of the second zoning. The output is a data table with all the risky observations and it indicates the encompassing and encompassed areas leading to the differencing problems. The package is freely available on the CRAN.

Footnotes

Acknowledgments

I wish to express my gratitude to my colleagues from the methodological department at Insee. I especially thank Marc Branchu, Vincent Loonis and Patrick Sillard for their enriching remarks and conversations which helped me to achieve this work. I also thank Arlindo Dos Santos and François Sémécurbe for their C++ code which allows to test all the subgraphs smaller than a given size. I also would like to thank Hicham Abbas for his precious help for the proofreading. Obviously, all the errors in this text are entirely my own.

References

Cox

. Suppression methodology and statistical disclosure control. Journal of the American Statistical Association. 1980; 73(370): 377-385.

Gusfield

. A graph theoretic approach to statistical data security. SIAM Journal on Computing. 1988; 17(3): 552-571.

de Carvalho

Dellaert

Osório

MDS

. Statistical disclosure in two-dimensional tables: General tables. Journal of the American Statistical Association. 1994; 89(428): 1547-1557.

Shlomo

. Statistical disclosure control methods for census frequency tables. International Statistical Review. 2007; 75(2): 199-271.

Roehrig

Padman

Krishnan

Duncan

. Exact and heuristic methods for cell suppression in multi-dimensional linked tables. Journal of the Operational Research Society. 2011; 62(2): 291-304.

Buron

Fontaine

. Confidentiality of spatial data. In: Loonis

de Bellefon

, editors. Handbook of spatial analysis; 2018.

Shlomo

Tudor

Groom

. Data Swapping for Protecting Census Tables. Privacy in statistical databases. 2010; 41-51.

Duke-Williams

Rees

. Can Census Offices publish statistics for more than one small area geography? An analysis of the differencing problem in statistical disclosure. International Journal of Geographical Information Science. 1998; 12(6): 579-605.

of Statistics

AB.

,SSF Guidance material – Protecting privacy for geospatially enabled statistics: geographic differencing, 2015.

10.

Behnisch

Meinel

Tramsen

Diesselmann

. Using Quadtree representations in buildings stock visualization and analysis. Erdkunde. 2013; 67(2): 151-166.

11.

Loonis

de Bellefon

. Handbook of spatial analysis, 2018.

12.

for National Statistics O. In-depth review of developing geospatial information services based on official statistics. United Nations Economic Commission for Europe; 2016; Note on the Conference of European statisticians.

13.

Ruggles

. Differential privacy and census data: Implications for social and economic research. American Economic Association, 2019.

14.

Nations

. Handbook on geographic information systems and digital mapping, 2000.