K-Nearest Embeddings Blocking

Indexing in entity resolution helps address the main computational challenge, which is the large number of potential candidate pairs. Traditional methods rely on the following:

• Lexical matching (also known as exact matching), such as SB

• Lexical sorting, like in SN

Both methods work within the original feature space. Let’s explore how to measure similarity in a vector space and how to complement lexical by semantic search.

Concept

Let $r_1,\ldots,r_n$​ denote our dataset of size $n$ we aim to deduplicate. Indexing is about selecting match candidates from all possible pairs $p_{ij}=(r_i,r_j)$, preserving most matches while removing many no-matches. The indexing algorithm must be very efficient because the number of all pairs grows quadratically with $n$.

In other words, an indexer is a cheap matcher optimized for high recall, while precision is irrelevant. The indexers we discuss here have costs that are linear in $n$ (cheap enough). The figure below illustrates the construction: