Deduplication of complex records / Similarity Detection

I’m working on a project that involves records with fairly large numbers of fields (~15-20) and I’m trying to figure out a good way to implement deduplication. Essentially the records are people along with some additional data. For example, the records are likely to include personal information like first name, last name, postal address, email address, etc. but not all records have the same amount of data.

Currently records are stored in a RDBMS (MySQL) and I want to detect duplicates on insertion and still have them inserted but flagged as a duplicate. It needs to be fast as I need to provide feedback as to if it is a duplicate or not in real time. The dataset is large (millions of records).

I’ve considered the following options but I’m not sure which is best/if they are better options available:

Use MySQL’s built in fulltext search and use fuzzy searching. Major issue with this is that is seems slow, only the latest version supports fulltext indexes with InnoDB (alternative engine is MyISAM which is not good and critically does not support transactions) and fuzzy searching alone does not seem the best method for similarity detection.
Use simhash or similar. Issue with this is that I’d also like to be able to detect synonyms which I don’t see how simhash handles this. For example, address might be: “Some Road” or “Some Rd.” and names might be: “Mike” or “Michael”
Index the data using an Apache Lucene derivative (elasticsearch/solr/etc) and perform a query that would likely return numerous results.

In terms of using Apache Lucene I’ve been reading about similarity detection and using cosine similarity to produce a value from 0 to 1 from the term frequency vectors that lucene stores. I could apply this to the results from the lucene query and check to see if any of the results are above a certain threshold. My concern about this is how relevant the cosine similarity would be for the type of data I’m storing, i.e a number of fields with either single or a small number of words compared to calculating the cosine similarity of a comparison of some large text document.

Basically, I’m wondering what is the best way to deduplicate this type of data (or put alternatively, detect similarities with this type of data)?

There is no silver bullet for de-duplication. You should concentrate first on normalization (from a pattern sense, not 3NF) and standardization. This gives you some kind of level playing field from which to start making comparisons.

To achieve this, you need to apply the standardization techniques that work for each type of data. Standardizing address data is a totally different problem domain than standardizing given names. Most of these data standardization problem domains are much too complex to attempt to solve yourself. Consider buying 3rd party software that does postal address validation and standardization and one which does name standardization.

For things like e-mail addresses or phone numbers, you can probably roll your own, since these are relatively straight-forward by comparison.

Once you’ve got your data components properly standardized, then you can worry about what’s better: fuzzy match, Levenshtein distance, or cosine similarity (etc.)

You’re best to consider matching like sub-elements rather than trying to take records as a whole. Then look at how many sub-elements reasonably match. Two identical names with different email addresses and mailing addresses are a very weak match. Two nearly identical names with nearly identical mailing addresses with one record missing the email address is probably a pretty strong match.

For many deduplication techniques, standardization of data is, as Joel Brown pointed out, very important. But you may be able to get by without it if you use minhash.

You still want to normalize data as much as you can: e.g. case and whitespace normalization, ignoring punctuation in addresses, etc. You can even normalize synonyms if you have known synonym groups; so “Mount Saint Helens Street” becomes “mt st helens st” (introducing ambiguity like this doesn’t normally harm the precision of your results, but it improves recall).

Names and addresses are still likely to differ, with spelling mistakes, possible changes to ordering, and perhaps inclusion of extra items e.g. middle names, or different region names. That doesn’t have to be a problem.

Minhash generates multiple hashes per record, based on features. In many implementations people just throw all features into a single minhash generator, and get, say, 50 hashes out as a result; but in your case you may want to split this up. Take all the name fields, generate, say, 7-character shingles for each of them, and throw those shingles into one minhash generator which spits out, say, 5 hashes. Take all the postal/physical address fields and do the same using another minhash generator, which spits out, say, 15 hashes. Derive, say, 3 hashes from the email address on its own. And so on.

The number of hashes you keep for each type of information can be tuned depending on how important that info is for determining a duplicate, and how likely the field is to have not been filled in. The most reliable data should have the most hashes allocated to it.

Finding near duplicates is then fairly simple. It is rather slower than simhash and can take up a bit of memory, because it has to sift through large numbers of results, counting shared hashes for each one. In the worst case, a few minhashes may be selected from very generic parts of the record, such as “@gmail.” in the email address, and may be present in hundreds of thousands or even millions of other records. But the beauty of minhash is that it allows you to find results that are not just 4 or 5% different, but 20%, 40%, or as much as you like, really.

(You can somewhat defeat these “generic” minhashes by using the same technique as synonym replacement, and replace very common generic strings such as “@gmail.com” with shorter encoded placeholders such as “@G!”. That’s shorter than your 7-character shingle, so it will never form a shingle on its own.)

There are some variants on minhash that improve results through requiring fewer hashes to represent the same data (see https://stackoverflow.com/questions/27712472/choosing-between-simhash-and-minhash-for-a-production-system), but if the size of each record is small this may not give significant benefits. You may already be down to 30 or 40 hashes per record (and 32-bit hashes may be sufficient). If you haven’t already mitigated the “generic minhashes” problem, locality sensitive hashing (LSH) can help a lot; though this reduces precision of similarity estimates.

make the email address as primary key, as always email address is unique. so that redundant data will not be there.

Else if you have address and name of the person, then you can use both to check of duplicates

Filed under: softwareengineering - @ 08:06

Thẻ: algorithms, data, database, design

Deduplication of complex records / Similarity Detection

I’ve considered the following options but I’m not sure which is best/if they are better options available:

Use MySQL’s built in fulltext search and use fuzzy searching. Major issue with this is that is seems slow, only the latest version supports fulltext indexes with InnoDB (alternative engine is MyISAM which is not good and critically does not support transactions) and fuzzy searching alone does not seem the best method for similarity detection.
Use simhash or similar. Issue with this is that I’d also like to be able to detect synonyms which I don’t see how simhash handles this. For example, address might be: “Some Road” or “Some Rd.” and names might be: “Mike” or “Michael”
Index the data using an Apache Lucene derivative (elasticsearch/solr/etc) and perform a query that would likely return numerous results.

Basically, I’m wondering what is the best way to deduplicate this type of data (or put alternatively, detect similarities with this type of data)?

For things like e-mail addresses or phone numbers, you can probably roll your own, since these are relatively straight-forward by comparison.

Once you’ve got your data components properly standardized, then you can worry about what’s better: fuzzy match, Levenshtein distance, or cosine similarity (etc.)

For many deduplication techniques, standardization of data is, as Joel Brown pointed out, very important. But you may be able to get by without it if you use minhash.

make the email address as primary key, as always email address is unique. so that redundant data will not be there.

Else if you have address and name of the person, then you can use both to check of duplicates

Filed under: softwareengineering - @ 08:06

Thẻ: algorithms, data, database, design

Thiết kế website giá rẻ

Danh mục

Deduplication of complex records / Similarity Detection

Deduplication of complex records / Similarity Detection