Skip to main content
Erschienen in: Knowledge and Information Systems 1/2016

01.10.2016 | Regular Paper

Managing dimensionality in data privacy anonymization

verfasst von: Hessam Zakerzadeh, Charu C. Aggarwal, Ken Barker

Erschienen in: Knowledge and Information Systems | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The curse of dimensionality has remained a challenge for a wide variety of algorithms in data mining, clustering, classification, and privacy. Recently, it was shown that an increasing dimensionality makes the data resistant to effective privacy. The theoretical results seem to suggest that the dimensionality curse is a fundamental barrier to privacy preservation. However, in practice, we show that some of the common properties of real data can be leveraged in order to greatly ameliorate the negative effects of the curse of dimensionality. In real data sets, many dimensions contain high levels of inter-attribute correlations. Such correlations enable the use of a process known as vertical fragmentation in order to decompose the data into vertical subsets of smaller dimensionality. An information-theoretic criterion of mutual information is used in the vertical decomposition process. This allows the use of an anonymization process, which is based on combining results from multiple independent fragments. We present a general approach, which can be applied to the k-anonymity, \(\ell \)-diversity, and t-closeness models. In the presence of inter-attribute correlations, such an approach continues to be much more robust in higher dimensionality, without losing accuracy. We present experimental results illustrating the effectiveness of the approach. This approach is resilient enough to prevent identity, attribute, and membership disclosure attack.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Fußnoten
1
Although the works in [29, 30] are originally proposed for the set-valued (transaction) data, the relational data can be transformed to set-valuded data for anonymization.
 
4
Recall that fragmentation is the first step in the k-anonymity and step 3 in the \(\ell \)-diversity algorithm.
 
5
Here, the power of an attacker means the number of quasi-identifier that he/she is aware of.
 
6
The work in [12] only considers the \(\ell \)-diversity model, so it is not suitable for comparison with our work.
 
8
There are 7 classes. However, there exist instances for only 6 classes in this training sample.
 
9
This data set has only 36 features.
 
10
We adopt distinct \(\ell \)-diversity in our experiments.
 
11
Note that this metric is independent of anonymity degree (k or \(\ell \)) because it is calculated before anonymization algorithm is applied on the data.
 
