Efficient Detection and Protection of Information in Cross Tabulated Tables I: Linear Invariant Test

Ming-Yang Kao, Dan Gusfield

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells in the table. A linear combination of suppressed cells is called a linear invariant if the combination has a unique feasible value. Intuitively, the information contained in an invariant is not protected even though the values of the suppressed cells are not disclosed. This paper gives a surprisingly efficient algorithm for testing whether a linear combination of suppressed cells is an invariant. In sequential computation, the algorithm runs in optimal linear time. In parallel computation, the algorithm runs in polylogarithmic time using a polynomial number of processors on a parallel random access machine. The algorithm exploits a linear algebraic structure of directed and undirected cycles in a mixed graph induced by a given table. This new structure also plays a crucial role in subsequent papers on other aspects of detecting and protecting sensitive information in a cross tabulated table.
Original languageEnglish
Pages (from-to)460-476
JournalSIAM Journal on Discrete Mathematics
Volume6
DOIs
StatePublished - Aug 1993

Fingerprint Dive into the research topics of 'Efficient Detection and Protection of Information in Cross Tabulated Tables I: Linear Invariant Test'. Together they form a unique fingerprint.

Cite this