CELL SUPPRESSION - DISCLOSURE PROTECTION FOR SENSITIVE TABULAR DATA

When a statistical agency, such as the United States Bureau of the Census, publishes tabular data, it must withhold certain data elements that contain confidential information associated with the data respondents. Cell suppression is a technique commonly used in the publishing of economic data in tabular formats. The sensitive entries, which are called primary suppressions, need to be suppressed. However, the suppression of the primary cells alone still allows one to estimate a range for each of the missing values by considering the published entries. Additional entries in the table must be suppressed to ensure that these ranges are not too narrow. Traditionally, the protection required is defined by an interval centered around the value of each primary suppression. This paper formulates and develops solution techniques for the traditional problem as well as for a relaxation of the problem where sliding protection ranges are allowed. In the relaxed problem, the protection ranges have fixed widths but are free to slide; the only restriction is that each range must contain the value of the primary suppression. We present network flow-based heuristics for both versions of the cell suppression problem and use a lower-bounding procedure to evaluate the performance of the heuristics. Extensive computational results based on real-world and randomly generated tables demonstrate that sliding protection ranges can significantly reduce the total amount of suppressed data, as compared to the traditional suppression scheme. Furthermore, the heuristics produce optimal or near-optimal solutions for real-world problems.