Search

Numerous generalization techniques have been proposed for privacy-preserving data publishing. Most existing techniques, however, implicitly assume that the adversary knows little about the anonymization algorithm adopted by the data publisher. Consequently, they cannot guard against privacy attacks that exploit various characteristics of the anonymization mechanism. This article provides a practical solution to this problem. First, we propose an analytical model for evaluating disclosure risks, when an adversary knows everything in the anonymization process, except the sensitive values. Based on this model, we develop a privacy principle, transparent l-diversity, which ensures privacy protection against such powerful adversaries. We identify three algorithms that achieve transparent l-diversity, and verify their effectiveness and efficiency through extensive experiments with real data. Categories and Subject Descriptors: H.2.8 [Database Management]: Database Applications-Statistical databases General Terms: Theory, Algorithms, Experimentation Additional Key Words and Phrases: Privacy-preserving data publishing, generalization, l-diversity DOI = 10.1145/1735886.1735887

In an uncertain database, every object a is associated with a probability density function, which describes the likelihood that a appears at each position in a multidimensional workspace. This article studies two types of range retrieval fundamental to many analytical tasks. Specifically, a nonfuzzy query returns all the objects that appear in a search region [r.sub.q] with at least a certain probability [t.sub.q]. On the other hand, given an uncertain object q, fuzzy search retrieves the set of objects that are within distance [[epsilon].sub.q] from q with no less than probability [t.sub.q]. The core of our methodology is a novel concept of "probabilistically constrained rectangle", which permits effective pruning/validation of nonqualifying/qualifying data. We develop a new index structure called the U-tree for minimizing the query overhead. Our algorithmic findings are accompanied with a thorough theoretical analysis, which reveals valuable insight into the problem characteristics, and mathematically confirms the efficiency of our solutions. We verify the effectiveness of the proposed techniques with extensive experiments. Categories and Subject Descriptors: H.2.2 [Database Management]: Physical Design--Access Methods; H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval General Terms: Algorithms, Experimentation Additional Key Words and Phrases: Uncertain databases, range search