Finding near-duplicates with Jaccard similarity and MinHash
blog.nelhage.com
Finding near-duplicates with Jaccard similarity and MinHash
1–10 of 39 posts
Re: Finding near-duplicates with Jaccard similarity and MinHash
#2I worked with a client that implemented their own Python version of this to deduplicate citizen entries in a big french gov database. It worked well.
Of course, nowaday I would probably just tell them to use datasketch (https://pypi.org/project/datasketch/).
With this trip to memory lane, I looked around a little, and noticed people are still creating new stuff on the topic. E.G:
https://pypi.org/project/rensa/
Which is basically a more specialized but faster version of datasketch minhash, written in rust, with a little python on top.
Re: Finding near-duplicates with Jaccard similarity and MinHash
#3I had to do this with sport teams but I used levenshtein for the names. I ended up creating a vector with other data (country, gender) and using that vector to calculate the distance (similarity).
Re: Finding near-duplicates with Jaccard similarity and MinHash
#4I worked with a client that implemented their own Python version of this to deduplicate citizen entries in a big french gov database. It worked well. Of course, nowaday I would probably just tell them to use datasketch ( https://pypi.org/project/datasketch/ ). With this trip to memory lane, I looked around a little, and noticed people are still creating new stuff on the topic. E.G: https://pypi.org/project/rensa/ Whi…
For deduplicating people, the Fellegi Sunter model is also a powerful approach. Splink[0] is a free Python library that implements this for big datasets. Probably you could combine parts of both approaches as well. Full disclosure: I am the lead author.
I've also written up some interactive tutorials on how the method works [1] if anyone's interested
[0]https://github.com/moj-analytical-services/splink [1]https://www.robinlinacre.com/intro_to_probabilistic_linkage/
Re: Finding near-duplicates with Jaccard similarity and MinHash
#5I have this problem right now in postgres. I have 600000 feed_items with the schema (feed_item_id uuid, author varchar, content text, guid varchar, link varchar, title varchar, summary text, feed_id integer) The content and summary columns especially for some of the news items are highly similar but not equal. For any given 2 such news items, I am trying to cut them down to 1. Any ideas?
Re: Finding near-duplicates with Jaccard similarity and MinHash
#6I have this problem right now in postgres. I have 600000 feed_items with the schema (feed_item_id uuid, author varchar, content text, guid varchar, link varchar, title varchar, summary text, feed_id integer) The content and summary columns especially for some of the news items are highly similar but not equal. For any given 2 such news items, I am trying to cut them down to 1. Any ideas?
One useful technique here could be to use text embeddings and cosine similarity:
https://simonwillison.net/2023/Oct/23/embeddings/
Re: Finding near-duplicates with Jaccard similarity and MinHash
#7I worked with a client that implemented their own Python version of this to deduplicate citizen entries in a big french gov database. It worked well. Of course, nowaday I would probably just tell them to use datasketch ( https://pypi.org/project/datasketch/ ). With this trip to memory lane, I looked around a little, and noticed people are still creating new stuff on the topic. E.G: https://pypi.org/project/rensa/ Whi…
For deduplicating people, the Fellegi Sunter model is also a powerful approach. Splink[0] is a free Python library that implements this for big datasets. Probably you could combine parts of both approaches as well. Full disclosure: I am the lead author. I've also written up some interactive tutorials on how the method works [1] if anyone's interested [0] https://github.com/moj-analytical-services/splink [1] https://w…
Interesting.
What would you say are the main differences with other approaches?
Re: Finding near-duplicates with Jaccard similarity and MinHash
#8Earlier quoted context omitted.
For deduplicating people, the Fellegi Sunter model is also a powerful approach. Splink[0] is a free Python library that implements this for big datasets. Probably you could combine parts of both approaches as well. Full disclosure: I am the lead author. I've also written up some interactive tutorials on how the method works [1] if anyone's interested [0] https://github.com/moj-analytical-services/splink [1] https://w…
Interesting. What would you say are the main differences with other approaches?
The Fellegi Sunter model is able to estimate the importance of different types of information from the data itself (i.e. unsupervised learning).
For instance, a match on a date of birth column lends a greater weight of evidence in favour of a match than a match on first name (since dob has higher cardinality).
The method is also able to estimate weights for fuzzy matches (how much evidence in favour of a match is close match on dob with one character difference), and also how much evidence against a match a mismatch is.
For instance, if you have very high data quality on gender, then a match on gender doesn't tell you much, but a mismatch on gender is quite strong evidence against the idea two records match.
I have a blog post here that delves into this a bit more: https://www.robinlinacre.com/fellegi_sunter_accuracy/
Re: Finding near-duplicates with Jaccard similarity and MinHash
#9Earlier quoted context omitted.
Interesting. What would you say are the main differences with other approaches?
The Fellegi Sunter model is able to estimate the importance of different types of information from the data itself (i.e. unsupervised learning). For instance, a match on a date of birth column lends a greater weight of evidence in favour of a match than a match on first name (since dob has higher cardinality). The method is also able to estimate weights for fuzzy matches (how much evidence in favour of a match is clo…
Ok, so you get better accuracy if you datasets have obviously weighted fields. Do you pay that in perfs, and if yes how much?
Re: Finding near-duplicates with Jaccard similarity and MinHash
#10Earlier quoted context omitted.
The Fellegi Sunter model is able to estimate the importance of different types of information from the data itself (i.e. unsupervised learning). For instance, a match on a date of birth column lends a greater weight of evidence in favour of a match than a match on first name (since dob has higher cardinality). The method is also able to estimate weights for fuzzy matches (how much evidence in favour of a match is clo…
Ok, so you get better accuracy if you datasets have obviously weighted fields. Do you pay that in perfs, and if yes how much?
The performance is pretty good because the prediction is ultimately just adding up match weights. Much of the performance is dictated by
(1) The blocking approach you choose (how wide you cast the net in searching for matches. This is actually somewhere were minhash can be used in conjunction
(2) whether you choose to use complex fuzzy matching functions and how many - this is chosen by the user.
There's some benchmarking results here: https://www.robinlinacre.com/fast_deduplication/
Overall it's an approach which makes a pretty good trade off between speed and accuracy. That's why it's used by many national stats institutes (UK, US, Aus, Germany etc.) - because it's capable of working on country-population sized datasets.