Entity Resolution at 50M Records: Blocking Strategies That Actually Work

The Quadratic Problem You Cannot Ignore

Fuzzy entity matching is conceptually simple: compare every record to every other record, compute a similarity score, and declare a match if the score exceeds a threshold. For a few thousand records, this works fine and runs quickly. For 50 million records, naive pairwise comparison produces 2.5 x 10¹⁵ candidate pairs. Even at 1 microsecond per comparison, that is roughly 79,000 years of compute time.

This is not a hardware problem you can solve by throwing more cores at it. It is an algorithmic problem. The solution is blocking: a preprocessing step that groups records into candidate sets before matching, so that the matching algorithm only runs on pairs that have a reasonable probability of being the same entity. Good blocking reduces candidate pairs by 99.9% or more while retaining nearly all true matches. Bad blocking either leaves too many candidates (still slow) or eliminates true matches before they get evaluated (poor recall).

This post goes through the three blocking strategies we use in HyperNorm, why each one works in specific situations, and how to combine them for datasets that do not fit neatly into one category.

Strategy 1: Key-Collision Blocking (Soundex / Double Metaphone)

Key-collision blocking works by applying a deterministic function to each record's key field, then grouping records with the same resulting key. The classic implementation uses Soundex or Double Metaphone: phonetic hash functions that encode names based on how they sound rather than how they are spelled.

Soundex maps "Acme" and "Acme Corporation" to the same code (A250). It maps "Karbon" and "Carbon" to the same code (K615). It collapses many spelling variants that differ by vowel omission, doubled consonants, or common abbreviations.

Double Metaphone is more accurate than Soundex for English and handles some non-English patterns better. For company names in Latin-script languages, it is a reliable first-pass blocker.

blocking_config = {
    "strategy": "key_collision",
    "key_field": "company_name",
    "hash_function": "double_metaphone",
    "candidate_limit": 500
}

The candidate_limit parameter is important. For common words like "Global" or "National," the phonetic key will match thousands of company names that have nothing in common beyond a generic word. Setting a candidate limit prevents runaway comparison sets for high-frequency phonetic keys. Records in a block that exceeds the limit are flagged for secondary blocking rather than skipped entirely.

Key-collision blocking is best for: company names in a single language, entity types where the key field is a name or label, and datasets where variant spellings are the primary source of duplication.

Strategy 2: Sorted-Neighborhood

Sorted-neighborhood blocking sorts all records by a key field (or a transformed version of it) and then slides a window of size W across the sorted list, comparing only records within the same window. The intuition is that true duplicates, after sorting, will be near each other in the ordering, while non-matches will be far apart.

The typical approach is to sort by a phonetically or alphabetically normalized version of the key field. "Acme Corp" and "ACME Corporation" both sort near "Acme" after normalization, so they land in the same window. "Acme" and "Zenith" are far apart in the sorted order and never become a candidate pair.

blocking_config = {
    "strategy": "sorted_neighborhood",
    "sort_field": "company_name",
    "sort_transform": "nfkd_lowercase_strip_punctuation",
    "window_size": 10
}

The window size is the critical parameter. Larger windows mean more candidate pairs per record (higher recall, slower runtime). Smaller windows may miss true duplicates where the sort position is separated by more than W/2 positions. For most company name datasets, a window of 5-15 covers the majority of true matches without excessive candidate generation.

Sorted-neighborhood is best for: datasets where records are nearly sorted already (sequential ID assignment, alphabetical imports), and cases where you want predictable runtime because the candidate pair count is bounded by n x W rather than varying based on key distribution.

Strategy 3: Locality-Sensitive Hashing (LSH)

LSH is the most general blocking strategy and the most powerful for large, heterogeneous datasets. The idea: hash records into buckets such that similar records are likely to land in the same bucket, using a randomized hash family that has the locality-sensitive property. Records in the same bucket become candidate pairs.

For text fields, the common approach is MinHash LSH: convert each record to a set of character n-grams, apply multiple hash functions to generate a signature, then use band-and-row LSH to assign records to buckets. Records with high Jaccard similarity in their n-gram sets have a high probability of sharing at least one bucket.

blocking_config = {
    "strategy": "lsh",
    "lsh_field": "company_name",
    "ngram_size": 3,
    "num_hash_functions": 128,
    "num_bands": 16,
    "similarity_threshold": 0.5
}

The relationship between num_bands, num_hash_functions, and the effective similarity threshold follows the standard LSH tradeoff: more bands means lower effective threshold (catches more distant matches but generates more false-positive pairs). For entity resolution on company names, a Jaccard threshold of around 0.5-0.6 tends to work well as a blocking criterion because many variants share a substantial fraction of 3-grams even when the string edit distance is large.

LSH is best for: large heterogeneous datasets, cases where entity variants may have significant string differences that phonetic or sorted-neighborhood blocking misses, and multi-field blocking where you want to combine similarity signals from several fields before selecting candidates.

Composite Blocking: Combining Strategies

For a 50M-record dataset with multi-vendor provenance, no single blocking strategy covers all entity types reliably. The practical approach is composite blocking: run multiple blocking passes with different strategies, take the union of candidate pairs, deduplicate the candidate list, and then run the matching algorithm once on the combined candidate set.

blocking_config = [
    {
        "strategy": "key_collision",
        "key_field": "company_name",
        "hash_function": "double_metaphone"
    },
    {
        "strategy": "lsh",
        "lsh_field": "company_name",
        "ngram_size": 3,
        "num_bands": 16,
        "similarity_threshold": 0.5
    },
    {
        "strategy": "exact_match",
        "match_field": "domain",
        "optional": true
    }
]

The exact_match on domain is a high-precision supplement: if two records have the same company domain (acme.com), they are almost certainly the same entity regardless of how differently the company name is spelled. Exact blocking on a reliable identifier field is cheap and high-precision. It does not replace the fuzzy strategies but adds a complementary high-confidence path.

On a 50M-record dataset processed through HyperNorm's blocking layer, composite LSH plus Double Metaphone with domain supplement typically reduces the candidate pair space to 0.05-0.2% of the naive O(n²) count, while retaining approximately 97-99% of true matches in the candidate set. The loss of a few percent of true matches in the blocking step is acceptable for most use cases; it is not acceptable for high-stakes entity contexts like regulatory compliance datasets where false negatives carry real risk.

Evaluating Blocking Quality Before Running Matching

One mistake teams make is running the full matching step before checking whether their blocking strategy is working. Blocking quality has two dimensions: recall (are true matches reaching the candidate set?) and precision (is the candidate set small enough to be tractable?).

You can evaluate both with a sample before running at full scale:

blocking_eval = client.blocking.evaluate(
    config=blocking_config,
    sources=["vendor_a", "vendor_b"],
    sample_size=50000,
    ground_truth=known_matches_sample  # optional, for recall estimation
)

print(blocking_eval)
# {
#   "candidate_pair_rate": 0.0012,   # 0.12% of O(n*m)
#   "estimated_recall": 0.984,       # 98.4% of true matches in candidate set
#   "avg_block_size": 4.3,
#   "max_block_size": 1204,
#   "oversize_blocks": 7,            # blocks exceeding 500-record limit
#   "runtime_estimate_seconds": 142
# }

The oversize_blocks count of 7 tells you which phonetic keys or LSH bucket collisions are producing unusually large candidate sets. These are typically generic words in company names ("Global," "National," "Systems") that are legitimate disambiguation challenges. You can inspect and split these blocks with secondary blocking strategies before proceeding.

One More Thing About Scale

The blocking strategies described here are not new. LSH was formalized in the late 1990s; sorted-neighborhood has been in the record linkage literature since the early 1980s. What changes at 50M records is the engineering discipline required to implement them correctly at production scale: memory management for large block sets, deterministic parallel execution across worker nodes, and incremental blocking for new records arriving in a stream rather than batch.

Incremental blocking deserves a post of its own. The short version: for streaming ingestion, you do not want to re-block the full dataset on every new record. HyperNorm maintains a blocking index that supports efficient insertion of new records into existing block structures, so new records are compared against their candidate set without reprocessing the entire corpus. The index is rebuilt periodically (configurable schedule) to account for cumulative drift in the blocking key distribution.

The point here is that scale is a solvable engineering problem for entity resolution. The algorithmic foundation is well-established. What matters is choosing the right combination of blocking strategies for your entity type, evaluating blocking quality before running at full volume, and building the feedback mechanisms to detect when blocking performance degrades as source data changes.