The Entity Resolution Task: Atomic Factory

Ilya Shishov24 May 2025

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)
Continue reading — it's free

Google or a one-time email code. No password.