• Short Introduction to the sate-of-the-art in statical data protection
  

• Results
  
  • Publications
  • Conference presentations 

Members and partners

Introduction and objectives

Short introduction to the state-of-the-art in statistical tabular data protection and the problems to be solved in the scope of the project.

The safe dissemination of data is one of the main concerns of National Statistical Agencies. The released data can be classified as disaggregated or aggregated. Disaggregated data (a.k.a. microdata or microfiles) consists of files of records, each record providing the values for a set of variables of an individual. Aggregated data (a.k.a. tabular data) is obtained from microdata crossing two or more variables, which results in sets of tables with a likely large number of cells. It must be guaranteed, for both types of data, that no individual information can be derived from the released information. The available methods for this purpose belong to the field of statistical disclosure control. Good introductions to the state-of-the-art in this field can be found in the monographs [ 25, 16].

In the project we first and mainly focus on tabular data protection. Although each cell of the table shows aggregated information for several individuals, there is a risk of disclosing individual data. This is clearly shown in the tables below. Table (a)  gives the average salary for age interval and ZIP code, while table (b) shows the number of individuals for the same variables. If there was only one individual in ZIP code z2 and age interval 51-55, then any external attacker would know the salary of this single person is 40000EUR. For two individuals, either of them could deduce the salary of the other, becoming an internal attacker. Usually, cells showing information about few individuals are considered sensitive, although other rules can be used in practice. Methods for detecting sensitive cells are out of the scope of this project. A recent discussion on sensitivity rules can be found in [ 17, 24].

The above tables show a two-dimensional example. This can be considered the simplest case. However, in practice we must deal with more complex situations, including multidimensional, hierarchical and linked tables. Multidimensional tables are obtained by crossing more than two variables, and they can be individually protected. Hierarchical tables are sets of tables whose variables have a hierarchical relation (e.g., ZIP code and city). In that case, the total or marginal cells of some tables are internal ones for the others. They have to be protected together, to avoid the disclosure of sensitive data. Finally, linked tables are a generalization of the previous situation, where several tables are made from the same microdata, thus sharing information or cells, either hierarchical or not. Again, they have to be protected together. Linked tables can deal with any table dimension, size and structure, and thus include the other situations. Dealing with linked tables is a desired feature of any tabular protection method. Eventually, the final goal would be the protection of the whole set of linked tables that can be produced from some microfiles (e.g., a population census). Clearly, the number of cells involved in that case might be several million, an impractical size for most current tabular protection techniques. The family of protection methods considered in this project deal with linked tables, and can solve real-world large instances in a few seconds. All the above situations can both refer to frequency tables (i.e., cell values are integer and are usually associated to the number of individuals in that cell) or magnitude tables (i.e., cell values are real, and, for instance, they show the mean for some other variable of all the individuals in that cell). In the project we mainly focus on tables of magnitudes. For tables of frequencies the optimitzation procedures to be developed can also be applied and followed by some heuristic post-process.
 

Current methods for tabular data protection can be classified as perturbative (they change the cell values) or nonperturbative (no change is performed). The most widely used nonperturbative method is cell suppression, where some secondary cells are removed to avoid the disclosure of some sensitive primary cells (which are removed as well). That results in a difficult combinatorial optimization problem, which finds the pattern of secondary suppressions that makes the table safe with a minimum number of cells or information loss. Some heuristics for two and three-dimensional tables [ 22 , 2,, 15, 4, 5] and exact methods for two-dimensional and general linked tables [ 18 , 19] have been suggested for the cell suppression problem. The main inconvenience of this approach is that, due to its combinatorial nature, the solution of very large instances (with possibly millions of cells) can result in impractical execution times.

Among the perturbative approaches, one of the techniques that received more attention was rounding . This method rounds cell values to a multiple of a fixed integer rounding base. Controlled rounding is a variant where the additivity of the table is preserved (i.e., rounded marginal values are the sum of the corresponding slice of internal rounded cells). Initially introduced in [ 1], efficient methods could only be developed for two-dimensional tables [ 9 ], possibly with subtotals [ 10]. For three-dimensional tables controlled rounding is an NP-hard problem [20 ]. Several heuristics [ 21] and exact approaches [ 23] were devised, but were only applied to small size tables. The NP-hardness of the approach makes it impractical for large tables, such as the real-world ones to be tested in this project. Moreover, in practice it can be necessary to maintain some (possibly all) of the original total cells, instead of rounding them.

To avoid the above absence of rounding, it was first introduced in [ 14] the controlled tabular adjustment method (CTA). Extensions to CTA have been recently considered for univarite and multivariate statistics [ 11]. Independently, a similar controlled perturbation method with a quadratic objective function was suggested in [ 3]. The resulting quadratic optimization problem is efficiently solved by an interior-point method in [6]. Both approaches find the minimum-distance (or closest) tables to those to be protected, preserving marginal values, if required, as well as any set of additional linear constraints. That means we try to minimize the information loss when delivering the perturbed values.

