Privacy Preserving Datamining on Vertically Partitioned Databases

It trusted database administrator monitors queries and introduces noise to
the responses with the goal of maintaining data privacy. Under a rigorous 
definition of breach of privacy, it proved that the total number of queries
is sub-linear in the size of the database, a substantial amount of noise is
required to avoid a breach, rendering the database almost useless.

The positive datamining results in the extensions to the model of described
while maintaining the strengthened privacy requirement :

1. Multi-attribute SuLQ databases : The statistics for every k-ary Boolean func-
tion can be learned. Since the queries here are powerful (any function), it is
not surprising that statistics for any function can be learned. The strength
of the result is that statistics are learned while maintaining privacy.

2. Multiple single-attribute SuLQ databases : It how to learn the statistics
of any 2-ary Boolean function. For example, we can learn the fraction of
records having neither attribute 1 nor attribute 2, or the conditional proba-
bility of having attribute 2 given that one has attribute 1.

3. Vertically Partitioned k-attribute SuLQ Databases : The constructions here
are a combination of the results for the first two cases: the k attributes are
partitioned into (possibly overlapping) sets of size k1 and k2, respectively,
where k1 +k2 >= k; each of the two sets of attributes is managed by a multi-
attribute SuLQ database.

A single-attribute database can be simulated in all of the above settings; hence, 
in order to preserve privacy, the sub-linear upper bound on queries must be enforced.
How this bound is enforced is beyond the scope of this work.

Data mining on Published Statistics : Our technique for testing implication in
probability yields surprising results in the real life model in which confidential
information is gathered by a trusted party, such as the census bureau, who pub-
lishes aggregate statistics.

, , , , , , , ,

  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: