Databases Reference
In-Depth Information
row #
Age Sex Zipcode Group-ID
1 23 M 11000 1
2 27 M 13000 1
3 35 M 59000 1
4 59 M 12000 1
5 61 F 54000 2
6 65 F 25000 2
7 65 F 25000 2
8 70 F 30000 2
(a) The quasi-identifier table (QIT)
Group-ID Disease Count
1 dyspepsia 2
1 pneumonia 2
2 bronchitis 1
2 flu 2
2 gastritis 1
(b) The sensitive table (ST)
Table 4.
The anatomized tables
in a new column
Group-ID
. However, QIT does not store any
Disease
value.
Finally, we produce the ST (Table 4b), which retains the
Disease
statistics
of each QI-group. For instance, the first two records of the ST (to avoid
confusion, we use 'record', instead of 'tuple', for the data of an ST) indicate
that, two tuples of the first QI-group are associated with dyspepsia, and two
with pneumonia. Similarly, the next three records imply that, the second
QI-group has a tuple associated with bronchitis, two with flu, and one with
gastritis.
Anatomy preserves privacy because the QIT does not indicate the sensi-
tive value of any tuple, which must be randomly guessed from the ST. To
explain this, consider again the adversary who has the age 23 and zipcode
11000 of Bob. Hence, from the QIT (Table 4a), the adversary knows that tu-
ple 1 belongs to Bob, but does not obtain any information about his disease
so far. Instead, s/he gets the id 1 of the QI-group containing tuple 1. Judging
from the ST (Table 4b), the adversary realizes that, among the 4 tuples in
QI-group 1, 50% of them are associated with dyspepsia (or pneumonia) in the
microdata. Note that s/he does not gain any additional hints, regarding the
exact diseases carried by these tuples. Hence, s/he arrives at the conclusion
that Bob could have contracted dyspepsia (or pneumonia) with 50% proba-
bility. This is the same conjecture obtainable from the generalized Table 3b,
as mentioned earlier.
By announcing the QI values directly, anatomy permits more effective
analysis than generalization. Given query A in Section 4.1, we know, from the
ST (Table 4b), that 2 tuples carry pneumonia in the microdata, and they are
