Total protection of analytic-invariant information in cross-tabulated tables

Ming Yang Kao*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

To protect sensitive information in a cross-tabulated table, it is a common practice to supress some of the cells in the table. An analytic invariant is a power series in terms of the suppressed cells that has a unique feasible value and a convergence radius equal to +∞. Intuitively, the information contained in an invariant is not protected even though the values of the suppressed cells are not disclosed. This paper gives an optimal linear-time algorithm for testing whether there exist nontrivial analytic invariants in terms of the suppressed cells in a given set of suppressed cells. This paper also presents NP-completeness results and an almost linear-time algorithm for the problem of suppressing the minimum number of cells in addition to the sensitive ones so that the resulting table does not leak analytic-invariant information about a given set of suppressed cells.

Original languageEnglish (US)
Pages (from-to)231-242
Number of pages12
JournalSIAM Journal on Computing
Volume26
Issue number1
DOIs
StatePublished - Feb 1997

Keywords

  • Analytic invariants
  • Data security
  • Graph augmentation
  • Mathematical analysis
  • Mixed graph connectivity
  • Statistical tables

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Total protection of analytic-invariant information in cross-tabulated tables'. Together they form a unique fingerprint.

Cite this