Duplicate data is a well-known issue - one aspect of poor data quality - and there is more of it in most systems than we would imagine. It causes problems in accounting, in analytical reports (whether the data is presented in text or in fancy dashboards) and it damages relationships between organisation and their clients, when the organisation cannot find some of a client's transactions, for example.
We have seen many methods for identifying duplicate data, many of them using naïve or arbitrary approaches. The method described here is easy to use, effective and efficient. It is therefore low-cost. Knowing the state of your data is an important start; fixing it is another problem (which we will address in another article). If the amount of duplicate data is not too high, then the best way to fix it is one pair of records at a time.
In order to identify duplicate records, you must have a unique identifier for every record. You can then look for different identifiers that have important data values which are exactly the same, or very similar, or with one set of values that is a sub-set of the other.
"Exactly the same" is easy.
"Very similar" requires some "fuzzy-matching" capability.
"One set of values that is a sub-set of the other" refers to the situation where, for example, one record has first name, last name, address and mobile phone number, and the duplicate has the same first name, last name and address, but the mobile phone number is missing.
The most common place for duplication is in the data you keep for contacts. Often the same person will appear in your contact table more than once, with slightly different data values. We'll use a contact table as an example because contact data is very familiar to everyone - we all have to enter this data into forms frequently. Duplication can certainly happen for other objects in your database, objects that are not individual people. The same principles apply, but we will talk about personal contact data for individual people here, to give us concrete examples that should relate to data we all understand.
Data fields that are recorded in most contact systems are:
| Field | Example Population |
|---|---|
| last name | 99.9% |
| first name | 99.7% |
| address: town | 77% |
| email address | 76% |
| postcode | 73% |
| address: number and street | 73% |
| title | 61% |
| mobile phone number | 9% |
| middle initial | 3% |
The example population numbers show the percentage of records that have a value for this field in a system that we are currently working on. In the fields where the value is missing, it should be null in the database, but sometimes other conventions are used (unfortunately). The detailed profile of your data will be different, but this one is fairly typical. We will refer to these population values later.
Also, very importantly, we need the personal number for each contact in the system you are dealing with. This may be account number, National Insurance number, membership number, etc. The personal number must be a unique identifier for each contact; there should not be two or more people with the same personal number. If your system has multiple people with the same number, that should be easy to identify, like this (substitute your object names for the values in square brackets):
select [personal_identifier], count(*) from [contact] group by [personal_identifier] having count(*) > 1;
Proper relational databases make it very easy to ensure that the same identifier is not used for two or more different records (using primary keys or uniqueness constraints) so it is quite rare for this to happen. If it has happened in your data, then you need to fix this first, by untangling the data for the two people and recording it under two separate identifiers. What we are looking at in the rest of this article are cases where one person has two or more records, with different identifiers.
If we tried to find duplicates by comparing every record with every other record, this would rapidly become very expensive.
Suppose we have 1 million contacts.
We could take contact number 1 and compare it with each of the other contacts from number 2 to number 1 million.
We could then take contact number 2 and compare it with each of the other contacts from number 3 to number 1 million
then contact 3 compared from 4 to 1 million
then contact 4 from 5 to 1 million
and so on until we compare contact 999,999 with contact 1,000,000.
This would be 500,000,000,000 (500 billion) comparisons, and even for a modern powerful computer this would take a long time.
What we do instead, is to sort the data by one of the highly populated fields, say last_name, (ignoring case) and then compare adjacent pairs of records. The number of comparisons will be one less than the number of records.
Window Functions (sometimes described as "analytic functions") enable us to compare adjacent pairs of records. If you are not familiar with Window Functions, you can find them described in Relational Databases for Agile Developers on pages 185-192 and on the PostgreSQL website. The examples below should help to understand Window Functions too.
Fuzzy Matching tells us if two field values are similar, even if they are not exactly the same. We need to do this because data values (especially in contact data) are often entered inconsistently, with typing errors or different formatting. Have a look at this page in the PostgreSQL documentation, to see a few alternative fuzzy-matching functions. We have found the most useful of these functions to be the "Levenshtein edit distance". This was invented by the Russian mathematician Vladimir Iosifovich Levenshtein (Влади́мир Ио́сифович Левенште́йн) in 1965. (It isn't always the latest thing that is the most useful.)
The Levenshtein edit distance is the number of single-character edits needed to change one string into another. This is very good at picking up common typing errors like missing out one character or transposing two characters. A result of zero means that the strings are identical, low numbers mean they are very similar and therefore may represent duplicate records where there is a misspelling in one of them.
Examples:
levenshtein('banana', 'Panama') gives result: 2
levenshtein('pomegranate','Uzbekistan') gives result: 9
There are several examples, below, which show real duplicates and things that look like duplicates at first glance, but actually are genuinely separate records.
It is common for the same person to be entered into the system twice, with two identifiers. This is what we are trying to find. The details for each pair of duplicates, will usually not be exactly the same, so we have to find pairs that are very similar and therefore likely to be the same person.
Here's a simple version of the query we need:
Let's start with the section shown in yellow. This uses window functions to return records in the contact table in order of first name within last name. "lag" gives us the record before the current one, so we can compare the two.
If your data contains records that have been flagged as inactive, deceased, deduplicated (already), anonymised, or not relevant for a current round of deduplication for some other reason, exclude them at the end of the yellow section. Here is a where clause I used to do this in a real database:
where
a.statecodename = 'Active' and /* excludes: Inactive */
a.statuscodename = 'Active' and /* excludes: Inactive, Terminated and Deceased */
coalesce(a.fsdyn_additionalstatusreasonname, 'Unique') <> 'Duplicate' and
The blue section shows the calls to the
We return zero for a pair of values if one of the pair is null, because it often happens that a value (mobile phone number for example) is present in one of the pair and absent in the other. This gives us no information about whether these two records represent the same person or not, so we do not include this difference in the score.
The pink section is there so that we report each pair of values only once.
This is the simple version, and it has a couple of issues.
We are making the assumption that the last name is going to be reliable, especially in the first few characters. This is a reasonable assumption in most cases, but by no means all. I recently had my name spelled by a shop assistant as "Vallard" instead of "Ballard" when I was placing an order. This may have resulted in a duplicate record in the shop's customer database, and it would not be found by the query above.
[In all the examples, below,all personal data has beeen altered, so that the real people cannot be identified, but the distribution of results is just like the real data.]
Our simple query successfully finds many genuine duplicate contacts, like this:
contact_id | last_name | first_name | address_town | address_street | postcode | email_address | title | mobile_phone | house_number |
--------------------------------------+-------- --+------------+-----------------+------------------------+----------+------------------------------+-------+--------------+--------------+
3c849da5-48e5-e811-a96a-0022480130e2 | COLLINS | BRIDGETTE | BELFAST | FLAT 11A | BT1 2PA | | MRS | | |
918e3f63-28a3-e911-a978-002248014cda | COLLINS | BRIGETTE | BELFAST | FLAT A 11 COMPTON ROAD | BT1 2PA | col_brig@yahoo.co.uk | MRS | | |
and like this:
contact_id | last_name | first_name | address_town | address_street | postcode | email_address | title | mobile_phone | house_number |
--------------------------------------+-------- --+------------+-----------------+------------------------+----------+------------------------------+-------+--------------+--------------+
c4df577b-8b53-ec11-8f8e-000d3ad551c5 | SIMSON | KARYN | LONDON | FLAT 18 | SW15 2NX | simsonputney@gmail.com | | | |
0e01c8b1-0ce5-e811-a96a-0022480130e2 | SIMSON | KAREN | LONDON | FLAT 18, CASTLE HOUSE | SW15 2NX | imaginesimson@hotmail.co.uk | MISS | | |
but it also finds some groups of different people, who are not duplicates, as we can see here:
contact_id | last_name | first_name | address_town | address_street | postcode | email_address | title | mobile_phone | house_number |
--------------------------------------+-------- --+------------+----------------+------------------------+----------+------------------------------+-------+--------------+--------------+
372560e7-eae4-e811-a969-002248014cd6 | WILSON | MELANIE | MAIDSTONE | 27 NORTH WALLS | ME19 1DB | | MISS | | 27 |
8654328a-eee4-e811-a96b-00224801377b | WILSON | MELANIE | READING | 4 THE PLEASANCE | RG32 0RG | | MRS | | 4 |
bb5b05fb-f7e4-e811-a966-002248014cda | WILSON | MELANIE | BRISTOL | 35 GLENHURST ROAD | BS95 5HZ | melaniewilson@btinternet.com | MRS | | 35 |
62fc614b-48e5-e811-a966-002248014cda | WILSON | MELANIE | STOKE-ON-TRENT | 19 HILLSIDE AVENUE | ST2 8EZ | mlaw@kentforlife.net | MRS | | 19 |
9a1e1a05-03e5-e811-a970-002248014773 | WILSON | MELANIE | | | | mmello@mindspring.com | MS | | |
bc079cde-51f8-eb11-94ef-000d3ad67d2c | WILSON | MELANIE | IPSWICH | | | melwil@gmail.com | | | |
fd3eb5cc-48c6-eb11-bacc-000d3ad69b59 | WILSON | MELANIE | JOHNSTONE | HARBOUR ARCHITECTS | GL10 2EG | rock_on_melanie@hotmail.com | | | |
3a2badcf-2db4-eb11-8236-002248418b95 | WILSON | MELANIE | BIRMINGHAM | 13 AUSTIN ROAD | B13 1SJ | verylikealump123@hotmail.com | | | 10 |
The query took 10 seconds on a dataset of 860,000, so the performance is fine, but we don't want this level of false positives. These Melanie Wilsons are, clearly, not duplicates.
Notice that the way we decided if something was a duplicate or not, was to look at other significant contact fields. We can use these fields in our query to get more precise results, and many fewer false positives. The query is longer, but still has the same structure, so it is easy to add the extra lines for each extra field that we test.
[click on the image to download the code.]
Here are some results, all plausible duplicates, but the first two have quite a lot of missing data, so they would need to be checked before combining them.
contact_id_a | contact_id_b | last_name_a | last_name_b | first_name_a | first_name_b | address_town_a | address_town_b | address_street_a | address_street_b | postcode_a | postcode_b | email_address_a | email_address_b | title_a | title_b | mobile_phone_a | mobile_phone_b | house_number_a | house_number_b | levenshtein_score
--------------------------------------+--------------------------------------+-------------+-------------+--------------+--------------+----------------+----------------+------------------+------------------+------------+------------+-----------------------+-----------------------------+---------+----------+----------------+----------------+----------------+----------------+-------------------
8b907354-0e5f-ed11-9562-002248429643 | 94d8d697-845f-ed11-9562-0022484256b8 | ROBERSON | ROBERSON | HAYLEY | HAYLEY | | NORTHGATE | | 100 42TH AVE | | 98004-5136 | hroberson1086@msn.com | | | | | | | 100 | 0
4239f945-4ae5-e811-a966-002248014cda | e7ed2eba-19e5-e811-a96b-00224801377b | ROBBINS | ROBBINS | FREDERICK | FREDERICK | | CAMBRIDGE | | 26 ROYSTON ROAD | | CB32 6JS | fredrobbins@gmail.com | | | MR | | | | 26 | 0
eec87ec6-f3fb-e811-a96d-0022480140fe | f7f4bdc6-f3fb-e811-a972-002248014773 | ROBARTS | ROBARTS | MARJORIE | MARJORIE | BUCKINGHAM | BUCKINGHAM | WATERFORD LANE | WATERFORD LANE | MK7 6FN | MK76FN | | | | | | | | | 1
6d9958de-18e5-e811-a96b-00224801377b | 91f92047-6335-eb11-a813-000d3ad50753 | ROADS | ROADS | MARY | MARY | LONDON | LONDON | 8 MINSTER ROAD | 8 MINSTER ROAD | SW7 1GD | SW7 1GD | | roadsmary@gmail.com | MS | MRS | 07899373390 | | 8 | 8 | 1
7aa5284e-a5ec-ec11-bb3c-00224842b852 | 94b3f30d-16e5-e811-a96a-0022480130e2 | ROACH | ROACH | FELICITY | FELICITY | DURHAM | DURHAM | 10 BIRCH DENE | 10 BIRCH DENE | DH5 3EF | DH5 3EF | | felicityroach@hotmail.co.uk | | MRS | 01918243098 | | 10 | 10 | 0
87fdcbea-5417-ea11-a811-000d3a0ba026 | 9bdfa421-1de5-e811-a969-002248014cd6 | RIU | RIU | VITTORIA | VITORIA | WOODFORD GREEN | WOODFORD GREEN | 30 NEVILLE ROAD | 30 NEVILLE ROAD | IG2 7HS | IG2 7HS | | | | MS | | | 30 | 30 | 1
9bdfa421-1de5-e811-a969-002248014cd6 | c271b562-25e5-e811-a969-002248014cd6 | RIU | RIU | VITORIA | VITORIA | WOODFORD GREEN | WOODFORD GREEN | 30 NEVILLE ROAD | 30 NEVILLE ROAD | IG2 7HS | IG2 7HS | | | MS | MRS | | | 30 | 30 | 1
09d68ce2-09bd-e911-a98d-002248014cd6 | 267473e1-09bd-e911-a97d-00224801377b | RITCHIE | RITCHIE | SUSAN | SUSAN | LONDON | LONDON | 86 CHAUCER COURT | 86 CHAUCER COURT | SE14 3HB | SE141 3HB | | | | | | | 86 | 86 | 0
We still need to find those duplicates where the start of the last name is different between two duplicates. We can do this by changing the sort order in the window functions. Here we have changed it to town.
[click on the image to download the code.]
Here are some of the results:
contact_id_a | contact_id_b | last_name_a | last_name_b | first_name_a | first_name_b | address_town_a | address_town_b | address_street_a | address_street_b | postcode_a | postcode_b | email_address_a | email_address_b | title_a | title_b | mobile_phone_a | mobile_phone_b | house_number_a | house_number_b | levenshtein_score
--------------------------------------+--------------------------------------+-----------------+-----------------+---------------+---------------+----------------+----------------+-------------------------+----------------------+------------+------------+----------------------------+-------------------------+---------+---------+----------------+----------------+----------------+----------------+-------------------
2d86d877-feba-ec11-983f-6045bd0ffd3c | d71cecd7-e5ba-ec11-983f-6045bd0ff433 | BABESHA | BADESHA | KOMAL | KOMAL | BECKENHAM | BECKENHAM | 66 EAST WAY | 66 EAST WAY | BR3 4XT | BR3 4XT | | kmal@samovar.org.uk | | | | | 66 | 66 | 1
48579595-901a-ea11-a811-002248078004 | ee339173-b14c-ea11-a812-002248078004 | WALTER-CLARK | WEALTER-CLARK | ROBERT | ROBERT | BEDFORD | BEDFORD | 30 ABINGDON ROAD | 30 ABINGDON ROAD | MK45 1AF | MK45 1AF | | | | MR | | | 30 | 30 | 1
1957f2e8-13b3-e911-a97b-0022480130e2 | 695836ac-17e5-e811-a969-002248014cd6 | DE NIRO | DE-NIRO | MICHAEL | MICHAEL | BIRMINGHAM | BIRMINGHAM | 1 NEWTOWN ROAD | 1 NEWTOWN ROAD | B10 3PW | B10 3PW | | michaeldeniro@gmail.com | | MR | | | 1 | 1 | 1
695836ac-17e5-e811-a969-002248014cd6 | bd9364ec-13b3-e911-a981-0022480140fe | DE-NIRO | DE NIRO | MICHAEL | MICHAEL | BIRMINGHAM | BIRMINGHAM | 1 NEWTOWN ROAD | 1 NEWTOWN ROAD | B10 3PW | B10 3PW | michaeldeniro@gmail.com | | MR | | | | 1 | 1 | 1
105907d8-61ec-eb11-bacb-00224841ec92 | ebb01104-0036-ea11-a813-002248078004 | PREECE | PRICE | ELIZA | ELIZA | BRIGHTON | BRIGHTON | | 104 PILCHARD AVENUE | | BN1 5GD | | | | | | | | 104 | 2
01aa19b9-f6e4-e811-a970-002248014773 | a6e1e2c4-240e-ec11-b6e6-000d3ad674d1 | WARD | WOOD | PENELOPE | PENELOPE | LONDON | LONDON | THE ULTIMATE HANDBAG CO | | SW3 1SE | | | wood.penelope@gmail.com | MS | | 07774823568 | | | | 2
a847bbf6-31f9-e811-a96e-00224801377b | aa3f8dbc-08e5-e811-a969-002248014cd6 | MOYES | MOYSE | JULIAN | JULIAN | LONDON | LONDON | 22 FORBES ROAD | 22 FORBES ROAD | SW11 6RS | SW11 6RS | | | MR | MR | | | 22 | 22 | 2
0483d508-ed34-ec11-8c64-000d3a0af583 | bc725183-b86e-ea11-a811-000d3a0ba026 | PRASAD | RRASAD | PRIYA | PRIYA | | | 71C BUXTON ROAD | 71C BUXTON ROAD | GL3 5QU | GL3 5QU | priyaprasad@doctors.org.uk | | DR | | | | 71 | 71 | 1
You can see that there are differences between the two last names in every case. In the last case, even the first letter of the last name is different. But they are, clearly, duplicates. Our first query (ordered by last_name, first_name) missed these.
Each of these queries, using nine fields for comparison, with a table of 860,000 contacts, takes about 20 seconds to run. If we run just the first one of them (sorting by lastname, then first name) we find most of the duplicates. If we use other sort orders we will find a few more. We can sort by any of the fields we have identifiied. Postcode is particularly good, since a UK postcode identifies, on average, about 40 people. In our example dataset, though, the postcode is often missing, so that limits its effectivenesss.
We have selected rows where the
In a comparison with a commercial service:
We used PostgreSQL as our database, for several reasons, one of which is that it has a rich set of useful functions. When we wanted fuzzy-matching facilities, we had several choices from the functions that come with the product.
Microsoft Dataverse has duplicate detection facilities that are described here.
There are a lot of settings you can fiddle with in numerous web-forms, but the most sophisticated check seems to be to compare a number of first or last characters. Our solution is far more sophisticated thanks to the existence of the
Some other databases and programming languages do provide a
You can find code samples to implement a Levenshtein edit distance in many popular databases and languages. We did not look at these in detail because the function is in our database as standard.
We hope you find the code and descriptions provided here to be useful. You can contact us about any aspect of this.