When working on the common data engineering problem of identifying which records across two different databases correspond to the same real-world entity — a process known as record linkage — one inevitably runs into issues associated with the worst-case quadratic complexity of doing pairwise comparisons. To understand where things can get computationally heavy, let’s look at the standard workflow for the record linkage (RL) process:
From domain knowledge, we can usually design a reasonable Comparison function that measures how similar two records are. If we can afford to do so, we want to compare all pairs of records. But in many practical applications, we can’t afford to do that O(n^2) operation if n is larger than, say, tens of thousands. The aim of the Blocking step in the RL process is to find ways to cheaply and efficiently remove candidate record pairs that are obviously not matches, in the hope that we can save massive amounts of compute and allow record linkage to actually scale.
How Blocking Helps: Here’s a simple example to illustrate how blocking can help.
There are six different address records here. If we don’t do any blocking, we have to perform 15 pairwise comparisons. We can introduce a simple blocking key that picks out the street number, street name, and either postcode or the state name. That gives us the diagram on the right, with all the records grouped into two different blocks. Only 7 comparisons are now required.
Practical Blocking Strategies: Now that we have the basic idea, let’s look at the problem of designing good blocking keys on massive, messy datasets. When designing blocking keys, we generally look for four properties:
- the keys have good data quality on common measures (i.e. not too many missing values and good data accuracy);
- the keys are relatively stable over time (e.g. date of birth is preferred over age);
- the keys can take on a large number of possible values (e.g. gender is not a good candidate);
- the keys’ frequency distribution has high entropy (i.e. the frequency distribution as close to uniform as possible).
In the special case where a unique entity identifier (ID) is available, that ID is a perfect blocking key. The key issue we face in practice is that there are usually no unique entity IDs available for matching. In that scenario, what strategies can we use to find good blocking keys?
There are two. The first strategy is to try and find an entity’s unique signature, a property that can be used to uniquely identify that entity in a database. The second blocking strategy is to use approximation algorithms to find likely nearest neighbours. The idea is to use an O(n log n) algorithm to approximate an O(n^2) operation. Let’s look at how these blocking strategies solve the scaling problem in three distinct modern architectures.
Scaling Fraud Detection with Probabilistic Signatures
Consider the data matching system used by AUSTRAC and Services Australia to combat welfare and tax fraud, as described in this paper. The data volumes involved are large: 3 to 5 million entities from Services Australia must be matched against 1-3 billion transaction records from AUSTRAC. A naive O(n^2) algorithm here would bring even the largest parallel databases to their knees.
Because no unique IDs exist between these systems, the blocking strategy relies on finding naturally occurring “probabilistic signatures” in records, particularly within raw, unstructured textual data. The system enumerates different token combinations to generate candidate blocking keys. The trick is filtering out keys that recur too often. Here’s a simple example to illustrate the basic idea.
In this case, using “VIC 3000” as a blocking key is practically useless because it groups thousands of Melbourne addresses into a single large block in each database. However, the token combination “513 Elizabeth” is a good candidate signature because it will only group a handful of highly relevant records together. By finding these rare signatures and only perform pairwise comparisons on records that match on these signatures, the system effectively bypasses the O(n^2) bottleneck and allow large-scale data matching to be done to support fraud detection activities.
We next look at using a signature-based blocking technique to do (probabilistic) deduplication, a special case of record linkage, in internet-scale data.
Deduplication in the Curation of Training Data for LLMs
To really understand how foundational AI models are trained from scratch, one has to go beyond the open-weight models to the fully open-source models, where not only is the weight of the model published, but the full training data and the source code of curating data and training the model are published as well.
There are two large projects that produce fully open-source models: one is the OLMO project at the Allen Institute of AI, and the other is the Apertus project at the Swiss Institute of AI. The following Gemini-generated diagram shows the data-integration pipeline for creating the Dolma dataset, an open corpus of 3 trillion tokens, used to train the OLMo language model.
The first two steps of the pipeline is about ingesting raw data from the internet and extracting contents from them. The record linkage step happens in step 3, but what we are dealing with here is the special case of using record linkage to find and remove duplicates. Finally, data fusion happens in step 5 of the pipeline, where we try to compute the right mix of data that yields well-balanced models.
In the context of this post, let’s look at that deduplication step in more details. At the scale of 3 trillion tokens, doing all pairs of string comparisons is completely out of the question and blocking is strictly necessary. For that, engineers use cryptographic hash functions to turn text strings into bit arrays, known as Bloom filters, which act as the blocking keys. We can understand how it works with a simple example.
In the diagram, we have two hash functions h1 and h2 that maps a string into a number between 0 and 5. Given the string “apple”, let’s say h1 maps it to 0 and h2 maps it to 5. We can use that to construct a 6-dimensional bit array with 1 set at the 0-th and 5-th location, and 0 otherwise. The other strings like “banana” are processed in a similar way. The bit arrays that are generated in this way can serve as good fingerprints / signatures of records, if we chose the dimension of the bit array and the number of hash functions appropriately. To do deduplication exactly, one can now proceed as usual and compare all the records in each block to find duplicates.
In practice, for very large datasets, this is still too expensive to do. So people end up settling for probabilistic deduplication, where they just assume records in the same block are the same (without comparing them), and they produce one single global bloom filter by adding all the individual bloom filters. By sacrificing exactness and accepting a few false positives, one can achieve constant-time lookups and save roughly 30x on memory in the case of Dolma.
The next example moves beyond signature-based blocking techniques to look at efficient approximate nearest neighbour algorithms.
Semantic Blocking in Vector Databases
Blocking also plays an important role in modern vector databases, where we use Large Language Models to map text records into numerical vector embeddings. Let’s look at another simple example to draw out the key concepts.
Suppose we have two datasets of text records, and we want to compare how similar the text records are, not just at a syntactic level but also at the semantic level. A good way to do that is to use a large language model to generate vector embeddings of these text records. Here, for example, “Apple laptops have good reputation” is mapped into a vector of 4 numbers (0.1, 0.2, 0.9, 0.8), and “Apples are cheaper than oranges” is mapped to another vector (0.5, 0.4, 0.4, 0.5).
Given these vector embeddings, we want to find similar text records by putting similar vector embeddings into the same block, like the following.
Here, for example, the two text records “Apple laptops have good reputation” and “Mac computers are well-liked” are mapped by the AI model to two vectors that are close by, and we want to put them in the same block. Similarly for the bottom two records.
The problem is, finding these nearby vector embeddings and putting them in blocks in an optimal way is an expensive O(n^2) computation. To scale this, modern vector databases rely on approximate nearest neighbour algorithms that scale at O(n log n). As one can imagine, new algorithms for solving the approximate nearest neighbour problem are constantly being invented. The latest state-of-the-art is the Hierarchical Navigable Small Worlds algorithm. I won’t go into the details of how it works here, but the key thing for readers to understand is that these newer algorithms are now implemented in commercial-grade vector databases that are widely available.
And vector databases are now a standard component in so-called Retrieval Augmented Generation architectures. If you are working as a data scientist or data engineer in industry today, it’s most likely that you will be asked to build AI systems with a locally hosted large-language model connected to the company’s own private database. A Retrieval Augmented Generation architecture is how one would build such a system, and its key components are shown on this Gemini-generated diagram.
In Conclusion
I hope I have given readers a sense of the sometimes under-appreciated blocking step in data matching pipelines. The power of modern data systems isn’t just in how fast they can compare records, it’s also in the clever blocking algorithms they use to avoid comparing them in the first place.
