Sort-Based Indexing

What if we could sort all records so that similar ones are nearby? We should compare only records that are close by position in the sorted array—for example, no more than the ten nearest neighbors per record, assuming that there are only a few duplicates per entity. That’s a computationally cheap approach to bringing down superfluous comparisons.

The key challenge here is figuring out how to sort in such a way that proximity translates to similarity that strongly correlates with actual matching likelihood.

When to use SN indexing

Sorted neighborhood (SN) indexing works as follows: first, pick any key attribute for sorting, such as customer_name, as in our example below. Second, rearrange records by the alphanumeric order of their sort key. Third, add each pair to the index where the records are at most $w$ positions apart, where the window size $w$ is up to us to choose.