Total protection of analytic invariant information in cross tabulated tables

Ming Yang Kao*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

To protect sensitive information in a cross tabulated table, it is a common practice to suppress 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 lineartime 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)
Title of host publicationSTACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
EditorsErnst W. Mayr, Klaus W. Wagner, Patrice Enjalbert
PublisherSpringer Verlag
Pages723-734
Number of pages12
ISBN (Print)9783540577850
StatePublished - Jan 1 1994
EventProceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) - Caen, Fr
Duration: Feb 24 1994Feb 26 1994

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume775 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherProceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94)
CityCaen, Fr
Period2/24/942/26/94

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(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