Fitjoin

Fitjoin is a family of algorithms designed to perform similarity joins between two datasets by identifying pairs whose similarity meets a predefined threshold. It is commonly used in tasks such as deduplication, entity resolution, and data integration where exact matches are too costly to compute for all pairs.

The core idea is to prune the search space before performing expensive similarity calculations. This is achieved through filtering and indexing: features are extracted, often tokenized items or attributes, and an index is built to connect records with overlapping features. Candidate pairs are generated from these overlaps; many pairs are discarded early if their partial information cannot reach the threshold.

A typical fitjoin pipeline consists of candidate generation and verification. In the candidate generation stage, lower bounds on similarity are computed from partial data, sometimes using sorted lists, signatures, or sketches. In the verification stage, the exact similarity is computed for surviving candidates to determine if they pass the threshold.

Variants of fitjoin support different similarity measures, including Jaccard, cosine, and Dice coefficients, as well as distance-based metrics. Some implementations extend to streaming data or high-dimensional sparse datasets and may combine with locality-sensitive hashing to accelerate candidate generation.

Applications include de-duplication in databases and data warehouses, record linkage across disparate sources, near-duplicate detection in document collections, and catalog reconciliation in e-commerce and digital libraries. Related concepts include similarity join, entity resolution, and locality-sensitive hashing, which provide complementary techniques for scalable matching tasks.