# \[RFC\] idea for a near duplicate filter **URL:** \ **Category:** Elasticsearch\ **Created:** [July 28, 2014, 9:12pm UTC](https://discuss.elastic.co/t/rfc-idea-for-a-near-duplicate-filter/18937 "2014-07-28T21:12:36Z")\ **Posts on this page:** 3\ **Page:** 1
**Author:** ![Valentin\_Pletzer](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/valentin_pletzer/32/105548_2.png) [@Valentin\_Pletzer](https://discuss.elastic.co/u/Valentin_Pletzer)\ **Post date:** [July 28, 2014, 9:12pm UTC](https://discuss.elastic.co/t/rfc-idea-for-a-near-duplicate-filter/18937/1 "2014-07-28T21:12:36Z")
I have an idea for a filter with a technique I used on another project. I thought I should share because this might be useful to someone. Finding exact matches is an easy task but finding documents with small differences isnt. Google is using a technique which is very easy to implement and only costs 64 bit (if you choose this size). It is called simhash and is not to be confused with minhash (which Twitter is using). In simple words simhash works like this: 1. you hash every token with a classic hash (like Murmur) 2. you sum up every first bit, second bit and so on (1 = +1 and 0 = -1) 3. now you have 64 numbers and for every positive number the corresponding simhash bit is 1 and for every zero and negative number the simhash bit is 0 Thats it. Now if you searching for a near duplicate document you only have to compare the simhashes and if it only differs in a small number of bits (the Google paper says a hamming distance of 3 in 64) its a near duplicate. And there is more. There are things you could do, like giving stop words only a small weight when adding up. Giving synonyms the same (murmur) hash with a smaller weight Links: [http://www.wwwconference.org/www2007/papers/paper215.pdf](http://www.wwwconference.org/www2007/papers/paper215.pdf) > **[CharikarEstim.pdf](https://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf)** > > 155.06 KB [http://www.matpalm.com/resemblance/simhash/](http://www.matpalm.com/resemblance/simhash/) > **[twitter/algebird](https://github.com/twitter/algebird)** > > algebird - Abstract Algebra for Scala -- You received this message because you are subscribed to the Google Groups "elasticsearch" group. To unsubscribe from this group and stop receiving emails from it, send an email to [elasticsearch+unsubscribe@googlegroups.com](mailto:elasticsearch+unsubscribe@googlegroups.com). To view this discussion on the web visit [https://groups.google.com/d/msgid/elasticsearch/31fe6560-d066-481d-8b7a-7f51cab735a2%40googlegroups.com](https://groups.google.com/d/msgid/elasticsearch/31fe6560-d066-481d-8b7a-7f51cab735a2%40googlegroups.com). For more options, visit [https://groups.google.com/d/optout](https://groups.google.com/d/optout). ---
**Author:** ![vineeth\_mohan\_2](https://sea2.discourse-cdn.com/elastic/user_avatar/discuss.elastic.co/vineeth_mohan_2/32/747_2.png) [@vineeth\_mohan\_2](https://discuss.elastic.co/u/vineeth_mohan_2)\ **Post date:** [July 29, 2014, 2:50am UTC](https://discuss.elastic.co/t/rfc-idea-for-a-near-duplicate-filter/18937/2 "2014-07-29T02:50:10Z")
Hello Valentin , Thanks for this suggestion. We might find this useful in some of our projects. Thanks Vineeth On Tue, Jul 29, 2014 at 2:42 AM, Valentin [pletzer@gmail.com](mailto:pletzer@gmail.com) wrote: > I have an idea for a filter with a technique I used on another project. I > thought I should share because this might be useful to someone. > > Finding exact matches is an easy task but finding documents with small > differences isnt. Google is using a technique which is very easy to > implement and only costs 64 bit (if you choose this size). It is called > simhash and is not to be confused with minhash (which Twitter is using). > > In simple words simhash works like this: > > 1. you hash every token with a classic hash (like Murmur) > 2. you sum up every first bit, second bit and so on (1 = +1 and 0 = -1) > 3. now you have 64 numbers and for every positive number the corresponding > simhash bit is 1 and for every zero and negative number the simhash bit is 0 > > Thats it. Now if you searching for a near duplicate document you only have > to compare the simhashes and if it only differs in a small number of bits > (the Google paper says a hamming distance of 3 in 64) its a near duplicate. > > And there is more. There are things you could do, like giving stop words > only a small weight when adding up. Giving synonyms the same (murmur) hash > with a smaller weight > > Links: > [http://www.wwwconference.org/www2007/papers/paper215.pdf](http://www.wwwconference.org/www2007/papers/paper215.pdf) > > [http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf](http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf) > [simhash](http://www.matpalm.com/resemblance/simhash/) > > [GitHub - twitter/algebird: Abstract Algebra for Scala](https://github.com/twitter/algebird) > > -- > You received this message because you are subscribed to the Google Groups > "elasticsearch" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [elasticsearch+unsubscribe@googlegroups.com](mailto:elasticsearch+unsubscribe@googlegroups.com). > To view this discussion on the web visit > [https://groups.google.com/d/msgid/elasticsearch/31fe6560-d066-481d-8b7a-7f51cab735a2%40googlegroups.com](https://groups.google.com/d/msgid/elasticsearch/31fe6560-d066-481d-8b7a-7f51cab735a2%40googlegroups.com) > . > For more options, visit [https://groups.google.com/d/optout](https://groups.google.com/d/optout). -- You received this message because you are subscribed to the Google Groups "elasticsearch" group. To unsubscribe from this group and stop receiving emails from it, send an email to [elasticsearch+unsubscribe@googlegroups.com](mailto:elasticsearch+unsubscribe@googlegroups.com). To view this discussion on the web visit [https://groups.google.com/d/msgid/elasticsearch/CAGdPd5%3Doqym%3D2y24rijgWekk2z5%2BZCYX%2BKg3UcCfet3-Lh%2BRjg%40mail.gmail.com](https://groups.google.com/d/msgid/elasticsearch/CAGdPd5%3Doqym%3D2y24rijgWekk2z5%2BZCYX%2BKg3UcCfet3-Lh%2BRjg%40mail.gmail.com). For more options, visit [https://groups.google.com/d/optout](https://groups.google.com/d/optout). ---
**Author:** ![system](https://us1.discourse-cdn.com/elastic/original/3X/1/a/1ac57faf039f6b580b3f104ef42a2a89e41014de.png) [@system](https://discuss.elastic.co/u/system)\ **Post date:** [July 6, 2017, 1:12am UTC](https://discuss.elastic.co/t/rfc-idea-for-a-near-duplicate-filter/18937/3 "2017-07-06T01:12:41Z")