Blocking

A blocking key is a deterministic function that maps a record to a string value, grouping records that share the same key into a block. Common functions include:

• Phonetic encoding: Soundex or Double Metaphone on surnames to group similar-sounding names
• Sorted neighborhood: Sorting records by a key and sliding a fixed-size window over the sorted list
• Token-based: Extracting the first 3 characters of a last name and zip code prefix
• N-gram indexing: Using character n-grams to create overlapping blocks for fuzzy matching

The key must balance recall (not missing true matches) against reduction ratio (eliminating unnecessary comparisons).

The reduction ratio quantifies how effectively a blocking strategy prunes the comparison space. It is calculated as:

RR = 1 - (s_M / s_N)

Where s_M is the number of candidate pairs generated and s_N is the total possible pairs n(n-1)/2.

• A reduction ratio of 0.99 means only 1% of all possible pairs are compared
• Higher ratios reduce compute cost but risk false negatives if true matches fall into different blocks
• Typical production systems target a reduction ratio between 0.95 and 0.99 while maintaining recall above 0.95

After blocking and pairwise comparison, transitive closure resolves indirect matches into connected components. If record A matches B, and B matches C, then A, B, and C form a single entity cluster.

• Connected components algorithm: Builds clusters by traversing all match edges in the graph
• Merge propagation: Ensures all records in a cluster share the same canonical identifier
• Cluster deduplication: Post-processing step that merges overlapping clusters from different blocking passes

Transitive closure is essential because blocking strategies often produce overlapping blocks where the same entity appears in multiple partitions.

Multi-pass blocking runs multiple independent blocking strategies and unions the candidate pairs to improve recall. No single blocking key captures all true matches, so combining approaches compensates for individual weaknesses.

• Disjoint blocking: Each pass uses a different key (e.g., zip code, then Soundex last name, then date of birth)
• Union of candidates: All pairs from all passes are pooled before deduplication and comparison
• Cost tradeoff: Each additional pass increases the number of comparisons, reducing the overall reduction ratio

Production pipelines typically use 3-5 blocking passes with orthogonal keys to achieve high recall without excessive compute.

The Sorted Neighborhood Method (SNM) sorts records by a blocking key and slides a fixed-size window over the sorted list, comparing only records within the same window.

• Window size (w): Typically 10-50 records; larger windows increase recall but add comparisons
• Multi-pass SNM: Running SNM multiple times with different sort keys to capture matches missed in a single pass
• Key selection: Sort keys should cluster similar records together; concatenating multiple fields (e.g., city + first initial) improves clustering

SNM is particularly effective when the blocking key has graded similarity rather than exact equality, as nearby records in the sorted order are likely to be true matches.

Canopy clustering is a cheap, approximate clustering technique used as a pre-blocking step. It creates overlapping "canopies" using a loose similarity metric, then performs expensive comparisons only within each canopy.

• T1 threshold: A loose threshold that determines canopy membership; records within T1 distance of a canopy center are included
• T2 threshold: A tight threshold; records within T2 distance become new canopy centers
• Overlapping canopies: Records can belong to multiple canopies, improving recall at the cost of some duplicate comparisons

Canopy clustering is commonly paired with TF-IDF or Jaccard similarity on tokenized text fields as the cheap distance metric.

The foundational statistical process of identifying records across different datasets that refer to the same real-world entity when a reliable unique identifier is absent. Blocking serves as the computational efficiency backbone of record linkage, preventing the quadratic explosion of O(n²) pairwise comparisons.

• Deterministic linkage: Exact matching on a shared key (e.g., Social Security Number)
• Probabilistic linkage: Uses the Fellegi-Sunter model to calculate match weights based on attribute agreement patterns
• Without blocking, linking two datasets of 1 million records each would require 1 trillion comparisons

The initial retrieval phase in entity linking that produces a shortlist of possible knowledge base entries for a given textual mention. Blocking is the database-centric analogue of candidate generation in NLP pipelines.

• Uses surface form dictionaries to map mention strings to candidate entity IDs
• Employs approximate nearest neighbor (ANN) search over dense entity embeddings for fuzzy retrieval
• A poorly tuned candidate generation step that misses the true entity creates an irrecoverable error downstream

A string comparison technique that calculates similarity between two text strings to identify non-exact duplicates. Often used as the similarity function within a blocking key to handle dirty real-world data.

• Levenshtein distance: Minimum edit operations to transform one string into another
• Jaro-Winkler: Optimized for short strings like personal names, weighting prefix matches
• Phonetic algorithms (Soundex, Metaphone): Index by pronunciation to block names with spelling variations

A rigorous statistical framework formalized by Fellegi and Sunter that calculates match weights for record pairs based on agreement and disagreement patterns across multiple attributes. Blocking defines the initial search space over which these probabilistic models operate.

• M-probability: The likelihood that a matching attribute agrees for a true match
• U-probability: The likelihood of random agreement for a non-match
• The match weight is the log-likelihood ratio: log₂(m/u), summing across all fields

The specific application of record linkage techniques to find and merge duplicate records representing the same entity within a single dataset. Blocking is equally critical here to avoid comparing every record against every other record.

• Sorted neighborhood method: Sort records by a blocking key, then slide a fixed-size window to only compare nearby records
• Transitive closure: If A matches B and B matches C, then A, B, and C form a connected cluster
• Produces a golden record that consolidates the best attribute values from all duplicates

A set of cryptographic and encoding techniques that allow linkage of records across databases without revealing plaintext personally identifiable information (PII) to any party. Blocking must be adapted to operate on encoded data.

• Bloom filter encoding: Represents attribute values as bit vectors, allowing similarity computation via set-based metrics like Dice coefficient
• Phonetic blocking on encoded fields enables efficient comparison without decryption
• Critical for inter-hospital patient matching and cross-agency fraud detection under GDPR and HIPAA