| Title | KHyperLogLog: Estimating Reidentifiability and Joinability of Large Data at Scale |
| Publication Type | Conference Paper |
| Year of Publication | 2019 |
| Authors | Chia, Pern Hui, Desfontaines, Damien, Perera, Irippuge Milinda, Simmons-Marengo, Daniel, Li, Chao, Day, Wei-Yen, Wang, Qiushi, Guevara, Miguel |
| Conference Name | 2019 IEEE Symposium on Security and Privacy (SP) |
| Date Published | may |
| Keywords | anonymity, approximate counting techniques, Approximate-Counting, Approximation algorithms, data characteristics, Data Governance, data privacy, Data-Privacy, Expert Systems and Privacy, Human Behavior, human factors, Indexes, joinability analysis, joinability risks, KHLL, KHyperLogLog, Measurement, Organizations, privacy, privacy relevant characteristics, proprietary data sets, pseudonymous identified data sets, pubcrawl, publicly available data sets, regression analysis, reidentifiability, Runtime, Scalability, very large databases |
| Abstract | Understanding the privacy relevant characteristics of data sets, such as reidentifiability and joinability, is crucial for data governance, yet can be difficult for large data sets. While computing the data characteristics by brute force is straightforward, the scale of systems and data collected by large organizations demands an efficient approach. We present KHyperLogLog (KHLL), an algorithm based on approximate counting techniques that can estimate the reidentifiability and joinability risks of very large databases using linear runtime and minimal memory. KHLL enables one to measure reidentifiability of data quantitatively, rather than based on expert judgement or manual reviews. Meanwhile, joinability analysis using KHLL helps ensure the separation of pseudonymous and identified data sets. We describe how organizations can use KHLL to improve protection of user privacy. The efficiency of KHLL allows one to schedule periodic analyses that detect any deviations from the expected risks over time as a regression test for privacy. We validate the performance and accuracy of KHLL through experiments using proprietary and publicly available data sets. |
| DOI | 10.1109/SP.2019.00046 |
| Citation Key | chia_khyperloglog_2019 |
KHyperLogLog: Estimating Reidentifiability and Joinability of Large Data at Scale