A Scheme for Fast k-Concealment Anonymization

Ryosuke KOYANAGI  Ryo FURUKAWA  Tsubasa TAKAHASHI  Takuya MORI  Toshiyuki AMAGASA  Hiroyuki KITAGAWA  

IEICE TRANSACTIONS on Information and Systems   Vol.E99-D   No.4   pp.1000-1009
Publication Date: 2016/04/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015DAP0030
Type of Manuscript: Special Section PAPER (Special Section on Data Engineering and Information Management)
k-concealment,  privacy,  data publishing,  

Full Text: PDF(1.4MB)
>>Buy this Article

In this paper we propose an improved algorithm for k-concealment, which has been proposed as an alternative to the well-known k-anonymity model. k-concealment achieves similar privacy goals as k-anonymity; it proposes to generalize records in a table in such a way that each record is indistinguishable from at least k-1 other records, while achieving higher utility than k-anonymity. However, its computation is quite expensive in particular when dealing with large datasets containing massive records due to its high computational complexity. To cope with this problem, we propose neighbor lists, where for each record similar records are stored. Neighbor lists are constructed in advance, and can also be efficiently constructed by mapping each record to a point in a high-dimensional space and using appropriate multidimensional indexes. Our proposed scheme successfully decreases the execution time from O(kn2) to O(k2n+knlogn), and it can be practically applied to databases with millions of records. The experimental evaluation using a real dataset reveals that the proposed scheme can achieve the same level of utility as k-concealment while maintaining the efficiency at the same time.