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

31–39 of 39 posts

Re: Finding near-duplicates with Jaccard similarity and MinHash

#31

Post by fantispug »

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?

I have seen it work better than LSH.

Each time you embed a document you search for approximate nearest neighbours before adding it, so it is O(N) like MinHash. Vector indexes like HNSW and PQ have better performance/quality tradeoffs than SimHash LSH which is the analogue of MinHash for cosine distance.

The quality depends on what you mean by near duplicate and the embedding model you use. Current models work well, and if you have labelled data you can fine tune them to be better.

The main drawback is the additional cost of embedding all the documents, especially for longer documents. But this cost has dropped really quickly with smaller models, better optimisations, and faster hardware.

Re: Finding near-duplicates with Jaccard similarity and MinHash

#32

Post by ColinWright »

In case the author is following this:

Typo:

It’s worth noticing that this definition is not in general transitive: we may well have three documents A,B,C such that S(A,B)≥S_{crit} and S(B,C)≥S_{crit} but S(A,B)That last S(A,B) should be S(A,C).

(Unless I'm very much mistaken ... and I could be)

Re: Finding near-duplicates with Jaccard similarity and MinHash

#33

Post by derefr »

fantispug wrote: post #31
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?

I have seen it work better than LSH. Each time you embed a document you search for approximate nearest neighbours before adding it, so it is O(N) like MinHash. Vector indexes like HNSW and PQ have better performance/quality tradeoffs than SimHash LSH which is the analogue of MinHash for cosine distance. The quality depends on what you mean by near duplicate and the embedding model you use. Current models work well, a…

If this is true, then why do you think that — as the OP article states — the developers of GPT3 chose to use non-ML-based techniques to deduplicate their dataset, when they would be the most equipped to use ML-based approaches?

Just the pure compute cost of needing to run an ML encoder over petabytes of data?

Or maybe because for their use-case — eliminating redundancy to reduce total dataset size and therefore training time — a non-domain-specific vectorization with a high-false-negative cluster-discovery rate was acceptable, because it just meant they'd "compress" the dataset slightly less well, and so get slightly more training time? (At the expense of increased bias in training toward the saliency of the features that weren't dedup'ed out; but that was going to happen regardless, and they likely already had a fully-general technique later in the pipeline for countering that.)

Re: Finding near-duplicates with Jaccard similarity and MinHash

#34

Post by derefr »

gpderetta wrote: post #30
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 overkil…

I was picturing doing the deduplication as a map-reduce process over a huge (petabytes) dataset, where every worker is blind to what embeddings other workers have already generated. In such a case, shoving the embeddings generated by each worker into a shared vector DB, and having it (maybe incrementally) clustering the vectors as it receives them, would be acting as the "reduce" step.

Re: Finding near-duplicates with Jaccard similarity and MinHash

#35

Post by ryantwolf »

Love the article! My team at nvidia recently released a GPU accelerated version of the fuzzy deduplication algorithm described, and I figure this community might be interested.

Here's the repo: https://github.com/NVIDIA/NeMo-Curator/

Some documentation on the fuzzy dedup scripts: https://docs.nvidia.com/nemo-framework/user-guide/latest/dat...

And a Python example: https://github.com/NVIDIA/NeMo-Curator/blob/main/examples/fu...

Would be interested in any feedback from the folks here.

Re: Finding near-duplicates with Jaccard similarity and MinHash

#36

Post by dekhn »

This is one of those techniques I don't understand when I read it as text, but will instantly absorb when I have a working code example and pass some of my own data through it a few times, inspecting the working process.

I first learned about this technique from Douglas Eck (https://research.google/people/douglas-eck/), who used it for song clustering at Google. I remember him saying something about hashing and random vectors, and was puzzled because I figured that less random optimiztion would work better.

Re: Finding near-duplicates with Jaccard similarity and MinHash

#37

Post by brianyu8 »

carnewal wrote: post #23

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.

This visualization is super cool! Thanks for sharing.

Re: Finding near-duplicates with Jaccard similarity and MinHash

#38

Post by a-dub »

dekhn wrote: post #36

This is one of those techniques I don't understand when I read it as text, but will instantly absorb when I have a working code example and pass some of my own data through it a few times, inspecting the working process. I first learned about this technique from Douglas Eck ( https://research.google/people/douglas-eck/ ), who used it for song clustering at Google. I remember him saying something about hashing and ran…

i think the key insight, at least for me, is that if you break things into piles of lots of little pieces and then you come up with n different ways of ordering those piles, similar things are going to have the same piece show up on top across those orderings.

add in the banding stuff and some simple probability and voila! a cheap and embarrassingly parallel way to approximate jaccard similarity across huge datasets.

Post reply on HN