ρ-uncertainty
Authors:
Open Access
- 1 September 2010
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 3 (1-2) , 1033-1044
Abstract
The publication of transaction data, such as market basket data, medical records, and query logs, serves the public benefit. Mining such data allows for the derivation of association rules that connect certain items to others with measurable confidence. Still, this type of data analysis poses a privacy threat; an adversary having partial information on a person's behavior may confidently associate that person to an item deemed to be sensitive . Ideally, an anonymization of such data should lead to an inference-proof version that prevents the association of individuals to sensitive items, while otherwise allowing for truthful associations to be derived. Original approaches to this problem were based on value perturbation , damaging data integrity. Recently, value generalization has been proposed as an alternative; still, approaches based on it have assumed either that all items are equally sensitive, or that some are sensitive and can be known to an adversary only by association, while others are non-sensitive and can be known directly. Yet in reality there is a distinction between sensitive and non-sensitive items, but an adversary may possess information on any of them. Most critically, no antecedent method aims at a clear inference-proof privacy guarantee. In this paper, we propose ρ-uncertainty, the first , to our knowledge, privacy concept that inherently safeguards against sensitive associations without constraining the nature of an adversary's knowledge and without falsifying data. The problem of achieving ρ-uncertainty with low information loss is challenging because it is natural . A trivial solution is to suppress all sensitive items. We develop more sophisticated schemes. In a broad experimental study, we show that the problem is solved non-trivially by a technique that combines generalization and suppression, which also achieves favorable results compared to a baseline perturbation-based scheme.Keywords
This publication has 25 references indexed in Scilit:
- Anonymization of set-valued data via top-down, local generalizationProceedings of the VLDB Endowment, 2009
- A framework for efficient data anonymization under privacy and accuracy constraintsACM Transactions on Database Systems, 2009
- FRAPP: a framework for high-accuracy privacy-preserving miningData Mining and Knowledge Discovery, 2008
- L -diversityACM Transactions on Knowledge Discovery From Data, 2007
- Association rule hidingIEEE Transactions on Knowledge and Data Engineering, 2004
- Using unknowns to prevent discovery of association rulesACM SIGMOD Record, 2001
- Hiding Association Rules by Using Confidence and Support2001
- Protecting respondents identities in microdata releaseIEEE Transactions on Knowledge and Data Engineering, 2001
- Scalable algorithms for association miningIEEE Transactions on Knowledge and Data Engineering, 2000
- A new and versatile method for association generationInformation Systems, 1997