报告题目: |
Approximate Algorithms for k-Anonymity |
报告人: |
Kyuseok Shim |
|
|
报告时间: |
2007-08-08 15:00 |
报告地点: |
清华大学FIT楼4-302 |
主办单位: |
计算机系数据库实验室 |
简介: |
Kyuseok is an Associate Professor at School of EECS at Seoul National University, Korea. Before that, he was an Assistant Professor at CS Department of KAIST (Korea), a MTS at Bell Laboratories (Murray Hill) and a research staff at IBM Almaden Research Center (San Jose). Kyuseok received a Ph.D in Computer Science from University of Maryland at College Park in 1993. He has been working in the area of data mining, data privacy, embedded flash memory database systems, semi-structured data (XML), stream data, histogram, query processing, query optimization and data warehousing. He has published more than 60 papers in some top journals and conferences, such as ACM TODS, IEEE TKDE, VLDB Journal, DMKD Journal, ACM SIGMOD, ACM SIGKDD, VLDB, STOC, and ICDE. He is currently an associate editor of the IEEE Transactions on Knowledge and Data Engineering, an editorial board member of the VLDB Journal, and is serving or has been served as a PC member for many top conferences, such as ACM SIGMOD, ACM SIGKDD, VLDB, IEEE ICDE, ICDT, WWW, IEEE ICDM, and SIAM SDM.
内容简介： When a table containing individual data is published, disclosure of sensitive information should be prohibitive. A naive approach for the problem is to remove identifiers such as name and social security number. However, linking attacks which joins the published table with other tables on some attributes, called quasi-identifier, may reveal the sensitive information. To protect privacy against linking attack, the notion of k-anonymity which makes each record in the table be indistinguishable with (k-1) other records has been proposed previously. It is shown to be NP-Hard to k-anonymize a table minimizing the number of suppressed cells. To alleviate this, O(k*log k)-approximation and O(k)- approximation algorithms were proposed in previous works.
In this talk, we present several approximation algorithms that guarantee O(log k)-approximation ratio and perform significantly better than the traditional algorithms. We also provide O(beta*log k)-approximate algorithms which gracefully adjust their running time according to the tolerance beta (>= 1) of the approximation ratios. Experimental results confirm that our approximation algorithms perform significantly better than traditional approximation algorithms.
|
|
