KHyperLogLog: Estimating Reidentifiability and Joinability of Large Data at Scale
Open accessAbstract
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.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Even desensitized data may still be re-identifiable through sophisticated analysis methods.
“However, studies indicate that even desensitized data may still be re-identifiable through sophisticated analysis methods [178].”
From A Comprehensive Review on Synergy of Multi-Modal Data and AI Technologies in Medical Diagnosis (2024) · cites this paper as [178]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
MapReduce: simplified data processing on large clusters
Dean, J., & Ghemawat, S. (2008) · Communications of the ACM · doi:10.1145/1327452.1327492 · Cited by 18,476 · see citing works
k-ANONYMITY: A MODEL FOR PROTECTING PRIVACY
SWEENEY, L. (2002) · International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems · doi:10.1142/s0218488502001648 · Cited by 8,571 · see citing works
Dwork, C. (2006) · Lecture notes in computer science · doi:10.1007/11787006_1 · Cited by 5,362 · see citing works
<i>L</i> -diversity: Privacy beyond <i>k</i> -anonymity
Machanavajjhala, A., Kifer, D., Gehrke, J., & Venkitasubramaniam, M. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217302 · Cited by 3,617 · see citing works
t-Closeness: Privacy Beyond k-Anonymity and l-Diversity
Li, N., Li, T., & Venkatasubramanian, S. (2007) · 2007 IEEE 23rd International Conference on Data Engineering · doi:10.1109/icde.2007.367856 · Cited by 3,451 · see citing works
Robust De-anonymization of Large Sparse Datasets
Narayanan, A., & Shmatikov, V. (2008) · 2008 IEEE Symposium on Security and Privacy (sp 2008) · doi:10.1109/sp.2008.33 · Cited by 2,372 · see citing works
Similarity estimation techniques from rounding algorithms
Charikar, M. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.509965 · Cited by 2,262 · see citing works
An improved data stream summary: the count-min sketch and its applications
Cormode, G., & Muthukrishnan, S. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2003.12.001 · Cited by 2,259 · see citing works
On the resemblance and containment of documents
Broder, A. (2002) · Compression and Complexity of Sequences (SEQUENCES) · doi:10.1109/sequen.1997.666900 · Cited by 1,734 · see citing works
Learning from labeled and unlabeled data with label propagation
Zhu, X., & Ghahramani, Z. (2002) · Cited by 1,547 · see citing works
How Unique Is Your Web Browser?
Eckersley, P. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14527-8_1 · Cited by 758 · see citing works
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
Flajolet, P., Fusy, É., Gandouet, O., & Meunier, F. (2007) · Discrete Mathematics & Theoretical Computer Science · doi:10.46298/dmtcs.3545 · Cited by 709 · see citing works
Efficient Computation of Frequent and Top-k Elements in Data Streams
Metwally, A., Agrawal, D., & Abbadi, A. E. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-30570-5_27 · Cited by 691 · see citing works
Similarity estimation techniques from rounding algorithms
Charikar, M. (2002) · doi:10.1145/509961.509965 · Cited by 662 · see citing works
Anatomy: simple and effective privacy preservation
Xiao, X., & Tao, Y. (2006) · Very Large Data Bases · doi:10.5555/1182635.1164141 · Cited by 657 · see citing works
Finding frequent items in data streams
Cormode, G., & Hadjieleftheriou, M. (2008) · Proceedings of the VLDB Endowment · doi:10.14778/1454159.1454225 · Cited by 309 · see citing works
Heule, S., Nunkesser, M., & Hall, A. (2013) · International Conference on Extending Database Technology (EDBT) · doi:10.1145/2452376.2452456 · Cited by 307 · see citing works
Approximate medians and other quantiles in one pass and with limited memory
Manku, G. S., Rajagopalan, S., & Lindsay, B. G. (1998) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/276304.276342 · Cited by 265 · see citing works
On synopses for distinct-value estimation under multiset operations
Beyer, K. S., Haas, P. J., Reinwald, B., et al. (2007) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/1247480.1247504 · Cited by 185 · see citing works
Halevy, A. Y., Korn, F. R., Noy, N. F., et al. (2016) · Proceedings - ACM-SIGMOD International Conference on Management of Data · doi:10.1145/2882903.2903730 · Cited by 175 · see citing works
Flajolet, P., & Martin, G. N. (1983) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1983.46 · Cited by 155 · see citing works
Space efficient mining of multigraph streams
Cormode, G., & Muthukrishnan, S. (2005) · ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/1065167.1065201 · Cited by 129 · see citing works
Optimal Quantile Approximation in Streams
Karnin, Z. S., Lang, K., & Liberty, E. (2016) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2016.17 · Cited by 92 · see citing works
Bootstrapping Privacy Compliance in Big Data Systems
Sen, S., Guha, S., Datta, A., Rajamani, S. K., Tsai, J., & Wing, J. M. (2014) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2014.28 · Cited by 81 · see citing works
Better with fewer bits: Improving the performance of cardinality estimation of large data streams
Xiao, Q., Zhou, Y., & Chen, S. (2017) · doi:10.1109/infocom.2017.8057088 · Cited by 45 · see citing works
HyperMinHash: Jaccard index sketching in LogLog space.Preprint
Yu, Y. W., & Weber, G. M. (2017) · arXiv (Cornell University) · Cited by 8 · see citing works
Flagged first, then by citations
Research works printed but not linked: 1
- P. Jaccard, "Lois de distribution florale dans la zone alpine," vol. 38, pp. 69-130, 01 1902.
Cited by
Sorted by citations
A Comprehensive Review on Synergy of Multi-Modal Data and AI Technologies in Medical Diagnosis
Xu, X., Li, J., Zhu, Z., Zhao, L., Wang, H., Song, C., Chen, Y., Zhao, Q., Yang, J., & Pei, Y. (2024) · Bioengineering · doi:10.3390/bioengineering11030219 · Cited by 242 · see citing works
- Authors
- Chia, P. H., Desfontaines, D., Perera, I. M., Simmons-Marengo, D., Li, C., Day, W.-Y., Wang, Q., & Guevara, M.
- Affiliations
- Google (United States) (US)
- ETH Zurich (CH)
- ORCID
- Venue
- 2019 IEEE Symposium on Security and Privacy (SP)
- Publisher
- IEEE
- Published
- 2019-05
- Pages
- 350-364
- ISSN
- 1081-6011 (ISSN-L)
- OpenAlex
- W2910285766
- Cited by
- 15
- References
- 26
- Citations by year
- 2025: 1 · 2024: 3 · 2023: 4 · 2022: 2 · 2021: 2 · 2020: 3
- FWCI
- 0.67
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- Locations
- IEEE Symposium on Security and Privacy (S&P) (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
- Social Sciences › Decision Sciences › Management Science and Operations Research › Data Quality and Management
- Social Sciences › Sociology and Political Science › Privacy, Security, and Data Protection
- Keywords
- joinability, privacy risk assessment, HyperLogLog, approximate counting, large databases, pseudonymized data, data governance, privacy-preserving data analysis
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
