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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2007
אירוע15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, ישראל
משך הזמן: 8 אוק׳ 200710 אוק׳ 2007

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך4698 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס15th Annual European Symposium on Algorithms, ESA 2007
מדינה/אזורישראל
עירEilat
תקופה8/10/0710/10/07

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'k-anonymization with minimal loss of information'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי