Abstract
As the digital advertising industry shifts away from individual tracking toward privacy-preserving cohort-based identity, the challenge of grouping millions of users into tight, similar clusters while maintaining $K$-anonymity has become paramount. Researchers at LinkedIn have introduced Consecutive Consistent Weighted Sampling (CCWS), a scalable hierarchical clustering algorithm. By leveraging advanced hashing techniques, CCWS ensures every cohort meets a minimum size $K$ while significantly outperforming industry standards like SimHash and vanilla Consistent Weighted Sampling (CWS) in targeting accuracy.
Introduction: The Privacy-Utility Trade-off
Driven by privacy initiatives such as Apple’s App Tracking Transparency (ATT) and Google’s Privacy Sandbox, the advertising landscape is moving toward cohort-based identity. The objective is to group users with similar interests into cohorts that are $K$-anonymous, meaning each group must contain at least $K$ users (e.g., $K=20$) to prevent individual identification.
Developing such a system at scale presents two major technical hurdles:
- Scalability: With hundreds of millions of users and high-dimensional feature vectors, traditional $O(n^2)$ clustering algorithms are computationally infeasible.
- Constraint Satisfaction: Standard clustering methods do not guarantee a minimum cluster size, a hard requirement for privacy compliance.
The CCWS Methodology
CCWS builds upon Consistent Weighted Sampling (CWS), a hashing technique designed to estimate similarity between non-binary, weighted data vectors. Unlike traditional "hash-and-sort" baselines that simply chop sorted users into fixed blocks, CCWS employs a recursive hierarchical splitting logic:
- Hierarchical Splitting: Starting with a single global cohort, the algorithm applies CWS to generate hash values for every user.
- Consecutive Logic: It identifies the most frequent hash value. A split is executed only if separating users with that hash into a new group leaves at least $K$ users in both the new and the remaining cohort.
- Termination: This process repeats until no further splits can be made without violating the $K$-member minimum.
This approach ensures that the resulting cohorts are not only privacy-compliant but also highly cohesive, as the splitting logic prioritizes the preservation of similarity.
Experimental Evaluation
The algorithm was evaluated using a real-world dataset from LinkedIn Ads, comprising over 70 million users. Each user was represented by a weighted feature vector of approximately 200,000 dimensions. Performance was measured by how well the generated cohorts matched the original intended audiences of actual ad campaigns.
Key Results
CCWS was compared against several baselines, including Random Grouping, MinHash, SignRP (SimHash), and a "hash-and-sort" version of CWS.
As shown in the table above, CCWS achieved a Macro-Recall of 0.844, outperforming the next best method (CWS hash-and-sort) at 0.721. More impressively, CCWS achieved a Micro-Recall of 0.254, representing a 3x improvement over both vanilla CWS (0.082) and SignRP (0.077).
Cohort Distribution and Privacy
To maximize targeting granularity, it is ideal for cohorts to stay as close to the privacy floor ($K$) as possible. CCWS demonstrates excellent control over cohort size distribution.
Analysis of the cohort distribution reveals that over 95% of the generated cohorts had sizes between 20 and 40. This indicates that the algorithm effectively creates tight groups that minimize audience dilution while strictly adhering to the $K=20$ privacy constraint.
Insights and Future Work
CCWS demonstrates linear efficiency ($O(Tn)$), making it viable for industrial-scale applications. The researchers found that utilizing weighted features (via CWS) rather than binarized data (via MinHash) is crucial for accuracy. Furthermore, the algorithm proved robust to hyperparameter tuning, specifically regarding the $p$-powered generalized min-max kernel.
While CCWS offers a massive leap in performance, micro-recall remains a challenge for very niche, highly-targeted campaigns where any grouping inevitably dilutes precision. Future work will explore integrating feature importance—such as weighting geographic or professional data more heavily—to further refine cohort quality while respecting the boundaries of $K$-anonymity.
Summary updated