TR-IIS-02-002    PDF format

This paper studies statistical database problems for two-dimensional tables whose regular cells, row sums, column sums and table sums may be suppressed. Using graph-theoretical techniques, we give optimal or efficient algorithms for the query system problem, the adversary problem and the minimum complementary suppression problem. The three problems are considered for the case of protecting a single cell or a sum of cells against exact or interval disclosures in a positive or general table.

Previously, graph-theoretical techniques are known for the three problems when the row, column and table sums are not suppressed, and when the data are being protected against exact disclosures.  This paper provides two generalized graph-theoretical techniques,
which unify previous results, to solve the three statistical database problems
without the above constraints.


KEYWORDS: statistical databases, cell suppression, exact disclosure, interval disclosure, graph theory, complementary suppression.