CTA and the quadratic minimum-distance controlled perturbation are essentially the same method. Both distances can be presented within a unified framework, including a new variant based on the infinity norm. Some of the benefits of presenting those distances under a unified framework are: (1) They can be easily compared. (2) A single general result regarding the disclosure risk of the distances can be developed independently of the objective function of the final formulation. (3) It is possible to combine the different distances in one single objective function [ 7 ].
 

The main features of CTA or minimum-distance controlled perturbation methods are:

• Efficient: real-world large instances can be solved in a few seconds using current linear and quadratic programming technology. For very large instances, specialized linear and quadratic programming tools are needed; this is the main purpose of the project.

• Versatile: they deal with any table or set of tables, and with any additional linear constraint (e.g., preserving the value of total cells).

• Safe: even with partial information, an attacker is not able to reproduce the original data.

• Simple: they have a straightforward derivation and formulation. That is a feature very much appreciated by National Statistical Agencies' staff, which tend to avoid methods based on sophisticated procedures [ 13].

Bibliography

Results

• J. Castro, S. Giessing, Quality Issues of Minimum Distance Controlled Tabular Adjustment, proceedings of the European Conference on Quality in Survey Statistics, available electronically from http://www.statistics.gov.uk/events/q2006/agenda.asp.
• J. Castro, D. Baena Automatic structure detection in constraints of tabular data, Lecture Notes in Computer Science, 4302 (2006), pp. 12-24, eds. J. Domingo-Ferrer and L. Franconi, © Springer.  
• J. Castro and S. Giessing, Testing variants of minimum distance controlled tabular adjustment, in Monographs of Official Statistics. Work session on Statistical Data Confidentiality, Eurostat-Office for Official Publications of the European Communities, Luxembourg, 2006, pp. 333-343. ISBN 92-79-01108-1.
• J. Castro, An interior-point approach for primal block-angular problems, accepted in Computational Optimization and Applications. Previously appeared as Research Report DR 2005/20 Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, 2005.
• J. Castro, A shortest paths heuristic for statistical disclosure control in positive tables, to appear in INFORMS Journal on Computing. Previously appeared as Research Report DR 2004/10 Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, 2004.
• J. Castro, Minimum-distance controlled perturbation methods for large-scale tabular data protection, European Journal of Operational Research, 171 (2006) 39-52. An extended version previously appeared as Research Report DR 2003/14, Dept. of Statistics and Operations Research, Universitat Politècnica de Catalunya, 2003.

• J. Castro, Quadratic interior-point methods in statistical disclosure control , Computational Management Science, 2(2) 2005 107-121.
• J. Castro, A fast network flows heuristic for cell suppression in positive tables, Lecture Notes in Computer Science, 3050 (2004), pp. 136-148. Volume Privacy in Statistical Databases, eds. Josep Domingo-Ferrer and Vicenç Torra, © Springer, ISBN 3-540-22118-2.
• J. Castro, Computational experiments with minimum-distance controlled perturbation methods, Lecture Notes in Computer Science, 3050 (2004), pp. 73-86. Volume Privacy in Statistical Databases, eds. Josep Domingo-Ferrer and Vicenç Torra, © Springer, ISBN 3-540-22118-2.
   

Top
 

Conference presentations
 

• J. Castro and D. Baena, Automatic structure detection in constraints of tabular data, Privacy in Statistical Databases 2006, Roma (Italia), December 2006. Member of Program Committee.  
• J. Cuesta and J. Castro, Quadratic regularizations in an interior-point method based on iterative solvers, Applied Mathematical Programming and Modelling APMOD 2006, Madrid (Spain), June 2006.
• J. Castro and S. Giessing, Quality issues of minimum distance controlled tabular adjustment, European Conference on Quality in Survey Statistics, Cardiff (Wales, UK), April 2006.
• J. Castro and S. Giessing, Testing variants of minimum distance controlled tabular adjustment, UNECE Work Session on Statistical Data Confidentiality, Geneva (Switzerland), November 2005. Invited presentation.
• J. Castro, A fast network flows heuristic for cell suppression in positive tables, Privacy in Statistical Databases, Barcelona (Catalonia), June 2004. Member of Program Committee.
• J. Castro, Computational experiments with minimum-distance controlled perturbation methods, Privacy in Statistical Databases, Barcelona (Catalonia), June 2004. Member of Program Committee.
• J. Castro, Large-scale optimization in statistical tabular data protection, Computational Management Science Conference, Neuchatel (Switzerland), April 2004. Chairman of session: Optimization methods and applications.