Exact and heuristic methods for cell suppression in multi-dimensional linked tables

Abstract

The increasing demand for information, coupled with the increasing capability of computer systems, has compelled information providers to reassess their procedures for preventing disclosure of confidential information. This paper considers the problem of protecting an unpublished, sensitive table by suppressing cells in related, published tables. A conventional integer programming technique for two-dimensional tables is extended to find an optimal suppression set for the public tables. This can be used to protect the confidentiality of sensitive data in three- and higher-dimensional tables. More importantly, heuristics that are intimately related to the structure of the problem are also presented to mitigate the computational difficulty of the integer program. An example is drawn from healthcare management. Data tables are randomly generated to assess the computational time/space restrictions of the IP model, and to evaluate the heuristics.

Keywords:

• privacy
• confidentiality
• heuristics
• inferential disclosure
• cell suppression
• tabu search

Acknowledgements

This research was supported in part by the National Science Foundation, NSF IRI-9312143, and by the US Army Research Office under Grant DAAH04-94-6-0239. We thank Anthony Colatrella for invaluable help in programming the heuristics and collecting the statistics presented here.