Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Finding near-duplicates with Jaccard similarity and MinHash

blog.nelhage.com

Post reply on HN
Print view View original

21–30 of 39 posts

Re: Finding near-duplicates with Jaccard similarity and MinHash

#21

Post by motohagiography »

there was a really simple string sort by similarity oneliner I can't find in my history, but the basic idea was to take a wordlist, split each word in half, reverse the halves, concatenate them back together, sort the resulting strings, then flip the strings back to their original words.

this simple shuffle was a poor man's similarity sort that I used to find sound-alike words. the thing about the quality of similarity is that it's hard to know for sure if it worked, but this was sufficient.

Re: Finding near-duplicates with Jaccard similarity and MinHash

#22

Post by ashvardanian »

Hashing or tiny neural nets combined with a Vector Search engine with Tanimoto/Jaccard is a very common deduplication strategy for large datasets. It might be wiser than using linear-complexity MapReduce operations.

There is a nice Google project using 0.5 M parameter RETSim model and the USearch engine for that: https://github.com/google/unisim

Re: Finding near-duplicates with Jaccard similarity and MinHash

#23

Post by carnewal »

As I got into Minhash & its variants I found it hard to wrap my head around this, so I'm building an online visualizer

https://websla.sh/tools/minhash

It's not really complete, I'd like to show Jaccard Similarity calculations among other things, but this already allows you to enter multiple strings and see with your own eyes what a "minhash" actually is.

Re: Finding near-duplicates with Jaccard similarity and MinHash

#24

Post by a-dub »

a little backstory (that seems to be missing from the blog post). this is a technique that was invented in the early days of google for deduplicating the crawl set (turns out that building an llm and building a plain ol' web text index look awfully similar; i wonder why that is?!). you can read about it in depth in jeffrey ullman's free book "mining massive datasets" which describes many of the really cool and impressive techniques that were used to prepare an index build for the entire internet when such a thing was really hard.

you can find the relevant material for free by searching "chapter 3 pdf mmds ullman"

enjoy!

edit: oh no! i'm wrong! according to wikipedia it was invented at dec for altavista. https://en.wikipedia.org/wiki/MinHash either way there's a nice description in the ullman book and they do describe how it was used at google as well.

Re: Finding near-duplicates with Jaccard similarity and MinHash

#25

Post by JimmyRuska »

RobinL wrote: post #8
BiteCode_dev wrote: post #7

Earlier 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…

It doesn't sound like the approaches are incompatible. You can use minhash LSH to search a large set and get a top-k list for any individual, then use a weighted average with penalty rules to decide which of those qualifies as a dupe or not. Weighted minhash can also be used to efficiently add repeats to give some additional weighting.

Re: Finding near-duplicates with Jaccard similarity and MinHash

#28

Post by gpderetta »

vivzkestrel wrote: post #5

I 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?

You can use min hash to avoid the full O(N^2) distance matrix, but with just 600000 items you might just brute force compute the full matrix for simiplicity. What's your time budget?

Re: Finding near-duplicates with Jaccard similarity and MinHash

#29

Post by gpderetta »

swasheck wrote: post #15
RobinL wrote: post #6

Earlier quoted context omitted.

One useful technique here could be to use text embeddings and cosine similarity: https://simonwillison.net/2023/Oct/23/embeddings/

love this and have been using tf/idf for embeddings and various measures of similarity for some personal pet projects. one thing i came across in my research is that cosine similarity was more useful for vectors of different lengths and that euclidean distance was useful for vectors of similar length but simon alludes to a same-length requirement. i’m not formally trained in this area so i was hoping someone could sh…

You can use cosine similarity with embedding vectors of different lengths (or better, the vectors have all the same length, but they are sparse with most components being 0).

Re: Finding near-duplicates with Jaccard similarity and MinHash

#30

Post by gpderetta »

derefr wrote: post #20

As a document clustering / dataset deduplication technique, how well does "throwing ML at the problem" (e.g. using a pre-trained LLM encoder to generate vector embeddings of your documents, and then sticking those vectors into a vector DB and doing k-means to cluster the vectors) compare, quality-wise and performance-wise, to these simpler discrete-algorithm methods?

Using an LLM is just one of the ways to generate embedding. To do k-means you still need to pick a distance function, like jaccard; k-means is probably not ideal for near duplicates, and you can use min-hash to speed up k-means as a pre-pass.

I don't think the vector DB adds much. You could use it to speed up the lookup of the min-hash sketches if you have hundreds of millions of documents, but it is probably overkill.

Post reply on HN