The authors investigate the suitability of the cell suppression by merging (CSM) technique as an SDB (statistical database) protection mechanism, and give various heuristic algorithms for the minimum information loss. They first revise the definition for the information loss when query probabilities are taken into account. This definition reflects the actual utilization of cells in the lattice. The authors then propose a heuristic approach to be used with the CSM technique. This approach tries to minimize the information loss by properly choosing the merging pairs. Experimental results show that, in most cases, the information loss is lower than that of the case in which the query probabilities are not considered. This indicates that the actual information loss under query probabilities is low when the CSM technique is combined with the heuristic approach. It is concluded that the CSM technique is therefore an effective protection mechanism for summary tables. It is also shown that the CSM technique is also applicable in the generalized lattice model as an effective security enforcement mechanism. The authors propose several heuristic approaches to minimize the information loss when this technique is applied.>

A statistical database (SDB) is a database that is used mostly to provide simple summary statistics (e.g., SUM, COUNT, MAX, MEDIAN, etc.) about individuals in the database and that supports statistical data analysis. When SDB users infer protected information in the SDB from responses to queries, we say that the SDB is compromised. Summary tables are tabular representations of summary data. For a given aggregate function and a set of attributes to specify subsets of individuals in the SDB, all possible (primitive) summary tables form a lattice. The SDB security problem in the lattice model is defined as preventing the users to obtain the information that a table element (i.e., cell) is of size one. In this paper, to solve the SDB security problem in the lattice model, we generalize a technique called cell suppression by merging, and analyze its information loss.