Sorted Neighborhood Method

The sorting key is the single most critical determinant of SNM performance. It is a composite attribute or function of attributes selected to cluster potential matches nearby in the sorted list.

• Objective: Place true matches within a close proximity to ensure they fall inside the same window.
• Common choices: Surname, ZIP code, or a phonetic encoding like Soundex.
• Risk: A poorly chosen key scatters true matches, causing them to fall outside the window and drastically reducing recall.

The window size (W) defines a fixed range of records ahead of the current record that will be compared. If W=10, the current record is compared only with the next 10 records in the sorted list.

• Complexity Reduction: Reduces comparisons from O(n²) to O(nW), making it linear with respect to the dataset size.
• Trade-off: A larger window increases computational cost but captures matches separated by greater distances in the sort order.
• Typical values: Often set between 10 and 50, depending on dataset density.

To mitigate the risk of missing matches due to a single imperfect sorting key, SNM is often executed in multiple independent passes.

• Mechanism: Each pass uses a different sorting key (e.g., first pass on surname, second pass on ZIP code).
• Transitive Closure: The results from all passes are merged using transitive closure to consolidate match clusters.
• Benefit: Dramatically improves recall by ensuring that if a match is missed by one key, it is likely caught by another, without requiring a prohibitively large single window.

After pairwise comparisons within the window, the resulting match pairs form a graph. Transitive closure is applied to merge these pairs into connected components representing unique entities.

• Logic: If record A matches B, and B matches C, then A, B, and C are all resolved into a single entity cluster.
• Consistency: This step is crucial for deduplication, ensuring that the final output is a set of distinct entities rather than just a list of pairwise links.
• Application: Essential for merging results from multi-pass SNM executions.

SNM transforms the computational complexity of record linkage from quadratic to near-linear.

• Sorting Phase: O(n log n) complexity, where n is the number of records.
• Comparison Phase: O(nW) complexity, where W is the fixed window size.
• Total Cost: O(n log n + nW). Since W is a small constant, this is effectively O(n log n), making it scalable for datasets with millions of records.
• Contrast: Naive all-pairs comparison is O(n²), which becomes computationally intractable for large datasets.

In Privacy-Preserving Record Linkage (PPRL), the standard SNM is adapted to operate on encoded data. Since plaintext sorting keys are not available, private blocking techniques are used.

• Private Blocking: Uses techniques like Locality-Sensitive Hashing (LSH) or Bloom Filter Encoding to generate privacy-preserving blocking keys.
• Adaptation: Records are sorted by these encoded keys, and the sliding window is applied over the encoded representations.
• Goal: Maintains the efficiency of SNM while ensuring that no plaintext information is leaked during the blocking phase.

Health information exchanges (HIEs) use SNM to link patient records from disparate hospital systems without exposing plaintext identifiers. By sorting on a phonetic encoding of patient names or a Bloom filter-encoded composite key, SNM enables the creation of a master patient index.

• Challenge: Matching millions of records with typos and missing data.
• Solution: A sliding window of size w=20 over a sorted list of Double Metaphone encodings catches spelling variations.
• Outcome: High recall linkage while maintaining differential privacy guarantees on non-matching records.

Financial institutions deploy SNM to identify customers appearing across multiple sanctioned-party watchlists. The method sorts records by a cryptographic longterm key (CLK) derived from entity names and domiciles.

• Process: Records are sorted by the CLK, and a window slides to compare only adjacent blocks.
• Key Insight: Money launderers often use slight name variations; SNM's fuzzy matching within the window catches these without comparing every record.
• Result: Drastically reduced false negatives in sanctions screening while keeping raw watchlist data private.

Statistical agencies use SNM to deduplicate census responses where citizens may have submitted multiple forms. The blocking key is often a TF-IDF weighted combination of address and date-of-birth tokens.

• Technique: Records are sorted by the blocking key, and a Felligi-Sunter probabilistic model scores pairs within the window.
• Why SNM: A naive comparison of 300 million records is computationally impossible. SNM with a window of w=30 makes the problem tractable.
• Privacy: When combined with secure multi-party computation, the sorting and comparison can occur on encrypted data.

Pharmacovigilance databases use SNM to link spontaneous adverse event reports from doctors, patients, and literature to detect safety signals. The sorting key is a MinHash signature of the drug name and reaction description.

• Challenge: The same drug may be reported under brand, generic, or misspelled names.
• SNM Application: Sorting by MinHash clusters similar reports, and the sliding window compares only these clusters.
• Benefit: Early detection of drug safety issues without centralizing sensitive patient narratives from multiple pharma companies.

Investigative agencies link suspects across fragmented intelligence databases using SNM on hardened identifiers. The blocking key is a salted Bloom filter of the suspect's alias and physical descriptors.

• Constraint: Databases cannot be shared between jurisdictions.
• Architecture: Each agency sorts its local database on the Bloom filter key, and a private set intersection cardinality (PSI-CA) protocol checks for matches within the sliding window.
• Outcome: Cross-jurisdictional linkage without revealing non-matching suspect identities.

Global retailers merge customer profiles from e-commerce, in-store POS, and loyalty programs using SNM. The sorting key combines Jaro-Winkler distance on names with geohashed addresses.

• Problem: A single customer may exist as 'Bob Smith', 'Robert Smith', and 'R. Smith' across systems.
• SNM Strategy: Sort by the phonetic encoding of the last name and zip code. A window of w=15 captures all variations.
• Result: A unified golden record for personalized marketing without exposing raw PII to the linkage engine.