Problem
Yandex advertising has about 5 million client accounts. One business often opens many logins, and the same business appears in several sources (tax registries, maps, advertising). Without a merged view the company cannot tell whether a "newcomer" who gets bonuses and promo codes is really new, and different sales managers serve the same business without knowing it. Pairwise matching of all accounts means 25 trillion pairs, too many to compute daily. A plain graph of shared attributes does not help either: it glues unrelated businesses into giant components.
Example from the article: several businesses served by different client managers turned out to be one business. The client got called about 10 times a day with upsell offers.
Solution in brief
Build groups of accounts that share a precise attribute (tax ID, website, map point), score pairs only inside groups with a model trained on crowd labels, and keep only confident pairs. Cluster those pairs into a "business atom", cutting oversized graphs. This reduces 25 trillion pairs to about one billion.
Questions this case answers
- How to merge duplicate entities across many sources into one entity at scale when pairwise matching is quadratic and shared attributes create giant connected components
- How to decide whether a new account belongs to an entity that already exists in the base
- How to merge duplicate advertiser accounts into one business entity across many data sources
- How to run pairwise matching on millions of entities without comparing every pair
Tools and methods
- Graph of shared attributes — vertices are accounts and organizations, edges are common tax ID, website or map point
- Connected components (distributed) — split the graph into candidate groups
- Client-client ML model — pairwise score trained on crowd labels (Yandex Crowd), ROC AUC 0.92
- METIS decluster and agglomerative clustering — cut oversized graphs and form tightly linked clusters (atoms)
Google or a one-time email code. No password.
