k-anonymization with minimal loss of information

Aristides Gionis, Tamir Tassa

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

The technique of k-anonymization allows the releasing of databases that contain personal information while ensuring some degree of individual privacy. Anonymization is usually performed by generalizing database entries. We formally study the concept of generalization, and propose two information-theoretic measures for capturing the amount of information that is lost during the anonymization process. Those measures are more general and more accurate than those proposed in [19] and [1]. We study the problem of achieving k-anonymity with minimal loss of information. We prove that it is NP-hard and study polynomial approximations for the optimal solution. Our first algorithm gives an approximation guarantee of O(ln k) - an improvement over the best-known O(k)-approximation of [1]. As the running time of the algorithm is O(n 2k), we also show how to adapt the algorithm of [1] in order to obtain an O(k)-approximation algorithm that is polynomial in both n and k.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAlgorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
ناشرSpringer Verlag
الصفحات439-450
عدد الصفحات12
رقم المعيار الدولي للكتب (المطبوع)9783540755197
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2007
الحدث15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, إسرائيل
المدة: ٨ أكتوبر ٢٠٠٧١٠ أكتوبر ٢٠٠٧

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت4698 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference15th Annual European Symposium on Algorithms, ESA 2007
الدولة/الإقليمإسرائيل
المدينةEilat
المدة٨/١٠/٠٧١٠/١٠/٠٧

بصمة

أدرس بدقة موضوعات البحث “k-anonymization with minimal loss of information'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا