Full Citation

Title: Kd-trees and the real disclosure risks of large statistical databases

Citation Type: Journal Article

Publication Year: 2011

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: Estimating the disclosure risk of a Statistical Disclosure Control (SDC) protection method by means of (distance-based) record linkage techniques is a very popular approach to analyze the privacy level offered by such a method. When databases are very large, some particular record linkage techniques such as blocking or partitioning are usually applied to make this process reasonably efficient. However, in this case the record linkage process is not exact, which means that the disclosure risk of a SDC protection method may be underestimated.In this paper we propose the use of kd-trees techniques to apply exact yet very efficient record linkage when (protected) datasets are very large. We describe some experiments showing that this approach achieves better results, in terms of both accuracy and running time, than more classical approaches such as record linkage based on a sliding window.We also discuss and experiment on the use of these techniques not to link a whole protected record with its original one, but just to guess the value of some confidential attribute(s) of the record(s). This fact leads to concepts such as k-neighbor l-diversity or k-neighbor p-sensitivity, a generalization (to any SDC protection method) of l-diversity or p-sensitivity, which have been defined for SDC protection methods ensuring k-anonymity, such as microaggregation.

User Submitted?: No

Authors: Sol, Marc; Herranz, Javier; Nin, Jordi

Periodical (Full): Information Fusion

Issue:

Volume: 13

Pages: 260-273

Data Collections: IPUMS USA

Topics: Methodology and Data Collection

Countries: