Table Servers Protect Confidentiality in Tabular Data Releases

Here we describe table servers being developed by the National Institute of Statistical Sciences (NISS) that disseminate tabular summaries of statistical data in response to user queries for marginal sub-tables of a large (for example, 40 dimensions with 4 categories each) contingency table containing counts or sums. Table servers evaluate disclosure risk dynamically, in light of previously answered queries.

The query space Q, which contains all 2^K sub-tables of a K-way table, is partially ordered by set inclusion of attributes in sub-tables. The set R(t) of all tables released through some time t contains direct releases in response to queries and indirect releases (previously unreleased children of direct releases); R(t) is specified by the released frontier RF(t) of its maximal elements.

Underlying dynamic release decisions is a risk criterion RC defined on subsets of Q: at all times the system must satisfy RC (R(t)) ≤ a, where a is a risk threshold set by the operators. A typical risk criterion is accuracy of bounds based on R(t) for sensitive (small count) cells in the full table. Bounds can be computed using integer programming methods, but these techniques do not scale to the table sizes under consideration here. There are also exact techniques for special cases. For example, if the released sub-tables constitute the minimal sufficient statistics of a decomposable graphical model [4], then bounds can be expressed as explicit functions of these sub-tables [2].

Whenever an answered query releases previously unreleased information, other queries become unanswerable. Consequently, at t there is an unreleasable set U(t) of sub-tables whose release would be too risky, with an unreleasable frontier UF (t) of its minimal elements.

Release rules determine which requests for unreleased tables will be fulfilled. The simplest is the myopic rule of releasing T at t as long as RC(R(t) T) ≤ a. To prevent the table server from taking excessively large steps, one can allow only tables adding but one attribute to a previously released table to be eligible for release. To prevent a single user (or a set of colluding users) from driving the table server into a region of Q that suits their needs but not those of other users, release rules can be biased against releases that add large numbers of tables to U(t). Rules can also incorporate the value of releasing T [3, 5].

Back to Top

System Design and Prototypes

A prototype table server, written as a Java application, is shown in the accompanying figure. Its principal strength is the engaging (but non-scalable) visualization of Q, which illustrates the underlying abstractions such as releasable and unreleasable frontiers.

A more powerful table server has been written using the Java 2 Enterprise Edition platform, with query processing performed by Java Servlets and risk computations by native executables. This prototype has been tested on a 14-dimensional, 300,000,000-cell, but extremely sparse, table derived from the Current Population Survey.

---

Table servers disseminate tabular summaries of statistical data in response to user queries for marginal sub-tables of a large contingency table containing counts or sums. Table servers evaluate disclosure risk dynamically, in light of previously answered queries.

---

If the requested table lies on or below RF (t), it is provided immediately, ordinarily via downloaded XML (HTML tables and text are alternatives). Releases are governed by the myopic and at most one step away from R(t) rules, and disclosure risk is evaluated in real time. The query history database, with tables for users, queries and the time trajectories of RF (t) and UF (t), is maintained in a MySQL database server. A frontier display facility monitors evolution of RF (t).

The system employs data structures based on hash tables for storing tables and algorithms that exploit sparsity and the fact that R(t) and U(t) are characterized completely by RF (t) and UF (t). The risk criterion is narrowness of cell bounds computed via a generalized shuttle algorithm [1].

Back to Top

Back to Top

Back to Top

Back to top