# Fuzzy Matching - Performance and Clustering

Fuzzy matching is a very powerful technique for matching when the data might have problems, such as spelling errors or noise words.

With power comes a price - a lot of work must be done to do the matching. In particular, when a source record comes in, it must be compared against EVERY record in the target. This is because it must be scored against every record, then the highest scoring records are used.

This can become very expensive. If for example, there are 10,000 records in the source and 10,000 records in the target, there will need to be 10,000 x 10,000 = 100,000,000 source - target comparisons.

Inaportassists in avoiding this issue by providing clustering - grouping the records in the target into smaller groups or clusters. When a source record is matched, instead of scoring against every record in the target , it is scored against only one of the clusters.

For example, you might cluster the target based on the first letter of the target field. This means there would be one cluster for each first letter found in the target. Suppose the match is on the company name, as in the following table, and we cluster on the first character of the name:

Company Name | Cluster
--- | ---
Able | "A"
Acme Corp
Charlie Company | "C"
Dazzle inc | "D"
Dynamite Corp

When a source record is compared, we

1. get the first letter of its company name
2. find the cluster of target records that match
3. score the source record against the target records in the cluster only

For example, if the source record had the company name "Able Inc", it would be scored against only the two records in the "A" cluster, instead of all five records in the table.

If the incoming record does not fit into any of the clusters, it will be marked as "not a match" without any scoring.

### Advantage

Clearly, clustering has the potential to greatly reduce the number of scoring operations. As a score is a relatively costly operation, reducing the number can have a significant effect on the performance of the matching process.

### Disadvantage

If the clustering method is not carefully chosen, you may miss matches that should have been made. For example, If the incoming company name is "Bale", it is likely that it really should be "Able", but because of the clustering it would not be matched with the "A" cluster and so would be marked as not a match.