Literatur
1.
Zurück zum Zitat Agrawal R, Srikant R (2000) Privacy-preserving data mining. In: SIGMOD Agrawal R, Srikant R (2000) Privacy-preserving data mining. In: SIGMOD
2.
Zurück zum Zitat Aggarwal CC (2005) On \(k\)-anonymity and the curse of dimensionality. In: VLDB Aggarwal CC (2005) On \(k\)-anonymity and the curse of dimensionality. In: VLDB
3.
Zurück zum Zitat Aggarwal CC (2007) On randomization, public information, and the curse of dimensionality. In: ICDE Aggarwal CC (2007) On randomization, public information, and the curse of dimensionality. In: ICDE
4.
Zurück zum Zitat Aggarwal CC (2008) Privacy and the dimensionality curse. In: Aggarwal C, Yu PS (eds) Privacy preserving data mining: models and algorithms. Springer, Berlin Aggarwal CC (2008) Privacy and the dimensionality curse. In: Aggarwal C, Yu PS (eds) Privacy preserving data mining: models and algorithms. Springer, Berlin
5.
Zurück zum Zitat Agrawal S, Haritsa J (2005) A framework for high accuracy privacy-preserving data mining. In: ICDE Agrawal S, Haritsa J (2005) A framework for high accuracy privacy-preserving data mining. In: ICDE
6.
Zurück zum Zitat Aggarwal CC, Yu PS (2008) Privacy preserving data mining: models and algorithms. Springer, BerlinCrossRef Aggarwal CC, Yu PS (2008) Privacy preserving data mining: models and algorithms. Springer, BerlinCrossRef
7.
Zurück zum Zitat Chow C-Y, Mokbel MF (2011) Trajectory privacy in location-based services and data publication. ACM SIGKDD Explor Newsl 13(1):19–29CrossRef Chow C-Y, Mokbel MF (2011) Trajectory privacy in location-based services and data publication. ACM SIGKDD Explor Newsl 13(1):19–29CrossRef
8.
Zurück zum Zitat Ciriani V, Capitani Di Vimercati S, Foresti S, Jajodia S, Paraboschi S, Samarati P (2010) Combining fragmentation and encryption to protect privacy in data storage. ACM Trans Inf Syst Secur 13(3):1–33CrossRef Ciriani V, Capitani Di Vimercati S, Foresti S, Jajodia S, Paraboschi S, Samarati P (2010) Combining fragmentation and encryption to protect privacy in data storage. ACM Trans Inf Syst Secur 13(3):1–33CrossRef
9.
Zurück zum Zitat Ding C, Peng H (2003) Minimum redundancy feature selection from microarray gene expression data. In: CSB Ding C, Peng H (2003) Minimum redundancy feature selection from microarray gene expression data. In: CSB
10.
Zurück zum Zitat Ganapathy V, Thomas D, Feder T, Garcia-Molina H, Motwani R (2011) Distributing data for secure database services. In: PAIS workshop Ganapathy V, Thomas D, Feder T, Garcia-Molina H, Motwani R (2011) Distributing data for secure database services. In: PAIS workshop
11.
Zurück zum Zitat Ghinita G, Karras P, Kalnis P, Mamoulis N (2007) Fast data anonymization with low information loss. In: VLDB Ghinita G, Karras P, Kalnis P, Mamoulis N (2007) Fast data anonymization with low information loss. In: VLDB
12.
Zurück zum Zitat Ghinita G, Tao Y, Kalnis P (2008) On the anonymization of sparse high-dimensional data. In: ICDE Ghinita G, Tao Y, Kalnis P (2008) On the anonymization of sparse high-dimensional data. In: ICDE
13.
Zurück zum Zitat Iyengar V (2002) Transforming data to satisfy privacy constraints. In: KDD Iyengar V (2002) Transforming data to satisfy privacy constraints. In: KDD
14.
Zurück zum Zitat Kifer D (2009) Attacks on privacy and deFinetti’s theorem. In: SIGMOD Kifer D (2009) Attacks on privacy and deFinetti’s theorem. In: SIGMOD
15.
Zurück zum Zitat LeFevre K, DeWitt DJ, Ramakrishnan R (2006) Mondrian multidimensional \(k\)-anonymity. In: ICDE LeFevre K, DeWitt DJ, Ramakrishnan R (2006) Mondrian multidimensional \(k\)-anonymity. In: ICDE
16.
Zurück zum Zitat LeFevre K, DeWitt DJ, Ramakrishnan R (2006) Workload-aware anonymization. In: KDD LeFevre K, DeWitt DJ, Ramakrishnan R (2006) Workload-aware anonymization. In: KDD
17.
Zurück zum Zitat LeFevre K, DeWitt D, Ramakrishnan R (2005) Incognito: efficient full-domain \(k\)-anonymity. In: SIGMOD LeFevre K, DeWitt D, Ramakrishnan R (2005) Incognito: efficient full-domain \(k\)-anonymity. In: SIGMOD
18.
Zurück zum Zitat Li F, Sun J, Papadimitriou S, Mihaila G, Stanoi I (2007) Hiding in the crowd: privacy preservation on evolving streams through correlation tracking. In: ICDE Li F, Sun J, Papadimitriou S, Mihaila G, Stanoi I (2007) Hiding in the crowd: privacy preservation on evolving streams through correlation tracking. In: ICDE
19.
Zurück zum Zitat Li N, Li T, Venkatasubramaniam S (2007) \(t\)-diversity. In: ICDE Li N, Li T, Venkatasubramaniam S (2007) \(t\)-diversity. In: ICDE
20.
Zurück zum Zitat Li T, Li N, Zhang J, Molloy I (2012) Slicing: a new approach for privacy preserving data publishing. IEEE Trans Knowl Data Eng 24(3):561–574CrossRef Li T, Li N, Zhang J, Molloy I (2012) Slicing: a new approach for privacy preserving data publishing. IEEE Trans Knowl Data Eng 24(3):561–574CrossRef
21.
Zurück zum Zitat Liu H, Motoda H (2007) Computational methods for feature selection. Chapman and Hall/CRC, London (data mining and knowledge discovery series)MATH Liu H, Motoda H (2007) Computational methods for feature selection. Chapman and Hall/CRC, London (data mining and knowledge discovery series)MATH
22.
Zurück zum Zitat Machanvajjhala A, Gehrke J, Kifer D, Venkitasubramaniam M (2006) \(\ell \)-anonymity. In: ICDE Machanvajjhala A, Gehrke J, Kifer D, Venkitasubramaniam M (2006) \(\ell \)-anonymity. In: ICDE
23.
Zurück zum Zitat Peng H, Long F, Ding C (2005) Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy. IEEE Trans Pattern Anal Mach Intell 27(8):1226–1238CrossRef Peng H, Long F, Ding C (2005) Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundancy. IEEE Trans Pattern Anal Mach Intell 27(8):1226–1238CrossRef
24.
Zurück zum Zitat Samarati P (2001) Protecting Respondents’ identities in microdata release. IEEE Trans Knowl Data Eng 13(6):1010–1027CrossRef Samarati P (2001) Protecting Respondents’ identities in microdata release. IEEE Trans Knowl Data Eng 13(6):1010–1027CrossRef
25.
Zurück zum Zitat Vaidya J, Clifton C (2002) Privacy-preserving association rule mining in vertically partitioned data. In: KDD Vaidya J, Clifton C (2002) Privacy-preserving association rule mining in vertically partitioned data. In: KDD
26.
Zurück zum Zitat Xiao X, Tao Y (2006) Anatomy: simple and effective privacy preservation. In: VLDB Xiao X, Tao Y (2006) Anatomy: simple and effective privacy preservation. In: VLDB
27.
Zurück zum Zitat Wong W, Mamoulis N, Cheung D (2010) Non-homogeneous generalization in privacy preserving data publishing. In: SIGMOD Wong W, Mamoulis N, Cheung D (2010) Non-homogeneous generalization in privacy preserving data publishing. In: SIGMOD
28.
Zurück zum Zitat Xue M, Karras P, Raissi C, Vaidya J, Tan K (2012) Anonymizing set-valued data by nonreciprocal recoding. In: KDD Xue M, Karras P, Raissi C, Vaidya J, Tan K (2012) Anonymizing set-valued data by nonreciprocal recoding. In: KDD
29.
Zurück zum Zitat Terrovitis M, Mamoulis N, Kalnis P (2008) Privacy-preserving anonymization of set-valued data. In: VLDB Terrovitis M, Mamoulis N, Kalnis P (2008) Privacy-preserving anonymization of set-valued data. In: VLDB
30.
Zurück zum Zitat Xu Y, Wang K, Fu AW, Yu PS (2008) Anonymizing transaction databases for publication. In: KDD Xu Y, Wang K, Fu AW, Yu PS (2008) Anonymizing transaction databases for publication. In: KDD
31.
Zurück zum Zitat Mohammad N, Fung B, Hung P, Lee C (2009) Anonymizing healthcare data: a case study on the blood transfusion service. In: KDD Mohammad N, Fung B, Hung P, Lee C (2009) Anonymizing healthcare data: a case study on the blood transfusion service. In: KDD
32.
Zurück zum Zitat Ercan Nergiz M, Atzori M, Clifton C (2007) Hiding the presence of individuals from shared databases. In: SIGMOD Ercan Nergiz M, Atzori M, Clifton C (2007) Hiding the presence of individuals from shared databases. In: SIGMOD
33.
Zurück zum Zitat Zakerzadeh H, Aggarwal CC, Barker K (2014) Towards breaking the curse of dimensionality for high-dimensional privacy. In: SDM Zakerzadeh H, Aggarwal CC, Barker K (2014) Towards breaking the curse of dimensionality for high-dimensional privacy. In: SDM
34.
Zurück zum Zitat Kifer D, Gehrke J (2006) Injecting utility into anonymized datasets. In: SIGMOD Kifer D, Gehrke J (2006) Injecting utility into anonymized datasets. In: SIGMOD
35.
Zurück zum Zitat Mohammed N, Fung B, Hung P, Lee C (2010) Centralized and distributed anonymization for high-dimensional healthcare data. In: TKDD Mohammed N, Fung B, Hung P, Lee C (2010) Centralized and distributed anonymization for high-dimensional healthcare data. In: TKDD
36.
Zurück zum Zitat Terrovitis M, Liagouris J, Mamoulis N, Skiadopoulos S (2012) Privacy preservation by disassociation. In: VLDB Terrovitis M, Liagouris J, Mamoulis N, Skiadopoulos S (2012) Privacy preservation by disassociation. In: VLDB
37.
Zurück zum Zitat Nergiz M, Atzori M, Clifton C (2007) Hiding the presence of individuals from shared databases. In: SIGMOD Nergiz M, Atzori M, Clifton C (2007) Hiding the presence of individuals from shared databases. In: SIGMOD
38.
Zurück zum Zitat Dwork C (2006) Differntial privacy. In: ICALP Dwork C (2006) Differntial privacy. In: ICALP
39.
Zurück zum Zitat Dwork C, McSherry F, Nissim K, Smith A (2006) Calibrating noise to sensitivity in private data analysis. In: TCC Dwork C, McSherry F, Nissim K, Smith A (2006) Calibrating noise to sensitivity in private data analysis. In: TCC
40.
Zurück zum Zitat Hotelling H (1993) Analysis of a complex of statistical variables into principal components. J Educ Psychol 24(6):417–441CrossRef Hotelling H (1993) Analysis of a complex of statistical variables into principal components. J Educ Psychol 24(6):417–441CrossRef
41.
Zurück zum Zitat He Y, Naughton J (2009) Anonymization of set-valued data via top-down, local generalization. In: VLDB He Y, Naughton J (2009) Anonymization of set-valued data via top-down, local generalization. In: VLDB
42.
Zurück zum Zitat Zakerzadeh H, Osborn SL (2013) Delay-sensitive approaches for anonymizing numerical streaming data. Int J Inf Sec 12(5):423–437CrossRef Zakerzadeh H, Osborn SL (2013) Delay-sensitive approaches for anonymizing numerical streaming data. Int J Inf Sec 12(5):423–437CrossRef
43.
Zurück zum Zitat Cao J, Karras P (2012) Publishing microdata with a robust privacy guarantee. In: VLDB Cao J, Karras P (2012) Publishing microdata with a robust privacy guarantee. In: VLDB
Metadaten
Titel
Managing dimensionality in data privacy anonymization
verfasst von
Hessam Zakerzadeh
Charu C. Aggarwal
Ken Barker
Publikationsdatum
01.10.2016
Verlag
Springer London
Erschienen in
Knowledge and Information Systems / Ausgabe 1/2016
Print ISSN: 0219-1377
Elektronische ISSN: 0219-3116
DOI
https://doi.org/10.1007/s10115-015-0906-8

Weitere Artikel der Ausgabe 1/2016

Knowledge and Information Systems 1/2016 Zur Ausgabe