Minhash explained blog post
https://mccormickml.com/2015/06/12/minhash-tutorial-with-python-code/
MinHash Tutorial with Python Code
2015-06-12
None
<div><div>
 <article>
 
 <time>12 Jun 2015</time>
 <p>In this post, I’m providing a brief tutorial, along with some example Python code, for applying the MinHash algorithm to compare a large number of documents to one another efficiently.</p>
<p>I first learned about this topic through Stanford’s Mining of Massive Datasets (“MMDS”) course available for free on Coursera <a href="https://www.coursera.org/course/mmds">here</a> (Update 11/5/19 - It’s no longer on Coursera, but still freely available <a href="https://lagunita.stanford.edu/courses/course-v1:ComputerScience+MMDS+SelfPaced/about">here</a>). What’s especially great about that course is that the authors also provide their textbook online for free! You can find the textbook <a href="http://www.mmds.org/">here</a>, with a separate PDF file for each chapter. <a href="http://infolab.stanford.edu/~ullman/mmds/ch3.pdf">Chapter 3</a> covers the MinHash algorithm, and I’d refer you to that text as a more complete discussion of the topic.</p>
<p>On to the tutorial!</p>
<h2>Set Similarity</h2>
<p>There is an interesting computing problem that arises in a number of contexts called “set similarity”.</p>
<p>Lets say you and I are both subscribers to Netflix, and we’ve each watched roughly 100 movies on Netflix. The list of movies I’ve seen is a set, and the list of movies you’ve seen is another set. To measure the similarity between these two sets, you can use the Jaccard Similarity, which is given by the <em>intersection</em> of the sets divided by their <em>union</em>. That is, count the number of movies we’ve both seen, and divide that by the total number of unique movies that we’ve both collectively seen.</p>
<p>If we’ve each watched exactly 100 movies, and 50 of those were seen by both of us, then the intersection is 50 and the union is 150, so our Jaccard Similarity is 1/3.</p>
<h2>Documents as sets</h2>
<p>What seems to be the more common application of “set similarity” is the comparison of documents. One way to represent a document would be to parse it for all of its words, and represent the document as the set of all unique words it contains. In practice, you’d hash the words to integer IDs, and then maintain the set of IDs present in the document.</p>
<p>By representing the documents as sets of words, you could then use the Jaccard Similarity as a measure of how much overlap there is between two documents.</p>
<p>It’s important to note that we’re not actually extracting any semantic meaning of the documents here, we’re simply looking at whether they contain the same words. This technique of comparing documents probably won’t work as well, for example, for comparing documents that cover similar concepts but are otherwise completely unique.</p>
<p>Instead, the applications of this technique are found where there’s some expectation that the documents will specifically contain a lot of the same words.</p>
<p>One example is aggregating news articles. When the Associated Press releases an article about a particular event, many news agencies will take the AP article, perhaps modify it some, and publish it on their website. A news aggregator needs to recognize that a group of articles are really all based on the same AP article about one particular story. Comparing the web pages using this “similar sets” approach is one way to accomplish this.</p>
<p>Another example is detecting plagiarism. The dataset used in my example code is a large collection of articles, some of which are plagiarisms of each other (where they’ve been just slightly modified).</p>
<p>You might say that these are all applications of “near-duplicate” detection.</p>
<h2>Shingles</h2>
<p>A small detail here is that it is more common to parse the document by taking, for example, each possible string of three consecutive words from the document (e.g., “A small detail”, “small detail here”, “detail here is”, etc.) and hashing these strings to integers. This retains a little more of the document structure than just hashing the individual words. This technique of hashing substrings is referred to as “shingling”, and each unique string is called a “shingle”.</p>
<p>Another shingling technique that’s described in the Mining of Massive Datasets textbook is <em>k</em>-shingles, where you take each possible sequence of ‘k’ characters. I’m not clear on the motivation of this approach—it may have to do with the fact that it always produces strings of length ‘k’, whereas the three-word approach produces variable length strings.</p>
<p>In the example code, I’m using three-word shingles, and it works well.</p>
<h2>Problem scale</h2>
<p>So far, this all sounds pretty straight forward and manageable. Where it gets interesting is when you look at the compute requirements for doing this for a relatively large number of documents.</p>
<p>Let’s say you have a large collection of documents, and you want to find all of the pairs of documents that are near-duplicates of each other. You’d do this by calculating the Jaccard similarity between each pair of documents, and then selecting those with a similarity above some threshold.</p>
<p>To compare each document to every other document requires a lot of comparisons! It’s not quite N-squared comparisons, since that would include doing a redundant comparison of ‘a’ to ‘b’ and ‘b’ to ‘a’, as well as comparing every document to itself.</p>
<p>The number of comparisons required is given by the following formula, which is pronounced “N-choose-2”</p>
<p><a href="https://chrisjmccormick.files.wordpress.com/2015/06/n-choose-2-eq.png"></a></p>
<p>As noted in the equation, a good approximation is N^2 / 2 (This is approximation is equivalent to comparing each document pair only once, but also needlessly comparing each document to itself).</p>
<p>Lets say we have a collection of 1 million documents, and that on average, a PC can calculate the Jaccard similarity between two sets in 1ms per pair.</p>
<p>First, let’s calculate the rough number of comparisons required:</p>
<p><a href="https://chrisjmccormick.files.wordpress.com/2015/06/1m-doc-comparisons.png"></a></p>
<p>Next, the amount of time required:</p>
<p><a href="https://chrisjmccormick.files.wordpress.com/2015/06/1m-doc-comparisons-time.png"></a></p>
<p>16 years of compute time! Good luck with that. You’d need 1,000 servers just to get the compute time down to a week. But there’s a better way…</p>
<h2>MinHash Signatures</h2>
<p>The MinHash algorithm will provide us with a fast approximation to the Jaccard Similarity between two sets.</p>
<p>For each set in our data, we are going to calculate a MinHash signature. The MinHash signatures will all have a fixed length, independent of the size of the set. And the signatures will be relatively short—in the example code, they are only 10 components long.</p>
<p>To approximate the Jaccard Similarity between two sets, we will take their MinHash signatures, and simply count the number of components which are equal. If you divide this count by the signature length, you have a pretty good approximation to the Jaccard Similarity between those two sets.</p>
<p>We can compare two MinHash signatures in this way much quicker than we can calculate the intersection and union between two large sets. This is partly because the MinHash signatures tend to be much shorter than the number of shingles in the documents, and partly because the comparison operation is simpler.</p>
<p>In the example code, we have a collection of 10,000 articles which contain, on average, 250 shingles each. Computing the Jaccard similarities directly for all pairs takes 20 minutes on my PC, while generating and comparing the MinHash signatures takes only about 2 minutes and 45 seconds.</p>
<h2>MinHash Algorithm</h2>
<p>The MinHash algorithm is actually pretty easy to describe if you start with the implementation rather than the intuitive explanation.</p>
<p>The key ingredient to the algorithm is that we have a hash function which takes a 32-bit integer and maps it to a different integer, with no collisions. Put another way, if you took the numbers 0 – (2^32 – 1) and applied this hash function to all of them, you’d get back a list of the same numbers in random order.</p>
<p>To demystify it a bit, here is the definition of the hash function, which takes an input integer ‘x’:</p>
<p><a href="https://chrisjmccormick.files.wordpress.com/2015/06/random-hash-eq.png"></a></p>
<p>The coefficients <code>a</code> and <code>b</code> are randomly chosen integers less than the maximum value of <code>x</code>. <code>c</code> is a prime number slightly bigger than the maximum value of <code>x</code>.</p>
<p>For different choices of <code>a</code> and <code>b</code>, this hash function will produce a different random mapping of the values. So we have the ability to “generate” as many of these random hash functions as we want by just picking different values of <code>a</code> and <code>b</code>.</p>
<p>So here’s how you compute the MinHash signature for a given document. Generate, say, 10 random hash functions. Take the first hash function, and apply it to all of the shingle values in a document. Find the minimum hash value produced (hey, “minimum hash”, that’s the name of the algorithm!) and use it as the first component of the MinHash signature. Now take the second hash function, and again find the minimum resulting hash value, and use this as the second component. And so on.</p>
<p>So if we have 10 random hash functions, we’ll get a MinHash signature with 10 values.</p>
<p>We’ll use the same 10 hash functions for every document in the dataset and generate their signatures as well. Then we can compare the documents by counting the number of signature components in which they match.</p>
<p>That’s it!</p>
<h2>Why Does It Work?</h2>
<p>The reason MinHash works is that the expected value of the MinHash similarity (the number of matching components divided by the signature length) can be shown to be equal to the Jaccard similarity between the sets. We’ll demonstrate this with a simple example involving two small sets:</p>
<p>Set A     (32, <strong>3</strong>, 22, 6, <strong>15</strong>, <strong>11</strong>)</p>
<p>Set B      (<strong>15</strong>, 30, 7, <strong>11</strong>, 28, <strong>3</strong>, 17)</p>
<p>There are three items in common between the sets (highlighted in bold), and 10 unique items between the two sets. Therefore, these sets have a Jaccard similarity of 3/10.</p>
<p>Let’s look first at the probability that, for just a single MinHash signature component, we end up computing the same MinHash value for both sets.</p>
<p>The MinHash calculation can be thought of as taking the union of the two sets, shuffling them in a random order, and selecting the first value in the new sorted order. (Side note: the actual value used in the MinHash signature is not the original item ID, but the hashed value of that ID—but that’s not important for our discussion of the probabilities).</p>
<p>So if you take the union of these two sets,</p>
<p>Union    (32, <strong>3</strong>, 22, 6, <strong>15</strong>, <strong>11</strong>, 30, 7, 28, 17)</p>
<p>and then randomly shuffle them, what are the odds that one of the bold items ends up first in the list? It’s given by the number of common items (3) divided by the total number of items (10), or 3/10, the same as the Jaccard similarity.</p>
<p><em>The probability that a given MinHash value will come from one of the shared items is equal to the Jaccard similarity.</em></p>
<p>Now we can go back to look at the full signature. Continuing with our simple example, if we have a MinHash signature with 20 components, on average, how many of those MinHash values would we expect to be in common? The answer is the number of components (20) times the probability of a match (3/10), or 6 components. The expected value of the MinHash similarity, then, would be 6/20 = 3/10, the same as the Jaccard similarity.</p>
<p><em>The expected value of the MinHash similarity between two sets is equal to their Jaccard similarity.</em></p>
<h2>Example Python Code</h2>
<p>You can find my example code on GitHub <a href="https://github.com/chrisjmccormick/MinHash">here</a>.</p>
<p>If you’re not familiar with GitHub, fear not. Here’s the <a href="https://github.com/chrisjmccormick/MinHash/archive/master.zip">direct link to the zip file</a> containing all of the code.</p>
<h2>Notes on the history of the code</h2>
<p>After working through this material in the MMDS course, I played with the Python code from GitHub user rahularora <a href="https://github.com/rahularora/MinHash">here</a>. It’s a complete implementation, but it had a couple important issues (including one fatal bug) that I’ve addressed.</p>
<p>The most important notes:</p>
<ul>
 <li>
 <p>The modulo constant in his random hash function (the variable <code>c</code> in the equation above) was not a prime number. If this constant isn’t prime, the random hash produces a lot of collisions, and the algorithm doesn’t work well.</p>
 </li>
 <li>
 <p>I’ve replaced the example dataset with a much larger one I found <a href="http://www.inf.ed.ac.uk/teaching/courses/tts/assessed/assessment3.html">here</a>.</p>
 </li>
 <li>
 <p>rahularora made use of Python dictionaries to perform the shingle hashing, but this doesn’t scale well—it got really slow for a large number of documents / shingles. I’ve replaced this with CRC32 hashing.</p>
 </li>
</ul>
<h3>Cite</h3>
<p>McCormick, C. (2015, June 12). <em>MinHash Tutorial with Python Code</em>. Retrieved from http://www.mccormickml.com</p>
 
 
 
 
 
 
 
 
</article>
 </div>||||I|||| Chris McCormick About Membership Blog Archive

 Become an NLP expert with videos & code for BERT and beyond → Join NLP Basecamp now!

 MinHash Tutorial with Python Code

 12 Jun 2015

 In this post, I’m providing a brief tutorial, along with some example Python code, for applying the MinHash algorithm to compare a large number of documents to one another efficiently.

 I first learned about this topic through Stanford’s Mining of Massive Datasets (“MMDS”) course available for free on Coursera here (Update 11/5/19 - It’s no longer on Coursera, but still freely available here). What’s especially great about that course is that the authors also provide their textbook online for free! You can find the textbook here, with a separate PDF file for each chapter. Chapter 3 covers the MinHash algorithm, and I’d refer you to that text as a more complete discussion of the topic.

 On to the tutorial!

 Set Similarity

 There is an interesting computing problem that arises in a number of contexts called “set similarity”.

 Lets say you and I are both subscribers to Netflix, and we’ve each watched roughly 100 movies on Netflix. The list of movies I’ve seen is a set, and the list of movies you’ve seen is another set. To measure the similarity between these two sets, you can use the Jaccard Similarity, which is given by the intersection of the sets divided by their union. That is, count the number of movies we’ve both seen, and divide that by the total number of unique movies that we’ve both collectively seen.

 If we’ve each watched exactly 100 movies, and 50 of those were seen by both of us, then the intersection is 50 and the union is 150, so our Jaccard Similarity is 1/3.

 Documents as sets

 What seems to be the more common application of “set similarity” is the comparison of documents. One way to represent a document would be to parse it for all of its words, and represent the document as the set of all unique words it contains. In practice, you’d hash the words to integer IDs, and then maintain the set of IDs present in the document.

 By representing the documents as sets of words, you could then use the Jaccard Similarity as a measure of how much overlap there is between two documents.

 It’s important to note that we’re not actually extracting any semantic meaning of the documents here, we’re simply looking at whether they contain the same words. This technique of comparing documents probably won’t work as well, for example, for comparing documents that cover similar concepts but are otherwise completely unique.

 Instead, the applications of this technique are found where there’s some expectation that the documents will specifically contain a lot of the same words.

 One example is aggregating news articles. When the Associated Press releases an article about a particular event, many news agencies will take the AP article, perhaps modify it some, and publish it on their website. A news aggregator needs to recognize that a group of articles are really all based on the same AP article about one particular story. Comparing the web pages using this “similar sets” approach is one way to accomplish this.

 Another example is detecting plagiarism. The dataset used in my example code is a large collection of articles, some of which are plagiarisms of each other (where they’ve been just slightly modified).

 You might say that these are all applications of “near-duplicate” detection.

 Shingles

 A small detail here is that it is more common to parse the document by taking, for example, each possible string of three consecutive words from the document (e.g., “A small detail”, “small detail here”, “detail here is”, etc.) and hashing these strings to integers. This retains a little more of the document structure than just hashing the individual words. This technique of hashing substrings is referred to as “shingling”, and each unique string is called a “shingle”.

 Another shingling technique that’s described in the Mining of Massive Datasets textbook is k-shingles, where you take each possible sequence of ‘k’ characters. I’m not clear on the motivation of this approach—it may have to do with the fact that it always produces strings of length ‘k’, whereas the three-word approach produces variable length strings.

 In the example code, I’m using three-word shingles, and it works well.

 Problem scale

 So far, this all sounds pretty straight forward and manageable. Where it gets interesting is when you look at the compute requirements for doing this for a relatively large number of documents.

 Let’s say you have a large collection of documents, and you want to find all of the pairs of documents that are near-duplicates of each other. You’d do this by calculating the Jaccard similarity between each pair of documents, and then selecting those with a similarity above some threshold.

 To compare each document to every other document requires a lot of comparisons! It’s not quite N-squared comparisons, since that would include doing a redundant comparison of ‘a’ to ‘b’ and ‘b’ to ‘a’, as well as comparing every document to itself.

 The number of comparisons required is given by the following formula, which is pronounced “N-choose-2”

 As noted in the equation, a good approximation is N^2 / 2 (This is approximation is equivalent to comparing each document pair only once, but also needlessly comparing each document to itself).

 Lets say we have a collection of 1 million documents, and that on average, a PC can calculate the Jaccard similarity between two sets in 1ms per pair.

 First, let’s calculate the rough number of comparisons required:

 Next, the amount of time required:

 16 years of compute time! Good luck with that. You’d need 1,000 servers just to get the compute time down to a week. But there’s a better way…

 MinHash Signatures

 The MinHash algorithm will provide us with a fast approximation to the Jaccard Similarity between two sets.

 For each set in our data, we are going to calculate a MinHash signature. The MinHash signatures will all have a fixed length, independent of the size of the set. And the signatures will be relatively short—in the example code, they are only 10 components long.

 To approximate the Jaccard Similarity between two sets, we will take their MinHash signatures, and simply count the number of components which are equal. If you divide this count by the signature length, you have a pretty good approximation to the Jaccard Similarity between those two sets.

 We can compare two MinHash signatures in this way much quicker than we can calculate the intersection and union between two large sets. This is partly because the MinHash signatures tend to be much shorter than the number of shingles in the documents, and partly because the comparison operation is simpler.

 In the example code, we have a collection of 10,000 articles which contain, on average, 250 shingles each. Computing the Jaccard similarities directly for all pairs takes 20 minutes on my PC, while generating and comparing the MinHash signatures takes only about 2 minutes and 45 seconds.

 MinHash Algorithm

 The MinHash algorithm is actually pretty easy to describe if you start with the implementation rather than the intuitive explanation.

 The key ingredient to the algorithm is that we have a hash function which takes a 32-bit integer and maps it to a different integer, with no collisions. Put another way, if you took the numbers 0 – (2^32 – 1) and applied this hash function to all of them, you’d get back a list of the same numbers in random order.

 To demystify it a bit, here is the definition of the hash function, which takes an input integer ‘x’:

 The coefficients a and b are randomly chosen integers less than the maximum value of x. c is a prime number slightly bigger than the maximum value of x.

 For different choices of a and b, this hash function will produce a different random mapping of the values. So we have the ability to “generate” as many of these random hash functions as we want by just picking different values of a and b.

 So here’s how you compute the MinHash signature for a given document. Generate, say, 10 random hash functions. Take the first hash function, and apply it to all of the shingle values in a document. Find the minimum hash value produced (hey, “minimum hash”, that’s the name of the algorithm!) and use it as the first component of the MinHash signature. Now take the second hash function, and again find the minimum resulting hash value, and use this as the second component. And so on.

 So if we have 10 random hash functions, we’ll get a MinHash signature with 10 values.

 We’ll use the same 10 hash functions for every document in the dataset and generate their signatures as well. Then we can compare the documents by counting the number of signature components in which they match.

 That’s it!

 Why Does It Work?

 The reason MinHash works is that the expected value of the MinHash similarity (the number of matching components divided by the signature length) can be shown to be equal to the Jaccard similarity between the sets. We’ll demonstrate this with a simple example involving two small sets:

 Set A (32, 3, 22, 6, 15, 11)

 Set B (15, 30, 7, 11, 28, 3, 17)

 There are three items in common between the sets (highlighted in bold), and 10 unique items between the two sets. Therefore, these sets have a Jaccard similarity of 3/10.

 Let’s look first at the probability that, for just a single MinHash signature component, we end up computing the same MinHash value for both sets.

 The MinHash calculation can be thought of as taking the union of the two sets, shuffling them in a random order, and selecting the first value in the new sorted order. (Side note: the actual value used in the MinHash signature is not the original item ID, but the hashed value of that ID—but that’s not important for our discussion of the probabilities).

 So if you take the union of these two sets,

 Union (32, 3, 22, 6, 15, 11, 30, 7, 28, 17)

 and then randomly shuffle them, what are the odds that one of the bold items ends up first in the list? It’s given by the number of common items (3) divided by the total number of items (10), or 3/10, the same as the Jaccard similarity.

 The probability that a given MinHash value will come from one of the shared items is equal to the Jaccard similarity.

 Now we can go back to look at the full signature. Continuing with our simple example, if we have a MinHash signature with 20 components, on average, how many of those MinHash values would we expect to be in common? The answer is the number of components (20) times the probability of a match (3/10), or 6 components. The expected value of the MinHash similarity, then, would be 6/20 = 3/10, the same as the Jaccard similarity.

 The expected value of the MinHash similarity between two sets is equal to their Jaccard similarity.

 Example Python Code

 You can find my example code on GitHub here.

 If you’re not familiar with GitHub, fear not. Here’s the direct link to the zip file containing all of the code.

 Notes on the history of the code

 After working through this material in the MMDS course, I played with the Python code from GitHub user rahularora here. It’s a complete implementation, but it had a couple important issues (including one fatal bug) that I’ve addressed.

 The most important notes:

 * The modulo constant in his random hash function (the variable c in the equation above) was not a prime number. If this constant isn’t prime, the random hash produces a lot of collisions, and the algorithm doesn’t work well.

 * I’ve replaced the example dataset with a much larger one I found here.

 * rahularora made use of Python dictionaries to perform the shingle hashing, but this doesn’t scale well—it got really slow for a large number of documents / shingles. I’ve replaced this with CRC32 hashing.

 Cite

 McCormick, C. (2015, June 12). MinHash Tutorial with Python Code. Retrieved from http://www.mccormickml.com

 Please enable JavaScript to view the comments powered by Disqus.

 Related posts

 * Steps and Seeds in Stable Diffusion 11 Jan 2023
 * How Stable Diffusion Works 21 Dec 2022
 * How img2img Diffusion Works 06 Dec 2022
 © 2023. All rights reserved.
12 Jun 2015
 In this post, I’m providing a brief tutorial, along with some example Python code, for applying the MinHash algorithm to compare a large number of documents to one another efficiently.
I first learned about this topic through Stanford’s Mining of Massive Datasets (“MMDS”) course available for free on Coursera here (Update 11/5/19 - It’s no longer on Coursera, but still freely available here). What’s especially great about that course is that the authors also provide their textbook online for free! You can find the textbook here, with a separate PDF file for each chapter. Chapter 3 covers the MinHash algorithm, and I’d refer you to that text as a more complete discussion of the topic.
On to the tutorial!
Set Similarity
There is an interesting computing problem that arises in a number of contexts called “set similarity”.
Lets say you and I are both subscribers to Netflix, and we’ve each watched roughly 100 movies on Netflix. The list of movies I’ve seen is a set, and the list of movies you’ve seen is another set. To measure the similarity between these two sets, you can use the Jaccard Similarity, which is given by the intersection of the sets divided by their union. That is, count the number of movies we’ve both seen, and divide that by the total number of unique movies that we’ve both collectively seen.
If we’ve each watched exactly 100 movies, and 50 of those were seen by both of us, then the intersection is 50 and the union is 150, so our Jaccard Similarity is 1/3.
Documents as sets
What seems to be the more common application of “set similarity” is the comparison of documents. One way to represent a document would be to parse it for all of its words, and represent the document as the set of all unique words it contains. In practice, you’d hash the words to integer IDs, and then maintain the set of IDs present in the document.
By representing the documents as sets of words, you could then use the Jaccard Similarity as a measure of how much overlap there is between two documents.
It’s important to note that we’re not actually extracting any semantic meaning of the documents here, we’re simply looking at whether they contain the same words. This technique of comparing documents probably won’t work as well, for example, for comparing documents that cover similar concepts but are otherwise completely unique.
Instead, the applications of this technique are found where there’s some expectation that the documents will specifically contain a lot of the same words.
One example is aggregating news articles. When the Associated Press releases an article about a particular event, many news agencies will take the AP article, perhaps modify it some, and publish it on their website. A news aggregator needs to recognize that a group of articles are really all based on the same AP article about one particular story. Comparing the web pages using this “similar sets” approach is one way to accomplish this.
Another example is detecting plagiarism. The dataset used in my example code is a large collection of articles, some of which are plagiarisms of each other (where they’ve been just slightly modified).
You might say that these are all applications of “near-duplicate” detection.
Shingles
A small detail here is that it is more common to parse the document by taking, for example, each possible string of three consecutive words from the document (e.g., “A small detail”, “small detail here”, “detail here is”, etc.) and hashing these strings to integers. This retains a little more of the document structure than just hashing the individual words. This technique of hashing substrings is referred to as “shingling”, and each unique string is called a “shingle”.
Another shingling technique that’s described in the Mining of Massive Datasets textbook is k-shingles, where you take each possible sequence of ‘k’ characters. I’m not clear on the motivation of this approach—it may have to do with the fact that it always produces strings of length ‘k’, whereas the three-word approach produces variable length strings.
In the example code, I’m using three-word shingles, and it works well.
Problem scale
So far, this all sounds pretty straight forward and manageable. Where it gets interesting is when you look at the compute requirements for doing this for a relatively large number of documents.
Let’s say you have a large collection of documents, and you want to find all of the pairs of documents that are near-duplicates of each other. You’d do this by calculating the Jaccard similarity between each pair of documents, and then selecting those with a similarity above some threshold.
To compare each document to every other document requires a lot of comparisons! It’s not quite N-squared comparisons, since that would include doing a redundant comparison of ‘a’ to ‘b’ and ‘b’ to ‘a’, as well as comparing every document to itself.
The number of comparisons required is given by the following formula, which is pronounced “N-choose-2”
   
As noted in the equation, a good approximation is N^2 / 2 (This is approximation is equivalent to comparing each document pair only once, but also needlessly comparing each document to itself).
Lets say we have a collection of 1 million documents, and that on average, a PC can calculate the Jaccard similarity between two sets in 1ms per pair.
First, let’s calculate the rough number of comparisons required:
   
Next, the amount of time required:
   
16 years of compute time! Good luck with that. You’d need 1,000 servers just to get the compute time down to a week. But there’s a better way…
MinHash Signatures
The MinHash algorithm will provide us with a fast approximation to the Jaccard Similarity between two sets.
For each set in our data, we are going to calculate a MinHash signature. The MinHash signatures will all have a fixed length, independent of the size of the set. And the signatures will be relatively short—in the example code, they are only 10 components long.
To approximate the Jaccard Similarity between two sets, we will take their MinHash signatures, and simply count the number of components which are equal. If you divide this count by the signature length, you have a pretty good approximation to the Jaccard Similarity between those two sets.
We can compare two MinHash signatures in this way much quicker than we can calculate the intersection and union between two large sets. This is partly because the MinHash signatures tend to be much shorter than the number of shingles in the documents, and partly because the comparison operation is simpler.
In the example code, we have a collection of 10,000 articles which contain, on average, 250 shingles each. Computing the Jaccard similarities directly for all pairs takes 20 minutes on my PC, while generating and comparing the MinHash signatures takes only about 2 minutes and 45 seconds.
MinHash Algorithm
The MinHash algorithm is actually pretty easy to describe if you start with the implementation rather than the intuitive explanation.
The key ingredient to the algorithm is that we have a hash function which takes a 32-bit integer and maps it to a different integer, with no collisions. Put another way, if you took the numbers 0 – (2^32 – 1) and applied this hash function to all of them, you’d get back a list of the same numbers in random order.
To demystify it a bit, here is the definition of the hash function, which takes an input integer ‘x’:
   
The coefficients a and b are randomly chosen integers less than the maximum value of x. c is a prime number slightly bigger than the maximum value of x.
For different choices of a and b, this hash function will produce a different random mapping of the values. So we have the ability to “generate” as many of these random hash functions as we want by just picking different values of a and b.
So here’s how you compute the MinHash signature for a given document. Generate, say, 10 random hash functions. Take the first hash function, and apply it to all of the shingle values in a document. Find the minimum hash value produced (hey, “minimum hash”, that’s the name of the algorithm!) and use it as the first component of the MinHash signature. Now take the second hash function, and again find the minimum resulting hash value, and use this as the second component. And so on.
So if we have 10 random hash functions, we’ll get a MinHash signature with 10 values.
We’ll use the same 10 hash functions for every document in the dataset and generate their signatures as well. Then we can compare the documents by counting the number of signature components in which they match.
That’s it!
Why Does It Work?
The reason MinHash works is that the expected value of the MinHash similarity (the number of matching components divided by the signature length) can be shown to be equal to the Jaccard similarity between the sets. We’ll demonstrate this with a simple example involving two small sets:
Set A     (32, 3, 22, 6, 15, 11)
Set B      (15, 30, 7, 11, 28, 3, 17)
There are three items in common between the sets (highlighted in bold), and 10 unique items between the two sets. Therefore, these sets have a Jaccard similarity of 3/10.
Let’s look first at the probability that, for just a single MinHash signature component, we end up computing the same MinHash value for both sets.
The MinHash calculation can be thought of as taking the union of the two sets, shuffling them in a random order, and selecting the first value in the new sorted order. (Side note: the actual value used in the MinHash signature is not the original item ID, but the hashed value of that ID—but that’s not important for our discussion of the probabilities).
So if you take the union of these two sets,
Union    (32, 3, 22, 6, 15, 11, 30, 7, 28, 17)
and then randomly shuffle them, what are the odds that one of the bold items ends up first in the list? It’s given by the number of common items (3) divided by the total number of items (10), or 3/10, the same as the Jaccard similarity.
 The probability that a given MinHash value will come from one of the shared items is equal to the Jaccard similarity. 
Now we can go back to look at the full signature. Continuing with our simple example, if we have a MinHash signature with 20 components, on average, how many of those MinHash values would we expect to be in common? The answer is the number of components (20) times the probability of a match (3/10), or 6 components. The expected value of the MinHash similarity, then, would be 6/20 = 3/10, the same as the Jaccard similarity.
 The expected value of the MinHash similarity between two sets is equal to their Jaccard similarity. 
Example Python Code
You can find my example code on GitHub here.
If you’re not familiar with GitHub, fear not. Here’s the direct link to the zip file containing all of the code.
Notes on the history of the code
After working through this material in the MMDS course, I played with the Python code from GitHub user rahularora here. It’s a complete implementation, but it had a couple important issues (including one fatal bug) that I’ve addressed.
The most important notes:
 
 The modulo constant in his random hash function (the variable c in the equation above) was not a prime number. If this constant isn’t prime, the random hash produces a lot of collisions, and the algorithm doesn’t work well.
 
 
 I’ve replaced the example dataset with a much larger one I found here.
 
 
 rahularora made use of Python dictionaries to perform the shingle hashing, but this doesn’t scale well—it got really slow for a large number of documents / shingles. I’ve replaced this with CRC32 hashing.
 
Cite
McCormick, C. (2015, June 12). MinHash Tutorial with Python Code. Retrieved from http://www.mccormickml.com
MinHash Tutorial with Python Code
https://mccormickml.com/2015/06/12/minhash-tutorial-with-python-code/
http://matthewcasperson.blogspot.com/2013/11/minhash-for-dummies.html
MinHash for dummies
2013-11-14
Unknown
<div><div><p>
Duplicate document detection is becoming increasingly important for businesses that have huge collections of email, web pages and documents with multiple copies that may or may not be kept up to date.</p><p>
MinHash is a fairly simple algorithm that from all my Googling has been explained very poorly in blogs or in the kind of mathematical terms that I forgot long ago. So in this article I will attempt to explain how MinHash works at a practical code level.</p><p>
Before I start, please take a look at <a href="http://infolab.stanford.edu/~ullman/mmds/ch3.pdf">http://infolab.stanford.edu/~ullman/mmds/ch3.pdf</a>. That document goes into a lot of theory, and was ultimately where my understanding on MinHash came from. Unfortunately it approaches the algorithm from a theoretical standpoint, but if I gloss over some aspect of the MinHash algorithm here, you will almost certainly find a fuller explanation in the PDF.</p><p>
I'll also be using pseudo Java in these examples instead of traditional math. This means when I use terms like Set, I am referring to the group of classes that implement a Set in Java. Of course a set in Java shares a lot of properties with a set in maths, but keep in mind that this is written from a developers point of view.</p><h2>
What does it mean when we talk about document similarity?  </h2>
<p>
The whole point of MinHash is to efficiently answer the question "How similar is this document to that document".</p>
<p>
Before we can answer that question, we need to look at a more simple example of two sets of strings and determine how similar they are.</p>
<p>
Here are our two sets:</p>
<div><p>
Set</p> a = new Set(["chair", "desk", "rug", "keyboard", "mouse"]);</div>
<div><p>
Set</p> b = new Set(["chair", "rug", "keyboard"]);</div>
<p>
A measure of how similar these two sets are is known as the Jaccard Coefficient. It is calculated as <b>number of common elements / (total number of elements - number of common elements)</b>.</p>
<p>
In our case we have 3 common elements: "chair", "rug" and "keyboard". We have a total of 8 elements. So the Jaccard Coefficient  = 3 / (8 - 3) = 0.6, or 60%. <a href="http://www.planetcalc.com/1664/">http://www.planetcalc.com/1664/</a> is an online calculator that you can play around with to determine the similarity of two sets.</p>
<h2>
Documents as sets</h2>
<p>
While a document can be though of as a giant set of words, we don't just break down a document into individual words, place them in a set and calculate the similarity, because that looses the importance of the order of the words. The sets</p>
<div>
<div><p>
Set</p> a = new Set(["I", "went", "to", "work", "today"]);</div>
<div><p>
Set</p> b = new Set(["today", "I", "went", "to", "work"]);</div>
</div>
<p>
would be considered 100% similar, even though they clearly are not.</p>
<p>
Instead we break a document down into what are known as shingles. Each shingle contains a set number of words, and a document is broken down into <b>total words - single length + 1 </b>number of shingles. So if a document contained a single sentence of "The quick brown fox jumps over the lazy dog", that would be broken down into the following 5 word long shingles :</p>
<div>
<ol>
<li>The quick brown fox jumps</li>
<li>quick brown fox jumps over</li>
<li>brown fox jumps over the</li>
<li>fox jumps over the lazy</li>
<li>jumps over the lazy dog</li>
</ol>
</div>
<p>
So our document as a set looks like:</p>
<div><p>
Set</p> a = new Set(["The quick brown fox jumps", "quick brown fox jumps over", "brown fox jumps over the", "fox jumps over the lazy", "jumps over the lazy dog"]);</div>
<p>
These sets of shingles can then be compared for similarity using the Jaccard Coefficient.</p>
<h2>
Optimizing the process</h2>
<p>
So we now have a way to compare two documents for similarity, but it is not an efficient process. To find similar documents to document A in a directory of 10000 documents, we need compare each pair individually. This is obviously not going to scale well.</p>
<p>
What we can do to reduce some cycles is compare sets of randomly selected shingles from two documents. So for a document that is 10000 words long, we break it down into 9996 shingles, and randomly select say 200 of those to represent the document. If the second document is 20000 words long, we boil that down from 19996 shingles to another set of 200 randomly selected shingles.</p>
<p>
Now instead of matching 9996 shingles to 19996 other shingles, we are are comparing 200 shingles to another 200 shingles. We have reduced our workload at the expense of accuracy, but this is still good enough for most scenarios.</p>
<p>NOTE</p>
<p>So just how much accuracy did we sacrifice by comparing only a small subset of randomly selected shingles? I actually don't know, but I assume it sits on a bell curve where the number of random selections improves the accuracy to a point where more random selections won't provide any meaningful increase in accuracy. If you know the math behind this, please leave a comment.</p>
<h2>
Computing and saving the random shingle selections</h2>
<p>
So this is where MinHash comes in.</p>
<p>
We could save the 200 randomly selected shingles, but storing variable length strings kinda sucks. It complicates database design and comparing strings is slow.</p>
<p>
The clever part about MinHash is that it allows us to save integers instead of strings, and also takes the hassle out of randomly selecting shingles. It works like this.</p>
<p>
1. Break down the document a set of shingles.</p>
<p>
2. Calculate the hash value for every shingle.</p>
<p>
3. Store the minimum hash value found in step 2.</p>
<p>
4. Repeat steps 2 and 3 with different hash algorithms 199 more times to get a total of 200 min hash values.</p>
<p>
At this point instead of 200 randomly selected shingles, we have 200 integer hash values. This is effectively a random selection of shingles, because a good hash algorithm is supposed to generate a number that is as likely to be large as it is likely to be small. This kind of distribution of hash codes is what hashing is all about, so selecting the smallest hash is, for all intents and purposes, a random selection of a shingle.</p>
<h2>
Um, 199 more hash algorithms? WTF!</h2>
<p>
So you see the String.hashCode() method, but where do these other 199 hash codes come from? This is the step that most explanations on the MinHash algorithm conveniently leave out.</p>
<p>
The short answer is that you XOR the value returned by String.hashCode() with 199 random numbers to generate the 199 other hash code values. Just make sure that you are using the <i>same</i> 199 random numbers across all the documents.</p>
<h2>
Great, but I still have to compare every document to every other document. Can this be optimized?</h2>
<p>
This is where the second neat trick of MinHash comes in. </p>
<p>
Locality sensitive hashing (LSH) involves generating a hash code such that similar items will tend to get similar hash codes. This is the opposite of what .hashCode() does.</p>
<p>
LSH allows you to precompute a hash code that is then quickly and easily compared to another precomputed LSH hash code to determine if two objects should be compared in more detail or quickly discarded.</p>
<p>
We don't actually calculate a LSH hash code as such, but the idea of a boiling down a complex object (like our collection of minhash codes) into something that is quickly and easily compared with other complex objects is still applicable.</p>
<p>
What we do is take the collection of minhash values, and categorize them into bands and row. For the sake of simplicity we'll assume each document has 20 minhash values. We will break them down into 5 bands with 4 rows each. Also for the sake of simplicity we'll assume that .hashCode() (and any number XORed with it) results in a number between 0 and 9.</p>
<p>
So conceptually the minhash values from 5 documents in the first of the 5 bands and its rows looks like this.</p>
<div>
<table>
<tbody>
<tr>
<td>Band One</td><td><table>
<tbody>
<tr>
<td></td>
<td>MinHash Algorithm One</td>
<td>MinHash Algorithm Two</td>
<td>MinHash Algorithm Three</td>
<td>MinHash Algorithm Four</td>
</tr>
<tr>
<td>Document One</td>
<td>1</td>
<td>3</td>
<td>6</td>
<td>0</td>
</tr>
<tr>
<td>Document Two</td>
<td>2</td>
<td>3</td>
<td>1</td>
<td>0</td>
</tr>
<tr>
<td>Document Three</td>
<td>1</td>
<td>3</td>
<td>6</td>
<td>0</td>
</tr>
<tr>
<td>Document Four</td>
<td>2</td>
<td>1</td>
<td>3</td>
<td>1</td>
</tr>
</tbody></table>
</td>
</tr>
</tbody></table>
</div>
<p>
What we are looking for are rows within a band that are the same between documents. Document One and Document Three in this case both have rows with values 1, 3, 6, 0. This tells us that these two documents should be compared for their similarity.</p>
<p>
Although it is not shown here, you should look through Bands Two - Five looking for documents that share rows. Any documents that share rows in any bands should be compared for their similarity. </p>
<p>
This is useful when you have a document, and you want to know which other documents to compare to it for similarity. I'll assume that the minhash values are stored in SQL, so to get out candidates for comparison you would write:</p>
<p>
SELECT DocName </p>
<p>
FROM Documents</p>
<p>
WHERE (</p>
<div>
<p>
BandOneMinHashAlgorithmOne = 1 AND</p>
<p>
BandOneMinHashAlgorithmTwo = 3 AND</p>
<p>
BandOneMinHashAlgorithmThree = 6 AND</p>
<p>
BandOneMinHashAlgorithmFour = 0</p>
</div>
<div><p>
) OR<br />
(</p><div>
<p>
BandTwoMinHashAlgorithmOne = # AND</p>
<p>
BandTwoMinHashAlgorithmTwo = # AND</p>
<p>
BandTwoMinHashAlgorithmThree = # AND</p>
<p>
BandTwoMinHashAlgorithmFour = #</p>
</div><p>
) OR (</p><div>
<p>
BandThreeMinHashAlgorithmOne = # AND</p>
<p>
BandThreeMinHashAlgorithmTwo = # AND</p>
<p>
BandThreeMinHashAlgorithmThree = # AND</p>
<p>
BandThreeMinHashAlgorithmFour = #</p>
</div><p>
) OR (</p><div>
<p>
BandFourMinHashAlgorithmOne = # AND</p>
<p>
BandFourMinHashAlgorithmTwo = # AND</p>
<p>
BandFourMinHashAlgorithmThree = # AND</p>
<p>
BandFourMinHashAlgorithmFour = #</p>
</div><p>
) OR (</p><div>
<p>
BandFiveMinHashAlgorithmOne = # AND</p>
<p>
BandFiveMinHashAlgorithmTwo = # AND</p>
<p>
BandFiveMinHashAlgorithmThree = # AND</p>
<p>
BandFiveMinHashAlgorithmFour = #</p>
</div><p>
)</p></div>
<p>
This explanation completely glosses over why this works and what combination of bands and rows you should construct when looking for similar documents. If you want to get into that detail, take a look at <a href="http://infolab.stanford.edu/~ullman/mmds/ch3.pdf">http://infolab.stanford.edu/~ullman/mmds/ch3.pdf</a>.</p>
</div>||||I||||Skip to main content

 Search This Blog

 Matt's Blog

 MinHash for dummies

 * Get link
 * Facebook
 * Twitter
 * Pinterest
 * Email
 * Other Apps
 November 14, 2013
 Duplicate document detection is becoming increasingly important for businesses that have huge collections of email, web pages and documents with multiple copies that may or may not be kept up to date.

 MinHash is a fairly simple algorithm that from all my Googling has been explained very poorly in blogs or in the kind of mathematical terms that I forgot long ago. So in this article I will attempt to explain how MinHash works at a practical code level.

 Before I start, please take a look at http://infolab.stanford.edu/~ullman/mmds/ch3.pdf. That document goes into a lot of theory, and was ultimately where my understanding on MinHash came from. Unfortunately it approaches the algorithm from a theoretical standpoint, but if I gloss over some aspect of the MinHash algorithm here, you will almost certainly find a fuller explanation in the PDF.

 I'll also be using pseudo Java in these examples instead of traditional math. This means when I use terms like Set, I am referring to the group of classes that implement a Set in Java. Of course a set in Java shares a lot of properties with a set in maths, but keep in mind that this is written from a developers point of view.


 What does it mean when we talk about document similarity?

 The whole point of MinHash is to efficiently answer the question "How similar is this document to that document".

 Before we can answer that question, we need to look at a more simple example of two sets of strings and determine how similar they are.

 Here are our two sets:

 Set a = new Set(["chair", "desk", "rug", "keyboard", "mouse"]);
 Set b = new Set(["chair", "rug", "keyboard"]);

 A measure of how similar these two sets are is known as the Jaccard Coefficient. It is calculated as number of common elements / (total number of elements - number of common elements).

 In our case we have 3 common elements: "chair", "rug" and "keyboard". We have a total of 8 elements. So the Jaccard Coefficient = 3 / (8 - 3) = 0.6, or 60%. http://www.planetcalc.com/1664/ is an online calculator that you can play around with to determine the similarity of two sets.


 Documents as sets

 While a document can be though of as a giant set of words, we don't just break down a document into individual words, place them in a set and calculate the similarity, because that looses the importance of the order of the words. The sets

 Set a = new Set(["I", "went", "to", "work", "today"]);
 Set b = new Set(["today", "I", "went", "to", "work"]);

 would be considered 100% similar, even though they clearly are not.

 Instead we break a document down into what are known as shingles. Each shingle contains a set number of words, and a document is broken down into total words - single length + 1 number of shingles. So if a document contained a single sentence of "The quick brown fox jumps over the lazy dog", that would be broken down into the following 5 word long shingles :
 1. The quick brown fox jumps
 2. quick brown fox jumps over
 3. brown fox jumps over the
 4. fox jumps over the lazy
 5. jumps over the lazy dog
 So our document as a set looks like:

 Set a = new Set(["The quick brown fox jumps", "quick brown fox jumps over", "brown fox jumps over the", "fox jumps over the lazy", "jumps over the lazy dog"]);

 These sets of shingles can then be compared for similarity using the Jaccard Coefficient.

 Optimizing the process

 So we now have a way to compare two documents for similarity, but it is not an efficient process. To find similar documents to document A in a directory of 10000 documents, we need compare each pair individually. This is obviously not going to scale well.

 What we can do to reduce some cycles is compare sets of randomly selected shingles from two documents. So for a document that is 10000 words long, we break it down into 9996 shingles, and randomly select say 200 of those to represent the document. If the second document is 20000 words long, we boil that down from 19996 shingles to another set of 200 randomly selected shingles.

 Now instead of matching 9996 shingles to 19996 other shingles, we are are comparing 200 shingles to another 200 shingles. We have reduced our workload at the expense of accuracy, but this is still good enough for most scenarios.

 NOTE
 So just how much accuracy did we sacrifice by comparing only a small subset of randomly selected shingles? I actually don't know, but I assume it sits on a bell curve where the number of random selections improves the accuracy to a point where more random selections won't provide any meaningful increase in accuracy. If you know the math behind this, please leave a comment.

 I chose 200 random selections after reading http://blog.cluster-text.com/tag/minhash/.

 Computing and saving the random shingle selections

 So this is where MinHash comes in.

 We could save the 200 randomly selected shingles, but storing variable length strings kinda sucks. It complicates database design and comparing strings is slow.

 The clever part about MinHash is that it allows us to save integers instead of strings, and also takes the hassle out of randomly selecting shingles. It works like this.

 1. Break down the document a set of shingles.
 2. Calculate the hash value for every shingle.
 3. Store the minimum hash value found in step 2.
 4. Repeat steps 2 and 3 with different hash algorithms 199 more times to get a total of 200 min hash values.

 At this point instead of 200 randomly selected shingles, we have 200 integer hash values. This is effectively a random selection of shingles, because a good hash algorithm is supposed to generate a number that is as likely to be large as it is likely to be small. This kind of distribution of hash codes is what hashing is all about, so selecting the smallest hash is, for all intents and purposes, a random selection of a shingle.


 Um, 199 more hash algorithms? WTF!

 So you see the String.hashCode() method, but where do these other 199 hash codes come from? This is the step that most explanations on the MinHash algorithm conveniently leave out.

 The short answer is that you XOR the value returned by String.hashCode() with 199 random numbers to generate the 199 other hash code values. Just make sure that you are using the same 199 random numbers across all the documents.

 If you want some more detail on why this works, see http://stackoverflow.com/a/19711615/157605.


 Great, but I still have to compare every document to every other document. Can this be optimized?

 This is where the second neat trick of MinHash comes in.

 Locality sensitive hashing (LSH) involves generating a hash code such that similar items will tend to get similar hash codes. This is the opposite of what .hashCode() does.

 LSH allows you to precompute a hash code that is then quickly and easily compared to another precomputed LSH hash code to determine if two objects should be compared in more detail or quickly discarded.

 We don't actually calculate a LSH hash code as such, but the idea of a boiling down a complex object (like our collection of minhash codes) into something that is quickly and easily compared with other complex objects is still applicable.

 What we do is take the collection of minhash values, and categorize them into bands and row. For the sake of simplicity we'll assume each document has 20 minhash values. We will break them down into 5 bands with 4 rows each. Also for the sake of simplicity we'll assume that .hashCode() (and any number XORed with it) results in a number between 0 and 9.

 So conceptually the minhash values from 5 documents in the first of the 5 bands and its rows looks like this.

 MinHash Algorithm One MinHash Algorithm Two MinHash Algorithm Three MinHash Algorithm Four
 Document One 1 3 6 0 
 Band One Document Two 2 3 1 0 
 Document Three 1 3 6 0 
 Document Four 2 1 3 1 
   
 
 What we are looking for are rows within a band that are the same between documents. Document One and Document Three in this case both have rows with values 1, 3, 6, 0. This tells us that these two documents should be compared for their similarity.

 Although it is not shown here, you should look through Bands Two - Five looking for documents that share rows. Any documents that share rows in any bands should be compared for their similarity.

 This is useful when you have a document, and you want to know which other documents to compare to it for similarity. I'll assume that the minhash values are stored in SQL, so to get out candidates for comparison you would write:

 SELECT DocName
 FROM Documents
 WHERE (
 BandOneMinHashAlgorithmOne = 1 AND
 BandOneMinHashAlgorithmTwo = 3 AND
 BandOneMinHashAlgorithmThree = 6 AND
 BandOneMinHashAlgorithmFour = 0
 ) OR
 (
 BandTwoMinHashAlgorithmOne = # AND
 BandTwoMinHashAlgorithmTwo = # AND
 BandTwoMinHashAlgorithmThree = # AND
 BandTwoMinHashAlgorithmFour = #
 ) OR (
 BandThreeMinHashAlgorithmOne = # AND
 BandThreeMinHashAlgorithmTwo = # AND
 BandThreeMinHashAlgorithmThree = # AND
 BandThreeMinHashAlgorithmFour = #
 ) OR (
 BandFourMinHashAlgorithmOne = # AND
 BandFourMinHashAlgorithmTwo = # AND
 BandFourMinHashAlgorithmThree = # AND
 BandFourMinHashAlgorithmFour = #
 ) OR (
 BandFiveMinHashAlgorithmOne = # AND
 BandFiveMinHashAlgorithmTwo = # AND
 BandFiveMinHashAlgorithmThree = # AND
 BandFiveMinHashAlgorithmFour = #
 )

 This explanation completely glosses over why this works and what combination of bands and rows you should construct when looking for similar documents. If you want to get into that detail, take a look at http://infolab.stanford.edu/~ullman/mmds/ch3.pdf.
 * Get link
 * Facebook
 * Twitter
 * Pinterest
 * Email
 * Other Apps

 Comments

 Bill Dimm said…
 Regarding how the accuracy depends on the number of hash functions, that comes from the Central Limit Theorem. If you compute the mean of a bunch of independent samples from the same probability distribution, the probability distribution of the mean itself will be normal (i.e. bell-shaped) if you take enough samples even if the probability distribution of the individual samples is far from normal. The standard deviation of the bell-shaped distribution for the mean is given by the standard deviation of the individual sample distribution divided by sqrt(N), where N is the number of samples.

 For MinHash, you are taking the set of all unique shingles (between the two documents) and trying measure the fraction that are common to both documents, which is defined to be the document similarity. If the fraction is p, a randomly selected shingle has probability p of being a common shingle, and probability 1-p of being a non-common shingle -- this is known as a Bernoulli distribution. The standard deviation of a Bernoulli distribution is sqrt(p*(1-p)). So, the average of N Bernoulli samples will have a normal (bell-shaped) distribution with standard deviation sqrt(p*(1-p)/N). But, we don't know p -- that's what we are trying to measure. The largest possible value for the standard deviation occurs when p=0.5, so we know the standard deviation is at most 0.5/sqrt(N). To have 95% confidence that the true value is within our estimated range, the range should be plus or minus 2 standard deviations. So, a conservative estimate for the uncertainty in our result is plus or minus 1/sqrt(N).

 If we take N=200, our result is plus or minus 1/sqrt(200) = 0.07. So, if 100 or our 200 sampled shingles are common to both documents we know that p is in the range 0.43 to 0.57. If p is close to 0 or 1 the error bar will actually be smaller than 0.07, but we don't that that will be the case when we pick N. If we took four times as many samples the error bar would only be cut in half due to the sqrt.

 Useful references:
 http://en.wikipedia.org/wiki/Central_limit_theorem
 http://en.wikipedia.org/wiki/Bernoulli_distribution
 http://en.wikipedia.org/wiki/68–95–99.7_rule
 6:01 am
 Ryan Moulton said…
 This comment has been removed by the author.
 10:56 am
 Ryan Moulton said…
 If you'd like to incorporate weights info the minhashes, (for instance, for counting tokens more than once, or for idf weighting) I wrote a guide for how to do that here: Minhash
 10:57 am
 Unknown said…
 Thanks for Sharing This Article.It is very so much valuable content. I hope these Commenting lists will help to my website
 blockchain online training
 best blockchain online training
 top blockchain online training
 10:58 pm
 ed pills said…
 This is really interesting, You are a very skilled blogger. I have joined your feed and look forward to seeking more of your magnificent post. Also, I have shared your site in my social networks!
 11:32 am
 ed medication said…
 Its not my first time to visit this website, i am visiting this site dailly and get fastidious data from here all the time.
 11:49 am
 erectile dysfunction treatment said…
 Hi there, just became alert to your blog through Google, and found that it is really informative. I'm going to watch out for brussels. I will appreciate if you continue this in future. Many people will be benefited from your writing. Cheers!
 3:49 am
 erection pills said…
 I'm gone to say to my little brother, that he should also pay a visit this web site on regular basis to obtain updated from most up-to-date news.
 3:51 am
 sparkdeveloper said…
 thank you . can you share the code ? please.
 11:13 am
 Anonymous said…
 We are well established IT and outsourcing firm working in the market since 2013. We are providing training to the people ,
 like- Web Design , Graphics Design , SEO, CPA Marketing & YouTube Marketing.Call us Now whatsapp: +(88) 01537587949
 Digital marketing training
 good post Mobile XPRESS
 Free bangla sex video:Delivery Companies in UK
 good post Mobile XPRESS
 8:38 pm
 CrownQQ Official said…
 CrownQQ Agen DominoQQ BandarQ dan Domino99 Online Terbesar

 Yuk Buruan ikutan bermain di website CrownQQ
 Sekarang CROWNQQ Memiliki Game terbaru Dan Ternama loh...

 10 permainan :
 => Poker
 => Bandar Poker
 => Domino99
 => BandarQ
 => AduQ
 => Sakong
 => Capsa Susun
 => Bandar 66
 => Perang Baccarat
 => Perang Dadu

 Keunggulan bermain di CrownQQ :
 => Bonus Refferal 20%
 => Bonus Turn Over 0,5%
 => Minimal Depo 20.000
 => Minimal WD 20.000
 => 100% Member Asli
 => Pelayanan DP & WD 24 jam
 => Livechat Kami 24 Jam Online
 => Bisa Dimainkan Di Hp Android
 => Di Layani Dengan 5 Bank Terbaik
 => 1 User ID 10 Permainan Menarik
 => Menyediakan deposit Via Pulsa

 Link Resmi CrownQQ:
 - mastercqq.net
 - mastercqq.org

 Info Lebih lanjut Kunjungi :
 Website : DominoQQ Online
 Daftar CrownQQ : Poker Online
 Info CrownQQ : Kontakk
 Linktree : Agen Poker Online

 WHATSAPP : +6287771354805
 Line : CS_CROWNQQ
 Facebook : CrownQQ Official
 Kemenangan CrownQQ : Agen BandarQ
 12:53 pm
 Venny Fransiska Chen said…
 BandarQ Online
 5:45 am
 Rajabandarq said…
 Agen bandarq
 Agen bandarq
 Agen bandarq
 Agen bandarq
 Agen bandarq
 Agen bandarq
 Agen bandarq
 Agen bandarq
 Agen bandarq
 Agen bandarq
 8:33 pm
 salar said…
 The right place to learn to create websites and digital marketing strategies. Trainers explain real-time examples for clear understanding.
 3:35 pm
 jeslynwang said…
 Nagaqq Yang Merupakan Agen Bandarq terbaik , Domino 99, Dan Bandar Poker Online Terpercaya di asia hadir untuk anda semua dengan permainan permainan menarik dan bonus menarik untuk anda semua

 Bonus yang diberikan NagaQQ :
 * Bonus rollingan 0.5%,setiap senin di bagikannya
 * Bonus Refferal 10% + 10%,seumur hidup
 * Bonus Jackpot, yang dapat anda dapatkan dengan mudah
 * Minimal Depo 15.000
 * Minimal WD 20.000
 * Deposit via Pulsa TELKOMSEL
 * 6 JENIS BANK ( BCA , BNI, BRI , MANDIRI , CIMB , DANAMON )

 Memegang Gelar atau title sebagai AGEN POKER ONLINE Terbaik di masanya

 11 Games Yang di Hadirkan NagaQQ :
 * Poker Online
 * BandarQ
 * Domino99
 * Bandar Poker
 * Bandar66
 * Sakong
 * Capsa Susun
 * AduQ
 * Perang Bacarrat
 * Perang Dadu
 * BD QQ (New Game)


 Info Lebih lanjut Kunjungi :
 Website : NAGAQQ
 Facebook : NagaQQ official
 WHATSAPP : +62 87833350051
 Line : Cs_nagaQQ
 TELEGRAM :+855967014811
 8:36 pm
 Tamizhakarthic said…
 nice post.
 Best Digital Marketing Training In Sivakasi
 Best Digital Marketing Training
 8:10 pm
 Titration Calculator said…
 good work!
 Titration Calculator
 8:32 pm
 Tamizha Karthic said…
 Thank you for sharing knowledgeable blog with us Facebook ads mastery course in tamil
 11:08 pm
 Caterers in Faridabad said…
 It's been nice to see such articles!!
 I would Love to share
 6:20 pm
 Arnold DK said…
 Nice article, it is very valuable information. Thanks for sharing these information with all of us. whatsapp mod

 7:25 pm
 Unknown said…
 APOTAC
 Python Training
 8:46 pm
 sateesh said…
 nice artcle Digital Marketing agency
 8:17 pm
 LINUS PROJECTS (INDIA) said…
 Nice articles and your informatin valuable and good artices thank for the sharing information Brake Oil Plant
 12:11 am
 SOFTWARE COMPANY said…

 a fantastic article Thank you for sharing. Everyone seeking a software agency should read this post.
 Brisk logic is a Mohali-based software design, app development, and web design firm.
 digital transformation and business automation
 3:52 pm
 Anonymous said…
 The search engine determines whether or not the results of the query were accurate based on the users’ actions. If you add enough keywords in the description, title, tags, and transcript then your video will appear in more search results. The digital marketing agency London will tell you that comments, subscribers and likes on a YouTube video increase the relevancy of a post. You can get more hits through other users if your keywords are relevant.
 11:38 pm
 KPR RUMAH said…
 Rumah subsidi adalah bagian dari program pemerintah agar masyarakat dapat membeli rumah dengan harga dan cicilan yang terbilang cukup ringan. Melalui Kementerian Perumahan Rakyat (Kemenpera), pemerintah menggalakkan sebuah program satu juta rumah, dan salah satunya adalah KPR rumah bersubsidi. Sebagai informasi, rumah bersubsidi merupakan rumah yang mendapat kemudahan dari pemerintah yakni berupa bebasnya pajak dan cicilan dengan bunga yang sangat rendah. Selain itu, keunggulan lain yang bisa didapatkan dari rumah bersubsidi yakni memiliki suku bunga flat hingga lunas.
 Rumah
 12:34 pm
 Customer Support | Live Chat Service said…
 How to Unsend an Email in Outlook App?

 Check out the steps mentioned to know how to unsend an email in Outlook app. Select the sent items folder in the folder panel on the left of Outlook window. Here, open message that you want to recall and then double-click to open message. If you choose the message and it appears in reading panel then it will not allow to recall this message.If you have ribbon then choose actions and then recall this message from message tab. choose to delete unread copies of message or delete unread copies or replace it with the new one by clicking on OK. Lastly, if you are sending the replace message then compose new one and choose to send.


 How to Setup Bellsouth Email on iPhone?

 There are times when users have the query about how to setup Bellsouth email on iPhone then start by setting up your email. Now, launch the settings app on iPhone and choose mail, contacts, and calendar. Touch to add accounts under the accounts heading and choose other than account type. After that, click to add an email account. Now, enter your name, Bellsouth email address and password in the requested field. After that, you need to enter the Bellsouth email details in the requested fields. Now, choose to next to let your iPhone device check if settings are working properly or not. Lastly, you need to customize the email settings as per your personal preference.


 Troubleshooting Steps for Yahoo Not Working

 If you are an iPhone user then sometimes users do encounter with the issue of Yahoo not working. If you are the one facing same issue then check out the steps. For this, press and hold the power button along with volume up button. Within few seconds, you will see power-off slider. After that, drag the slider and let your device turn off properly. Now, to turn on press and hold the power button and then wait till the Apple logo appears. These are the steps that users need to follow to smoothly deal with the issue of Yahoo not working issue.

 How to Turn Off Outlook Notifications on Apple Watch?

 Check out the steps to know about to know how to turn off Outlook notifications on Apple Watch. If you don’t want to receive email notifications on Apple Watch, then you can smoothly turn it off by going to my watch (tab) > mail > custom > under alerts. You can access your iPhone settings by going to the settings application. After that, you can access notifications by going to the notifications section. The included section should contain a listing of Outlook. Lastly, to access Outlook and choose the tab. Lastly, these are the steps to turn off Outlook notifications on Apple Watch smoothly.
 5:36 pm
 Gerry Max said…
 Using Chrome's Incognito mode when using a public computer or someone else's device is a very useful feature. It prevents your browsing history from being seen by others. You can also use it on your own device for privacy reasons. However, Chrome does not provide an option to disable incognito mode. But there is another way to Disable Incognito Mode Chrome Browser. To achieve this, launch the Chrome app and tap the Square icon to switch between incognito and regular windows. You can tap the X icon to close the incognito mode on any iPhone series upon reaching this point. If you prefer not to close the incognito mode completely, you can toggle between regular and incognito mode.
 6:58 pm
 Gerry Max said…
 Various methods can be used to resolve the various CenturyLink Email related issues. So, to resolve the issue, check whether the CenturyLink email configuration settings are correct for both the servers, Incoming Mail Server and the Outgoing Mail Server. If you can't access CenturyLink email
 , then the issue can be with your log-in account login password. So, try to change your password and then re-login to your account. By deleting the unnecessary spam and junk mails, then moving them to your recycle bin or trash, and then deleting them once again from there, you can easily troubleshoot your CenturyLink Email problem.
 10:29 pm
 Gerry Max said…
 Any malfunction with Yahoo's products may cause your account to be suspended. Yahoo is very strict about maintaining the quality of its products and services. The Sign-in Helper can be used immediately to regain access to your Yahoo account if it has been locked temporarily. To Unlock Yahoo Email, use the Yahoo Help Forum Page. Now, you must click on the 'Account Locked' message. Now click on 'Sign-in Helper' and enter your Yahoo Mail address or phone number.
 7:20 pm
 murtazagrn said…
 . On Friday the 13th, no less! To be precise, Friday, April 13th, 2029. When 99942 Apophis was found in 2004, scientists believed it had a slim chance of hitting Earth.
 Facts About Subway

 Fun Facts about Friday
 9:08 pm
 website design company said…
 Thanks for sharing the post.
 web design company hyderabad
 5:15 pm
 Travel Bogor Bandung said…
 CV Nabil menyediakan Travel Bogor Bandung dan Bandung Bogor – Kami merupakan shuttle bogor – bandung dan sebalik nya. Dengan konsep menjemput door to door. Umum nya pada setiap orang, masalah waktu bisa dibilang merupakan satu pertimbangan yang utama dikarenakan faktor penentu, terlebih ada beberapa bagi mereka yang memang sangat dikejar kejar waktu atau memiliki jadwal yang sangat singkat.
 Travel Bogor Bandung Rental Mobil Bis
 2:27 pm
 Neil Taylor said…
 As discussed, if you have lost or forgotten the Spectrum email account password, you need to follow the Charter email password recovery process. Once you complete the steps of password recovery, you can use the new password to log into your Spectrum account and access your emails. Follow the below-mentioned steps to reset Charter password:

 Full read: https://www.gethumanhelp.com/how-to-change-charter-spectrum-email-password/
 4:47 pm
 komputer said…
 mungkin sudah tahu beberapa trik internet dan komputer yang membuat aktivitas harianmu lebih efektif dan efisien.Memang terdapat banyak sekali trik internet dan komputer yang sangat mempengaruhi aktivitas harian kita di luar sana, namun tentu tidak semuanya sudah kita ketahui.
 wisata komputer
 12:59 pm
 support printer help said…
 When it comes to providing support on hp printer offline, Support Printer Help has experience in making it easy to solve customer problems. We can solve all kinds of printer related problems quickly and very easily. Whether it’s a driver related issue, software issues or any hardware changes required in their printer, we understand the customer’s point of view first and identify the exact problem and fix the problem without taking the printer out of the house.
 8:53 am
 murtaza said…
 SNS Bank– Its special feature is that it offers an EU payment option. With the help of it, an individual can open a bank account anywhere in the EU and there is no requirement of a BSN.
 Bank Account in the Netherlands
 4:15 am
 rohit said…
 How To Open an Offshore Bank Account In 2022?- ODINT Consulting

 Often foreigners have financial transactions in other countries, open an offshore bank account if you want an effective strategy to implement profits overseas and also save in trading.

 Open Offshore Bank Account

 Open Offshore Bank Account
 8:48 pm
 rohit said…
 Dubai Company Registration 2022 - 100% Remote Incorporation and Ownership

 Your 100% dubai company registration guide- complete details, process, documentation. 100% ownership and remote incorporation

 DUBAI Company registration

 DUBAI Company registration
 11:37 pm
 Anonymous said…
 Difference between MOA and AOA with Comparison Chart- ODINT Consulting

 The key deference between memorandum of association and articles of association are stated here with the help of a comparison chart and both MOA and AOA are defined as well.

 Difference between MOA and AOA

 Difference between MOA and AOA
 8:32 pm
 shivam said…
 An Employment Pass Singapore is provided to foreign experts who are employed by Singaporean companies and meet all of the eligibility requirements. The employer is the third party who has been appointed to apply on the candidate's behalf. As a result, employees are compensated with a wage of at least $4,500 per month. It's good for up to two years, or three years if you're renewing an employment permit. Medical insurance is not likely to be offered in this situation, as companies will have to determine whether or not to do so themselves.
 5:21 pm
 rohit said…
 Company Registration In Poland 2022 | Complete Details

 Complete guide on company registration in Poland with complete process, documentation, and tax details. Register your company with our industry experts.

 Poland company registration

 Poland company registration
 6:40 pm
 Orthohandpartners said…
 Nice blog this is very informative and very easy too read and i also love your writing style

 read my blog Knee Replacement
 8:24 pm
 rohit said…
 Dubai Company Registration 2022 - 100% Remote Incorporation and Ownership

 Your 100% dubai company registration guide- complete details, process, documentation. 100% ownership and remote incorporation.

 UAE company registration
 UAE company registration
 7:33 pm
 shivam said…
 Thanks for sharing. Really, this is very helpful for all.

 Importance Of Poland Business Visa
 7:31 pm
 rohit said…
 USA Company Registration, Process and Complete Details

 Offshore USA company registration- USA company formation services by Odint consulting. Expand your business in the USA.

 usa company registration

 usa company registration
 8:14 pm
 rohit said…
 Silent Partner - Definition, Purpose & Benefits | ODINT Consulting

 A silent partner is a company associate who provides funds to an enterprise. They are not involved in the management of the company they are actively financing.

 Silent Partners
 Silent Partners

 1:01 am
 shivam said…
 The Issued Capital is the portion of a firm’s capital contribution that it is permitted to trade throughout its shareholdings. Dependent on the need for funds, a company can offer all or a piece of its stock.
 6:56 pm
 murtaza said…
 A Trademarkcan be defined as the right to a specific and unique name, logo, or symbol that represents your brand or product. It is basically a right to intellectual property that protects the identity of a business or a brand.
 7:04 pm
 rohit said…
 Larisa Realtech: Affordable, Residential, Commercial Properties

 Larisa Realtech Pvt. Ltd. is one of the fastest-growing Real Estate Advisory Firm in Gurugram. We aspire to touch thousands of people by helping them to buy their dream properties.

 luxury flats in gurgaon

 luxury flats in gurgaon

 9:19 pm
 rohit said…
 Limited Liability Partnership (LLP) Registration In India - ODINT Consulting

 Limited Liability Partnership (LLP) Registration In India comprises all the advantages one would get from a company, and a separate partnership firm.

 LLP In india

 LLP In india
 1:17 am
 rohit said…

 Affordable Home Gurgaon - Project Under Affordable Housing Gurgaon

 Buy Best Affordable Housing Projects in Gurgaon, Ready to Move Apartments, Flat, Community Shops, and Affordable Home gurgaon at an Affordable Price.

 Best Affordable Housing Projects in Gurgaon

 Best Affordable Housing Projects in Gurgaon

 3:56 pm
 shivam said…
 The term "UNIQUE IDENTIFICATION NUMBER" is used to describe a number that is used to identify It's a numerical sequence in a programme that corresponds to a single body. UIDs enable the thing to be addressed in order to be viewed and interacted with.

 Everything that has to stand out from the crowd, such as people, businesses, equipment, or locations, can be given a unique identity. These various returns are often allotted depending on the demands of the intended area, but they can also be produced arbitrarily using an approach, distributed gradually, or chosen by the consumer.

 Read more: what is uid number
 5:47 am
 rohit said…
 Best luxury floors in Gurgaon for sale at the best price

 we provide the best luxury floors in Gurgaon, having 2 BHK, 3BHK, and 4 BHK at the best price with luxurious amenities and the best location so, that you can live a luxurious and carefree life.

 luxury floors in Gurgaon

 luxury floors in gurgaon

 4:24 pm
 rohit said…

 M3M Atrium 57 Commercial Shop in Gurgaon

 M3M atrium 57 is new commercial project Gurgaon functions as an in-depth variety of centers that great meet the desires of cutting-edge business men.
 Your working environment and its adapt inside big business influence the viewpoints of clients, thus having an astonishing spot, play out a huge job.

 M3M atrium 57

 M3M atrium 57
 3:58 pm
 Anonymous said…
 Appointment Of Nominee Director-Complete Guide

 A person appointed to the board of directors of a company by an organization, in which the establishment has an asset is known as a nominee director.

 Nominee Director
 Nominee Director

 6:39 pm
 rohit said…
 Additional Wage (AW) Ceiling - How To Calculate With Examples

 Additional Wages are supplied to the workers as a separate way of remuneration. This has nothing to do with their monthly wage. Learn How to calculate your Additional Wages.


 Additional Wage(AW)


 Additional Wage(AW)

 9:04 pm
 rohit said…

 Singapore Work Passes And Permits - Meaning & Types Discussed

 To work in Singapore, a foreigner would require Singapore work passes and permits. Depending on the type of work, level of skill, and duration of your work, there are different types of work passes In Singapore.

 Singapore Work Passes And permits

 Singapore Work Passes And permits

 10:25 pm
 rohit said…
 M3M Corner Walk Commercial Property in gurgaon

 M3M Corner walk is bound to be the focal point of business Intended to be the preferred hotspot for upscale retail outlets and large corporates M3M Corner Walk is its exclusive corner location on Golf Course Road Ext. at sec-74, Gurgaon.

 M3M Corner Walk in gurgaon

 M3M Corner Walk in gurgaons
 4:24 pm
 rohit said…

 Hero Homes 104 Luxury Home in sector 104 Gurgaon

 Hero Homes Sector 104 are the luxury homes that Hero Realty Private Limited has presented, one of India’s most respected business groups.There are 2 and 3 BHK homes that range from 683 to 1082 sq. ft. to 1082 sq. ft. to 1082 sq.The project is located at Sector 104 on the Dwarka Expressway. It offers stunning views over the surrounding area.

 Hero Homes Sector 104

 Hero Homes Sector 104s
 8:53 pm
 rohit said…
 What is the Netherlands BSN (burgerservicenummer) number all about?


 While perusing about living and working in the Netherlands, you probably run over the word BSN number. Getting the BSN number is the first step that an individual ought to take assuming they are wanting to move or work in the Netherlands.
 Each resident who is living in the Netherlands has an exceptional resident recognizable proof number (BSN), individuals who are brought into the world in the Netherlands consequently have it (Dutch Government issue this number with birth endorsement) and outsiders need to apply for it when they show up.

 Netherlands BSN number
 Netherlands BSN numbers

 9:24 pm
 rohit said…

 Godrej Meridien sector 106 [Luxury Apartment] at Dwarka Expressway

 This Godrej Meridien Three-storied structure has an impressive glass façade and house an array of sports and entertainment facilities.These are homes crafted for the select few with wellness, an active life and luxurious amenities.The 6132 sq. m. sprawling clubhouse, is one of the finest in Gurugram(Dwarka Expressway).

 Godrej Meridien sector 106

 Hero Homes Sector 104
 5:14 pm
 shivam said…
 Every company has a guideline of stages to follow when forming a Private limited company registration in Mumbai. And when we read about India, Mumbai is the center of entertainment, commercial and global financial flow.
 6:06 pm
 rohit said…
 dubai international city

 In the event that you are somebody who is searching for a rural region to live in, Dubai International City is the region you ought to consider. It is a very well known place among individuals looking for in-spending plan homes for lease. Dubai is a place where there is different societies and sees individuals from different ethnicities getting comfortable consistently. In this way, Dubai International City is a region that does equity to Dubai's cosmopolitan and contemporary way of life.


 dubai international city



 12:47 am
 rohit said…
 UTR Number

 You are super lucky because we at ODINT Consulting take it as our goal to help people like you in setting up your business. We have all the necessary knowledge about the UTR number. So, to help you understand the UK’s UTR Number, types of Unique Taxpayer Reference Numbers, why do you need them, how to find a Unique Taxpayer Reference Number of UK, and other topics revolving around them, I’ve penned down this guide.

 UTR Number

 12:59 am
 shivam said…
 Before we dive into the entire matter, let’s look at some fundamentals. According to MCA (Ministry of Corporate Affairs) laws, India has made it incredibly straightforward and uncomplicated to establish a new business in India within a short amount of time.

 Read More: Company Registration Certificate in India
 8:24 pm
 rohit said…
 holding company

 A parent company is a kind of company or an organization named ‘a holding company‘ is an independent business entity that operates under certain legal guidelines throughout its time.

 holding company

 3:04 am
 murtaza said…
 The UEN was first presented back in year 2009. From that point, these following substances which are lawfully enrolled to work in Singapore are required and can apply to have a UEN:

 Neighborhood Companies
 Organizations
 Restricted Liability Partnerships (LLPs)
 Delegate Offices
 Social orders
 Worker's guilds
 UEN Singapore
 7:36 pm
 rohit said…
 onstruction company in Dubai

 Choosing Dubai as your construction company location is a great decision. The reason is, Dubai is a fast-paced country and the most attractive country. This country has evolved and has proven to become the most quickly growing nation. The beauty of this country is at its peak, and it is the right time for you to benefit from it by establishing a business in Dubai. It is a nation that has sky-scraping buildings, beautiful sites, and eye-catching beaches.

 onstruction company in Dubai

 12:25 pm
 rohit said…
 Private Company in Poland

 The Polish Limited Liability Company (condensed "sp. z o.o.") is the most well-known type of legitimate substance and can be laid out for any sort of action. It requires a base offer capital of 5,000 PLN and the ostensible worth of an offer should be of something like 50 PLN

 Private Company in Poland

 4:17 pm
 shivam said…
 A PESEL Number is a national number for identification in Poland. The Polish full form of a PESEL number is Powszechny Elektroniczny System Ewidencji Ludności. This is a universal digital structure for population registration. It comprises 11 digits that are known for their uniqueness and are separate for every registered individual. It appears like, YYMMDDPPPPK.
 5:33 pm
 Property in gurgaon said…
 Hi, Thanks for sharing.

 Find the best T and T Realty Services Private Limited is a leading consulting company incorporated in 2017 to drive Social and Economic Growth through REAL ESTATE - safeguarding the Future and creating a Brighter World for Customers, Partners, Communities, and the Environment.

 visit:-

 Property in Gurgaon
 9:22 pm
 rohit said…
 it companies in dubai

 Individuals who see their future in IT organizations ought to realize that there are a few fields to browse. Beginning from fill in as straightforward as Data section, to altered back-end programming. Among the most vigorously enrolling IT organizations comes the IT organizations in Dubai. It isn't covered up that Dubai has a strong substitute the country's monetary development and inutility of hello tech administrations and items. In every one of the Emirates, Dubai has been the most quickly developing city. In this way, on the off chance that you are keen on working in an IT organization, here is a rundown of IT organizations in Dubai organized only for you.


 it companies in dubai
 12:02 am
 murtaza said…
 Poland was formed around 60 million years ago by the tectonic activity of Africa and Europe. With 38.5 million inhabitants, it’s the sixth most populous state in the European Union, spanning 312,696 square kilometers and featuring a mild seasonal temperature. Warsaw is Poland’s biggest capital and metropolis, with other significant cities including, ód, Gdansk, Pozna, and Wroclaw.

 Too read more click here Poland Visa
 3:49 am
 shivam said…
 Permission for infrastructure projects, which covers work done before any bases are laid. The contractor must submit detailed plans of the planned project to the relevant rule to get a permit to build. So, let’s dive into details and know more about the mandatory permits one needs to have to construction company in Dubai.
 3:52 am
 murtaza said…
 A one-line description for General Ledger would be, One of the most necessary accounting records for good business life. To simplify it, a general ledger is a kind of a full record of your business transactions. It includes all the debts you’ve processed since your company started.
 general ledger
 6:42 pm
 rohit said…
 General ledger

 A one-line depiction for General Ledger would be, One of the most vital bookkeeping records for good business life. To improve on it, an overall record is a sort of a full record of your deals. It incorporates every one of the obligations you've handled since your organization begun. Assuming you recall the well established express, "keeping the books", that likewise alludes to dealing with an overall record.

 General ledger

 6:48 pm
 rohit said…
 FSSAI Registration

 Assuming you will begin your food-related firm or any food business in India, then, at that point, you should know about the FSSAI Registration or FSSAI licenses to work such business in India.Moreover, the FSSAI has two sorts of endorsement techniques: a permit and enrollment. Enlistment is frequently expected for all people engaged with negligible food undertakings, while a permit is expected for every one of the people who are in the food business, however not the little food industry.

 FSSAI Registration
 9:37 pm
 shivam said…
 Importance of Company Registration Certificate

 The following are some of the reasons why a company registration certificate is necessary for India:

 A legal document proving the company’s identity and existence.
 A corporation is a separate legal entity. As a consequence, the MCA issues a certificate of incorporation that contains a unique Corporate Identification Number (CIN), which serves as the entity’s unique identifier.
 This certificate proves that the company has registered with the RoC. As a consequence, it may begin activities in line with the conditions of the MOA.
 7:05 pm
 Affordable Home in Gurgaon said…
 Godrej Serenity 2BHK and 3BHK luxury apartments in Sector 33, Gurgaon

 Godrej Serenity concocting infection free homes in south Gurgaon. GODREJ SERENITY offers 2BHK and 3BHK extravagance lofts. This lavish way of life beginning with 71 Lacs* Only. These extravagance lofts ideal mix of innovation, nature, and wellbeing. So assuming you are looking for a home that can give a top notch home or better return. Then, at that point, Stop your examination and simply purchase this cutting edge property.Godrej Serenity has top-class development quality since it's created by GODREJ PROPERTIES. Furthermore, Godrej Properties are constantly known for on-time ownership and development quality.


 Godrej Serenity

 Godrej Serenity
 7:03 pm
 rohit said…

 company registration certificate

 Each element that longings to work inside the legitimate system should initially get a Company Certificate Registration. To get the Registration Certificate on the principal attempt, the documentation should be accurate.To have a Company Registration Certificate a requirements to satisfy the standards of the Ministry of Corporate undertakings, I.e. MCA.On the off chance that you are another in the business area and wish to comprehend the part of Registration Certificates in India, then, at that point, this article is for you.This post will help you in having a deep understanding of business Registration Certificates from the base to up.

 company registration certificate

 7:58 pm
 Affordable Home in Gurgaon said…
 Sobha City 108- Luxury 2BHK & 3BHK Flats Starting @1.52Cr*

 Sobha City has intentionally made at Sector 108 Dwarka Expressway which is the fastest making area of Gurgaon. This is a confidential errand to which you can call a dream home for an age. Enthusiastically made 2 and 3 BHK Apartments with the top level comforts, Sobha City Dwarka Expressway is for the people who wish for a satisfying lifestyle. Spread in excess of 39 segments of land where only 14% of the everything out land is committed for the advancement of apexes and the rest is planned for open green districts and comforts.

 Sobha City 108

 Sobha City 108
 9:00 pm
 Affordable Home in Gurgaon said…

 Ashiana Anmol ready to move Luxury Home For KIDS in Sector 33, Sohna, Gurgaon

 Ashiana Anmol Sohna is Ready to move condos in Sohna which is attempted to find a kid's genuine potential by laying out a youngster driven environment to stimulate their perception, creative mind, and conviction. The undertaking is spread over 13.33 areas of land and has 5 designs of 300 units. These high rise lofts have G+14 floors that offer 2 and 3BHK extravagance pads with tip top merchandise and establishments. The size of lofts goes from 118 sq. ft to 182 sq. ft.

 Ashiana Anmol


 Ashiana Anmol
 10:49 pm
 rohit said…



 Meaning of a Company Registration Certificate

 A Company Registration Certificate is otherwise called Certificate of Incorporation or COI or Letter of Incorporation. It is an authoritative report or testament gave by the Ministry of Corporate Affairs to an organization in India after effectively finishing the enrollment cycle

 Meaning of a Company Registration Certificate

 3:02 pm
 murtaza said…
 Bathroom mirror cabinet has an amazing storage capacity and it includes brush holders, comb stand, and other shelves according to your requirements. It is an ideal way to organize all your bathroom essentials at a single place. It is available in various designs and different colour options.

 bathroom mirror cabinet
 7:55 pm
 Affordable Home in Gurgaon said…
 spaze Grand Central 114 Commercial Properties SCO Plots in Sector 114, Gurgaon

 Spaze Grand Central 114 is a surprising Shop-cum-workplaces (SCO) design with a rich social framework, a humming biological system, and a solid base of purchasers.
 It's the ideal blend to feature your business for a fantastic scope and to allow the customers to get the best in a look.Fantastic Central 114 has B + G + 4 Floors + Terrace (according to DTCP endorsed standard design control sheet) Sprawling across 12.3* sections of land with Land proprietorship and Two-side passage.

 Spaze Grand Central 114

 Spaze Grand Central 114
 10:23 pm
 murtaza said…
 An outbound investment can be comprehended as any form of investment that is conducted by a person or business by venturing into the shares of a completely owned subsidiary company or a combined investment that is done outside of India.

 Outbound Investment
 3:00 am
 rohit said…
 types of companies in Hong Kong

 Types Of Hong Kong Companies
 A few investors are liking to begin their organizations abroad, and Hong Kong is one the essential spot for each business person to begin their business.One of the significant motivations to enter a worldwide market is simply to acquire the honor of Hong Kong's assessment accommodating locale. Being the world's ninth greatest economy, which gives an entirely productive and normal climate with present-day broadcast communications.sssHong Kong has a stable political environment and a non-interceding taxpayer-supported initiative. The business-accommodating expense strategy and the proper cycle have been enticing a lot of individuals to carry on with work in Hong Kong.

 types of companies in Hong Kong

 2:57 pm
 shivam said…
 strategic planning is the process of developing unique business plans, putting them into action, and analyzing the performance in terms of a company’s overall future goals. It is an idea that emphasizes a company’s vision and mission that is being met through combining different sectors such as financial accounting, sales, and human resource management.
 7:02 pm
 rohit said…
 imited Liability Companies

 A imited Liability Companies (LLC) is a half breed unincorporated business structure that joins the pass-through charge model of associations and sole ownerships with the security of individual resources given by the C enterprise. The proprietors of a LLC are known as individuals.

 imited Liability Companies


 8:51 pm
 veerediwedding said…
 Make your wedding day memorable by choosing to have your journey in a luxurious and beautifully designed car.
 if you need more information visit our website.
 luxury car rental in Chandigarh
 hire a wedding car for marriage in Chandigarh
 9:35 pm
 rohit said…


 Sales Deed

 A Sale deed is broadly utilized among realtors and property vendors. This authoritative archive is critical verification of the responsibility for property.
 The procurement or offer of a property isn't finished legitimately except if the purchaser and dealer sign a deal deed. Ordinarily, a deal deed is marked solely after the two players are fulfilled and consent to the agreements.


 Sales Deed

 10:44 pm
 Affordable Home in Gurgaon said…
 DLF Garden City Floors- Luxury 3/4BHK+S Flats in Gurgaon

 Presenting Independent Floors at DLF Garden City Floors, Gurgaon. DLF Garden City Floors is a confidential world in itself. The city is spread over a colossal range and is home to various families, residing as one and congruity. Other than having a wealth of nature's enjoyments including various sumptuous green gardens, the free city is home to a rich social and business establishment. DLF Garden City Floors Gurgaon offers 3/4BHK+S Luxury condos at important costing.SAll that YOU EXPECT FROM A DLF GARDEN CITY INDEPENDENT FLOORS GURGAON AMIDST OODLES OF GREENERY.


 DLF GARDEN CITY FLOORS

 DLF GARDEN CITY FLOORS
 3:37 pm
 Media Foster said…
 MediaFoster offers expert SEO service that makes sure your business gets the most out of the World Wide Web.
 BestITCompanyinMohaliforfresher
 SeotraininginstitutesinMohali
 SixmonthtrainingInstitutesinMohali
 6:29 pm
 rohit said…
 Equity Shares

 EQUITY shares are well known among financial backers as they give gigantic returns from now on. Value shares are given to public financial backers to acquire capital for the development of business and furthermore to produce tremendous measures of assets. Numerous associations source most of the capital from public financial backers. Value shares are intended for long haul speculations and not so much for momentary ventures.These offers are given by recorded organizations and unlisted organizations. Recorded organizations are those organizations that have their stocks recorded on stock trades while unlisted organizations don't have such stocks yet utilize private value. These offers are given at an ostensible worth of Rs 10 each on account of recorded organizations and unlisted organizations can give these offers at not entirely settled by them, however regularly it is finished at a lot higher worth than that of recorded organizations. The offer qualities differ now and again contingent on different elements.

 Equity Shares
 10:55 pm
 murtaza said…
 When you start a company, it is important that you have some proof of its formation. The certificate of incorporation will help you with that. This certificate will confirm your firm’s formation. This certificate of incorporation is also known as a corporate charter or Articles of incorporation. You need this document to continue doing your business as an organization.

 Too read more click here certificate of incorporation
 6:44 pm
 Anonymous said…

 visual seo studio crack
 10:23 pm
 Affordable Home in Gurgaon said…
 Krisumi Waterfall best Luxury project i sector 36A, Gurgaon.

 Krisumi Waterfall is an luxury project. Krisumi Waterfall is situated in area 36A in Gurgaon. It has worked by the Krisumi Corporation. Krisumi is a joint endeavor between India's Krishna bunch and Sumitomo Corporation. Krisumi cascade offers 2BHK and 3BHK Luxury Apartments with a loaded with lavish way of life and very much associated area. The best component is a significant street like Dwarka Expressway, NH 8 interfaces it. The spread region of the Krisumi cascade is 5.4 sections of land. Krisumi cascade project has 510 units.

 Krisumi Waterfall

 Krisumi Waterfall
 4:03 pm
 rohit said…


 operating profit

 At the point when a business' all's functional uses are taken out from its incomes, benefit is regularly characterized as the equilibrium. At the point when the all out books and expenses are adjusted and eliminated from incomes, benefit is left.Income Before Interests and Taxes (EBIT) is one more term for working benefit (EBIT). To put it another way, benefit is registered in the wake of deducting funding costs like interest and expenses paid to the public authority. Just functional consumptions, which are costs caused by a firm because of its typical business exercises, are deducted from net benefit to decide working benefit. Numerous merchandisers are shuffling stocks in response to impacts affecting item value, cost of products sold, volumes, and developing item blend.

 operating profit

 1:00 pm
 rohit said…

 what is operating profit

 An operating is all functional uses are taken out from its incomes, benefit is regularly characterized as the equilibrium. At the point when the all out books and expenses are adjusted and eliminated from incomes, benefit is left.Income Before Interests and Taxes (EBIT) is one more term for working benefit (EBIT). To put it another way, benefit is registered in the wake of deducting funding costs like interest and expenses paid to the public authority. Just functional consumptions, which are costs caused by a firm because of its typical business exercises, are deducted from net benefit to decide working benefit. Numerous merchandisers are shuffling stocks in response to impacts affecting item value, cost of products sold, volumes, and developing item blend.

 what is operating profit

 1:09 pm
 murtaza said…
 The commercial services supplied by the finance business are known as financial services in India. These financial services are supplied by corporations that handle money, such as community banks, banking, credit card issuers, insurance firms, accounting firms, consumer lending firms, stock broker-dealers,

 read more click here financial services in India.
 7:15 pm
 rohit said…

 public limited company

 A public limited company is a firm that is controlled by leaders and procured by partners. A PLC can give some measure of offers to the overall population. As PLC is even enlisted on the offer market and it hopes to be substantially more clear and public about its realities, highlights, and plan than a privately owned business.
 Be that as it may, a PLCs stock or firm offer is acquainted with the overall population and could be purchased or recognized by any individual, either specifically during the pattern of the IPO or through exchanging the financial exchange. PLC is even perceived as a freely held firm.

 public limited company


 9:41 pm
 Jobi Johnson said…
 This is the best post I have ever seen. Very clear and simple. Mid-portion Is quite interesting though. Keep doing this. I will visit your site again. Guardians of The Galaxy 3 Star Lord Jacket
 11:33 pm
 rohit said…




 Officers of a Corporation

 Top administration experts enrolled by the group's pioneer or leader board are alluded to as corporate officials of an enterprise. The CEO (CEO), finance chief, clerk, official, bad habit director, and secretary are models.Chiefs can be financial backers and leaders, despite the fact that they are not expected to be. They reserve the privilege to make a move against the organization, including the capacity to sign agreements. An association can have however many leaders as it needs, and an individual can stand firm on however many footholds as they need. In truth, in little organizations, exactly the same individual might possess the situations in general.

 Officers of a Corporation


 3:05 pm
 rohit said…
 corporations structure

 A corporation structure of investors, a directorate, and officials. At the point when you structure a company, you should sort out the proprietors and directors — give them obligations and freedoms — as per the standards spread out in your state's enterprise regulations.

 corporations structure

 8:52 pm
 shivam said…
 Singapore is considered one of the best destinations for business all over the world. This country is ranked constantly for the top destination in the ease of doing business index. This country has the easiest and free business regulations. The Singapore work visa has several foreign employees to work in Singapore and explore better opportunities.
 Read More: Why is strategic planning important

 4:19 am
 shivam said…
 Singapore is considered one of the best destinations for business all over the world. This country is ranked constantly for the top destination in the ease of doing business index. This country has the easiest and free business regulations. The Singapore work visa has several foreign employees to work in Singapore and explore better opportunities.
 Read More: Singapore Work Visa for Indians
 4:25 am
 Affordable Home in Gurgaon said…
 Best 3BHK luxury flats in sector 89A New Gurgaon

 ATS Marigold is The luxury Ready to Move project and is located at sector 89A New Gurgaon which is a prime location. its offers 3BHK luxury flats with world-class amenities.ATS marigold is connected to the Dwarka expressway. This project plan over 16 acres of land near Dwarka expressway.

 ATS Marigold

 ATS Marigold
 4:02 pm
 Affordable Home in Gurgaon said…
 Experion The Heartsong Luxury Apartments Sector 108 Starting @ 1.37Cr*

 Experion The Heartsong is prepared to move 3BHK and 4BHK extravagance condos in area 108 Gurgaon. Cost begins from 1.37Cr* to 1.87CrExperion The Heart tune is a prepared to-move lodging society in Sector 108 Gurgaon. The venture is wanted to foster more than 15 sections of land of land close to the Dwarka expressway.This project offers 15 pinnacles created with super current engineering and development innovation. Giving sumptuous 3BHK, and 4BHK lofts with various formats.


 Experion The Heartsong

 Experion The Heartsong
 6:54 pm
 rohit said…


 File your TDS Return

 TDS on compensation alludes to the duty that the business deducts from the worker's compensation when they pay it. The business deducts your cash and stores it for your benefit with the public authority.TDS was made to gather charge straightforwardly from pay sources. This idea expresses that an individual (deductor), who is responsible for making installment of indicated nature to someone else (deductee), will deduct charge from the source and transmit it into the Central Government's record.A credit would be conceded to the individual whose personal duty was deducted at source in light of Form 26AS/TDS endorsements gave by the deductor.

 File your TDS Return




 10:27 pm
 GLS said…
 Signature Global Park 2&3 Sector 36 Sohna Gurgaon offering 2 BHK and 3 BHK Luxury Apartments. This is the 14th assignment through Signature Global beneathneath the Haryana government’s Affordable Housing Scheme. For more details like floorplan, siteplan, pricelist, etc. https://www.glsconsultant.com/property/signature-global-park-2-and-3-sohna-gurgaon/call: 9582821821.
 Visit: https://www.glsconsultant.com/property/signature-global-park-2-and-3-sohna-gurgaon/
 5:34 pm
 rohit said…

 Electronic Transactions Act


 The Electronic Transactions Act was at first passed in July 1998 to lay out a regulative design for electronic installments and to offer consistency and lucidity to arrangements made carefully. It doesn't need the utilization of computerized exchanges or installments, yet it makes them simpler to use when members want to do as such.Singapore's administrative system keeps up with up with worldwide exchange regulation and innovation progressions to guarantee that the nation stays serious around the world. Singapore's administration upholds endeavors to participate in business carefully and keep electronically put away data.

 Electronic Transactions Act
 1:59 pm
 rohit said…

 What is OLTAS?

 Online Tax Accounting System is a computerized and branch-based technique for gathering, charging for, and recording Direct Tax assortments and consumptions from a wide range of payers.

 What is OLTAS?
 2:58 pm
 Affordable Home in Gurgaon said…
 Best commercial shops in sector 80, new gurgaon-Elan Mercado

 Elan Mercado offers luxury retail shops, studio apartments, duplex service apartments, and street retail shops in sector 80,new Gurgaon.it has best prime location advantage li it connected to th NH-8 dwarka expressway.easy to going airport in 30 minuts etc.

 Elan Mercado

 Elan Mercado
 9:19 pm
 rohit said…
 operational planning

 An organization needs a technique plan, yet that is sufficiently not. To guarantee that your association's bigger objectives are attainable, you want a functional arrangement to deal with the everyday undertakings.Functional plans don't need to be held for huge organizations. People and independent companies can likewise benefit with functional preparation.This article will make sense of, what is functional arranging is and how to make one without feeling overpowered.

 operational planning



 10:24 pm
 shivam said…
 A founder’s stock usually includes a vesting program. This is a positive characteristic. This protects, the equity of the company and helps prevent other parties from taking control. It is common for founders to leave the company in the early years of a startup.

 Vesting is the time period during which the founder’s stock becomes fully owned by the recipient. The vesting schedule gives the company’s equity to the recipient, but the recipient does not have any real ownership of the shares after the vesting period.

 Read More: singapore company founder stock
 6:10 pm
 Affordable Home in Gurgaon said…
 Best 2bhk/3bhk/4bhk luxury apartment in sector 85 Gurgaon

 Godrej Group lunched their new luxury project in sector 85, Gurgaon. its offered 2BHK, 3BHK, 4BHK, Luxury apartments with world class morden facility or amenities.Godrej air located in best prime location this location is most dimanding location in sector 85, Gurgaon.

 Godrej Air

 Godrej Air
 7:43 pm
 rohit said…

 How to start HR staffing company in Poland

 Perhaps of the least difficult country in Europe to open a selecting organization in Poland. On the off chance that you're a finance manager hoping to enlist laborers from outside the EU, Poland's fast and viable strategy will empower you to send off your enrolling firm rapidly in contrast with other European countries.You should manage the local peculiarities as well as business rules while enrolling new representatives in an outside country. Assuming you have never selected a representative in Poland, the country's work regulations might seem bulky and muddled. Be that as it may, there are a few equals between Polish work consistence guidelines and those of other EU countries. You should know about these changed work rules in the event that you plan to fill in Poland to go along.

 How to start HR staffing company in Poland

 9:59 pm
 abhisekhh1 said…
 The term “Partnership” has been defined under section 4 of the
 Indian partnership act, 1932.
 It was in the year 1932 when a separate law of Partnership was passed,
 before that all the matters about the Indian Partnership were dealt with by a chapter in the Indian Contract Act, 1872.
 4:39 pm
 Affordable Home in Gurgaon said…
 Trump Tower Ultra Luxury Residential Apartments Gurgaon

 Trump Tower is ultra-luxury 3BHK and 4BHK apartments by Tribeca Creators LLP. This project is located in the prime location sector 65 Gurgaon. The amenities provides by this project made you get lured toward the project and you will enjoy every moment of your life. This project has many location advantages it is in close proximity to IGI airport and Delhi. Many renowned schools, colleges and world-class hospitals are close to the project and this project is located in one of the posh locations at Golf Course Extension Road.

 Trump Tower

 Trump Tower
 10:03 pm
 rohit said…
 What is MSME

 SME stands for Micro, Small, and Medium Enterprise. The Micro, Small, and Medium Entrepreneurial Development Act, 2006, was enacted by the Indian government. MSME organizations specialized in the manufacture, fabrication, handling, or maintenance of goods and materials are established and overseen by the Ministry of MSME.MSME businesses are the engine of economic growth in a growing nation like India. Since these industries prosper, the economic benefits of the entire grow and develop. The MSME Act provides for registration in both of these classifications if the firm is in the transport and distribution businesses in India. Although the administration has not made this certification essential, it is advantageous to have one’s company established under it because it offers multiple gains in terms of revenue, commercial setup, financial institutions, and mortgages.

 What is MSME
 10:47 pm
 rohit said…

 Outbound Investment

 An outbound investment can be comprehended as any form of investment that is conducted by a person or business by venturing into the shares of a completely owned subsidiary company or a combined investment that is done outside of India.For instance, an outbound investment can be any kind of investment by a firm or a person in the shares of a firm. A traditional example of an outbound investment is Liberalized Remittance Scheme (LRS).

 Outbound Investment


 9:49 pm
 rohit said…

 Singapore PR for Indians

 As an outsider, you might be qualified to apply for extremely durable home in the event that you are a/an: Spouse of a Singapore resident or Singapore long-lasting occupant (PR) Unmarried kid matured under 21 years of age, brought into the world inside the setting of a lawful union with, or have been legitimately embraced by, a Singapore resident or PR.

 Singapore PR for Indians
 9:33 pm
 rohit said…

 asset management company

 An Asset Management Company (AMC) is even perceived as an asset save house, which gets cash from various streams and underwrites such sum by purchasing value/stock for the benefit of their private supporters. Such an organization knows when, how and where to contribute these resources.

 asset management company

 4:09 am
 T and T Realty said…
 T and T Realty is one of the most trusted Real Estate Consultants, Property dealers in Gurgaon offering the best Real Estate properties in Gurgaon.

 Property in Gurgaon
 SCO Plots
 commercial SCO Plots
 Luxury Residencies
 7:42 pm
 brandingheight said…
 A Branding Height agency is a company that offers services in the field of digital marketing. It provides a range of services, such as search engine optimization (SEO), pay-per-click advertising (PPC), social media marketing, and conversion rate optimization.
 Google Partner Company In Delhi
 9:20 pm
 rohit said…

 EPFO Claim Status

 The internet based EPFO guarantee status for your temporary asset (PF) withdrawal demand is one of the most amazing ways of monitoring its situation. The public authority entrances and online administrations suppliers have made it simple to guarantee PF sums.You can check the situation with your case by visiting either the EPFO site or the entrance for individuals. Additionally, you can essentially follow your withdrawal status assuming that you have your PF number.

 EPFO Claim Status

 2:56 pm
 abhisekhh1 said…
 Start an eCommerce Business in Singapore
 As the labor market enters an unending state of uncertainty because of constant travel
 restrictions and lockdowns job security is disappearing into the past.
 The workforce is constantly challenged to come up with new methods to get back
 control and the ability to be in control of their futures – during these turbulent times
 and eCommerce has been one of the top ways to do this.
 But, like all startup ventures, it will require perseverance and determination to achieve your business goals.
 Complete guide on how to register a company in singapore with complete process, documentation, and tax details .
 Register your company with our industry experts.
 For more details, visit our webpage
 3:05 pm
 shivam said…
 For applying for an employment pass, employers should require the following documents of the candidate-

 Candidate’s personal particulars page of his passport.
 In case the personal information in the passport is different from other documents then an explanation letter is required
 Latest business profile of company and instant registered information with ACRA

 Read More: employment pass singapore
 3:35 pm
 Affordable Home in Gurgaon said…
 Zara Roma sector 95B-Gurgaon Affordable flats 2bhk/3bhk

 Zara Group is sending off their new forthcoming reasonable task, Zara Roma area 95B, Gurgaon Affordable pads. Zara Roma offers 2BHK and 3BHK reasonable pads. It is situated in area 95 Gurgaon, associated by Dwarka freeway or Pataudi street.This undertaking is spread over 9.02 sections of land. In Zara Roma, the complete number of pads is 1252. The undertaking comprises of 12 skyscraper towers with S+13 story, it offers 2BHK/3BHK lofts, and it has platform vehicle leaving. The width of the primary street to enter it is 75 meters.

 Zara Roma Sector 95B Gurgaon

 Zara Roma Sector 95B Gurgaon


 4:15 pm
 shivam said…
 This e channel uae is a progressive system and has been known to make the process of information and data sharing simpler with every passing second. Almost every individual in need of a visa, or an immigration service utilizes this portal. There is a sense of uniformity in all the 6 Emirates. Amongst all the 7 Emirates, only Dubai does not make use of this online channel as it has a separate system to take hold of such operations.
 8:52 pm
 Timeless Aesthetics Academy said…
 Learn Permanent Makeup Courses & Facial Training online at Timeless Aesthetics Academy. Get trained at TA with career-building courses in Fashion and Beauty Industry.

 visit Here:- permanent Makeup In Gurgaon
 9:39 pm
 rohit said…




 What is Financial Reporting?

 In each industry, you could have seen a help or assembling area. In any case, it is possible to have different divisions that work consistently to achieve the Indian organization's targets.The activity of all divisions shares a hidden string that can be recognized as an Accounting and Finance Department. The bookkeeping and monetary parts of every division are recorded and introduced to different individuals.

 What is Financial Reporting?
 5:19 pm
 rohit said…

 steps to setup an offshore company

 Offshore Company determination - Choose your Offshore Company purview, sort of endlessly company name.
 Offshore company Setup - Submit expense, marketable strategy, and all private documentation and KYC structures.

 steps to setup an offshore company
 3:50 pm
 rohit said…

 Start an eCommerce Business in Singapore

 The labor market is in an ever-changing state of uncertainty due to constant travel restrictions and lockdowns, so job security is rapidly disappearing.Workforce members are constantly challenged to find new ways to regain control and have control over their futures. eCommerce is one of the best options in these turbulent times.It will take perseverance and determination, just like any startup venture, to reach your business goals.

 Start an eCommerce Business in Singapore
 10:11 pm
 abhisekhh1 said…
 General ledger is the main accounting ledger used by businesses to debit and credit accounts and is used to create businesses’
 financial statements To follow the for the most part acknowledged standards of bookkeeping (GAAP) and standard bookkeeping
 rehearses, organizations follow the twofold passage bookkeeping strategy where each exchange in a business is recorded as a
 charge and a credit. These records monitor the business' resources, liabilities, value, income, cost, gain, and once in a while
 different subtleties into individualized accounts. The overall record records all of the movement inside each record. At times
 exchanges might be gathered into more modest records, yet they will be recorded collectively into the overall record.
 The overall record is the hotspot for making the total data required for the fiscal reports and for any investigation into a deals.
 2:16 pm
 rohit said…




 what is DUNS number

 DUNS Number represents Data Universal Numbering System, and it comprises of 9 digits that structure the character of any enlisted business. It is produced by the credit organization, Dun and Bradstreet, which gives them list an enterprise access their information base. One can track down every one of the insights regarding the recorded partnerships in this data set. Instances of certain subtleties that you can find are:

 Organization name
 Telephone number
 Address
 Industry
 Number of representatives
 Credit and monetary wellbeing subtleties
 Branches and auxiliaries

 what is DUNS number



 10:24 pm
 shivam said…
 In India, the procedure for registering a company is often referred to as incorporation or company formation. When you submit an application for company registration, it ensures that your business separates from other businesses and has its own legal existence. Your company's registration process must be handled by the Corporate Affairs Ministry.

 Read More: Benefits of Indian Company Registration
 7:33 pm
 rohit said…
 Parent Company

 A Parent Company is a kind of corporate substance that has the responsibility for company. Assuming the Parent Company claims in excess of 50% of another company's democratic offers, it consequently possesses the business tasks of that company and can straightforwardly impact its working. The company that a Parent Company claims is called it's Subsidiary Company. A Parent Company has the option to get to the resources of its Subsidiary Company.

 Parent Company

 8:46 pm
 abhisekhh1 said…
 The concept of a Dormant Company has been introduced recently under Section 455 of Companies Act, 2013.
 In simple terms, Dormant Company implies to that Company which is inoperative or inactive. It is a perfect getaway of Company strike off or closure that results in permanent shut down of the business. A Dormant Company enables the Promoters who seek to start a company for the future project or hold an
 asset/ intellectual property rights without having any significant Accounting transaction.
 To yield the benefits of Dormant Company, a Company needs to file an Application to Registrar (ROC).
 5:01 pm
 rohit said…



 Registration Requirements

 In request to setting up a branch office in Singapore, unfamiliar firms need to connect with the administrations of a supported recording specialist, which is commonly a corporate specialist organization. The accompanying rundown gives the fundamental prerequisites to setting up a branch office in Singapore for registration purposes.
 Nearby delegates:- Branch offices are supposed to have at least 1 provincial representative who is existing in Singapore. The agent from Singapore should be at least 18 years of age. They can be either a Singapore resident or a long-lasting occupant of Singapore or Employment Pass holders.Address for registration in Singapore:- A branch office ought to incorporate an enrolled provincial location set in Singapore. It is essential to bring up that the area should not be a location that is a PO box.


 Registration Requirements

 10:35 pm
 shivam said…
 The Companies Act of Singapore's Section IXA requires the provision of this legal service. The word "nominee," which relates to the director's position in corporations, denotes a non-executive position that is not intended to satisfy Singaporean legal or regulatory requirements.

 Read More: Nominee Director in Singapore
 4:32 pm
 Dehradun Escorts said…
 Hii…I am Queen in Rishikesh.
 Rishikesh Women
 Rishikesh Girls
 Rishikesh Lady Service
 Girl Service in Rishikesh
 6:12 pm
 Aegte Lifescience said…
 we have found a kajal that is also a Gel Eyeliner and can revamp your eyebrow makeup too? Aegte 3D Kajal a 3-in-1 package that can be used as a Kohl, Eyeliner and Eyebrow filler due to multi-purposeful formula blended with organic ingredients to ensure zero harm in the sensitive eyes.
 9:39 pm
 rohit said…
 types of companies in cayman islands

 There are various motivations behind why investors choose to invest and lay out their organization in Cayman Islands.
 The reasons could include:
 Easiness of opening another business on Cayman Islands
 Tax assessment laws of Cayman Islands
 Vicinity to other created nations
 Accessibility of gifted work
 Business-accommodating government standards
 Simple incorporation process
 There are numerous different reasons too on why investors lean toward the Cayman Islands for their offshore business movement.

 types of companies in cayman islands
 10:10 pm
 Affordable Home in Gurgaon said…
 Adani Samsara Sector 60 Luxury Residential Apartments Gurgaon

 Adani Group sent off their new under-development private venture, Adani samsara Sector 60. This task is a ultra-extravagance project in sector 60 Gurgaon which is the ideal place in Gurgaon. It offers 3BHK and 4BHK extravagance flats with Modern offices and top notch conveniences like a Gymnasium and pool. Kids play zone, club, and so on.This venture has the best area advantage as it is associated with the Golf course Extension Road. You get every one of the social and urban conveniences around Adani. This venture offers a lavish way of life with the best elegant security and comfort.Adani Group sent off their new under-development private task, Adani samsara Sector 60. This venture is a ultra-extravagance project in sector 60 Gurgaon which is the ideal spot in Gurgaon. It offers 3BHK and 4BHK extravagance condos with Modern offices and elite conveniences like a Gymnasium and pool. Kids play zone, club, and so forth.

 Adani samsara sector 60

 adani samsara
 4:29 pm
 abhisekhh1 said…
 Founders’ stock is related to equity within a startup, but this is something that’s often overlooked because shareholders are constantly changing.
 It’s also commonly ignored in favour of discussions surrounding investor and employee equity. Despite this, it’s imperative
 that you understand what Founders stock is because it can have a huge impact on your business overall moving forwards.
 Understanding what it is, how it works, and the role it plays in your business will serve you well in the future with regards
 to minimising time and money wasting, and it can also help you attract new investors. So, with this in mind, here’s your essential guide to founders’ stockFounders stock
 4:51 pm
 abhisekhh1 said…
 If you and your co-founders have begun exploring a new business idea, before creating a company, consider establishing a proper
 strategy for allocation of your company’s equity. When company founders invest money or intellectual property in their business,
 they usually receive so-called Founders stock a type of stock that carries unique rights with respect to voting, control, and distribution of profits.
 Below we’ll discuss the benefits as well as potential pitfalls of holding founder’s stock in a new company incorporated in Singapore.
 4:51 pm
 rohit said…

 Dutch Foundation

 A foundation is an organization that doesn't aim to make cash. A foundation raises cash through donations, loans, and legacies. Its primary intention is to help a non-benefit or social cause. You can also possess a business yet all benefits should go to the foundation's cause.A foundation may have a board however no individuals or shareholders. A general gathering of individuals is thusly not necessary. You should make the statutes clear on the off chance that you expect to appoint an oversight board. The administrative board directs the board.

 Dutch Foundation
 9:42 pm
 hubrix said…
 Great Review site, Directory of best affiliate sites
 HubPrix Website Overview Review
 Want to look for
 Indian Gaming Deals
 2:29 am
 rohit said…

 company registration certificate

 Each substance that longings to work inside the lawful structure should initially get a company certificate registration. To get the registration certificate on the principal attempt, the documentation should be definite.To have a Company registration certificate a necessities to satisfy the standards of the Ministry of Corporate issues, I.e. MCA.In the event that you are another in the business area and wish to comprehend the part of registration certificates in India, then this article is for you.This post will help you in having a deep understanding of business registration certificates from the base to up.

 company registration certificate
 9:42 pm
 Affordable Home in Gurgaon said…
 BEST M3M COMMERCIAL PROJECTS IN GURGAON

 Commercial projects in Gurgaon: M3M has the best commercial projects in Gurgaon. M3M Group is entirely decent in the housing market. Last year M3M Developed a 10 million sq. ft. region and this is the biggest region in India developed by the M3M Group. In the housing market, M3M Group remains on first situation in north India, and the entire of India remains on second position.M3M Group constructing numerous commercial projects like M3M 65TH AVENUE, M3M CORNER WALK, M3M PRIVE 73, M3M ATRIUM 57, M3M IFC, M3M BROADWAY, and M3M CAPITAL 113 High Street Retail. These all projects are situated in the most demanding and created city Gurgaon.

 Commercial projects in Gurgaon

 Commercial projects in Gurgaon
 9:02 pm
 rohit said…
 steps to setup an offshore company

 An offshore company is many times an equivalent word for the company that is enlisted in duty safe houses. In any case, an offshore company is a more broad term and covers any sort of company that has its enrolled office set up external its nation of origin.The importance of offshore companies is reliable with today's market patterns. Offshore companies permit business people to put their resources in unfamiliar business sectors where they can possibly create more significant yields. This has prompted a rising interest in offshore companies by business people, who presently decide to enroll their companies in charge amicable wards.

 steps to setup an offshore company
 10:06 pm
 shivam said…
 In an appropriately working capital market, the Capital Asset Pricing Model shows how dangerous ventures are assessed. It aids the forecast of a security's or alternately stock's projected exhibition. The CAPM-determined and expected pace of return can be utilized to check whether the speculation yields pretty much than the normal benefit. A financial backer ought to pick assets that create a good yield than the one projected by the capital asset pricing model while choosing to contribute.
 10:14 pm
 abhisekhh1 said…
 A Nominee director is an individual who goes about as an overseer of the organization for your sake.
 Then again, a nominee shareholder is somebody that "loans his name" to you to go about as the enlisted proprietor of offers in an organization. In truth in any case, he just holds the offers for your advantage. On the off chance that you delegate a candidate investor, he would appear to the world to be the proprietor of the offers, and you get to stay quiet about the game plan. Furthermore, in the event that the arrangement
 is made in the right manner, you hold the privileges as a whole and advantages in the offers, for example, the option to sell the offers, get profits, and vote at regular gatherings.

 4:49 am
 rohit said…

 Meaning of Articles of Association

 Articles of Association as initially outlined or as modified now and again in compatibility of this Act or some other past organization's regulation.An organization's articles of association are an agreement between the organization and investors. Chiefs are not gatherings to this agreement, but rather they have their own chief's obligations, which are authoritative in nature.

 Meaning of Articles of Association
 6:41 pm
 rohit said…

 What is general ledger

 To depict the importance of a general ledger in a sentence, it is the base and essential record of your entire business framework. It is delivered out of the bookkeeping sections you've made. These bookkeeping record sections are finished for each deal your organization pulls off and are then coordinated all neat and tidy. Through a general ledger, you can keep a mind deals by entering them in like manner. The passages are to be taken from the bookkeeping diaries, referenced in the credits and charges segment, and afterward are placed into individual records.
 Your Chart of Accounts should have somewhere around 5 records, and each passage is referenced in one of the records. These graphs of records can the follow:

 Income
 Liabilities
 Value
 Resources
 Costs

 What is general ledger

 8:28 pm
 abhisekhh1 said…
 In numerous ways, a Public Limited Company is like a private limited company. You'll in any case be expected to enlist with Companies House and your own risk is restricted. The fundamental trademark and benefit of a public restricted company is that you can raise capital through outer financial backers, basically, offering partakes in your company to people in general. To set up as need might arise to have something like two investors and somewhere around £50,000 worth of offers should be given, in spite of the fact that there's no commitment for you to offer any further offers to people in general. On the off chance that you're not in the expected monetary position right now a confidential restricted company can be re-enlisted as a PLC sometime later - as well as the other way around - by applying and passing a unique goal with Companies House.
 9:14 pm
 shivam said…
 A Sale Deed deed is the most well-known type of land exchange in the country. Sales deeds are utilized to move the title of a property starting with one party then onto the next. A sales deed should be endorsed by the two players engaged with the exchange, and it is made substantial when it is enlisted with the Registrar.
 5:29 pm
 sexy hemma said…
 Jammu Call-Girls Service
 3:06 am
 abhisekhh1 said…
 Dutch business regulation is one of the most mind boggling in Europe, as it changes like clockwork. For non-Dutch or unfamiliar organizations, it very well may be incredibly difficult to track and carry out these changes.
 In this aide, we have incorporated an outline of the Dutch duty framework, including relevant expense rates for occupants and non inhabitants, as well as exceptional ostracize charge system and movement recompenses. The guidelines around rates and recompenses change routinely. On the off chance that a business is viewed as in break of these guidelines, it can bring about enormous fines or retroactive allowances, so it is critical to check with the public authority or a global finance trained professional. Here’s more about hr and pay rolling in Netherlands
 5:31 pm
 abhisekhh1 said…
 Hr and pay rolling in netherlands
 Enrolling, recruiting, onboarding, preparing, and firing representatives are all essential for HR's liabilities. HR likewise manages the most awkward pieces of work, for example, HR breaks, cutbacks, and terminating. HR, then again, exist to give help to workers. For sure, it is a human asset. While enrolling for new jobs, HR must know about the association's necessities and ensure they are fulfilled. A promotion posted on a task board isn't sufficient; they'll have to do statistical surveying, contact partners and oversee spending plans. When the position is declared, further examination is expected to guarantee that the right individual is hired.HR is answerable for planning interviews, sorting out recruiting drives, and onboarding recently added team members, among different obligations. It is their obligation to guarantee that all selecting documentation is finished and that everything from the main day to the last day works out in a good way.
 5:32 pm
 rohit said…


 What Is Digital Signature?

 A signature is known to imply an understanding. Assuming you sign something, it implies you are giving your agree to it. While discussing the utilization of a signature in a bank while marking checkbooks, it again shows our assent. Be that as it may, these signatures can likewise transform into destruction when copied. This can be a little frightening as such copy signatures have the capacity of denying you of your well deserved cash. Yet, one way you can forestall this trick of copy signatures is by utilizing Digital Signature.
 Utilizing the procedure of digital signature, you can confirm every one of the reports and check in the event that it is veritable and genuine or not. The system of a digital signature is with the end goal that it can undoubtedly decide whether there is any intruding done to it. This way you get the well-suited subtleties on the personality, beginning, and status of your internet based report.


 What Is Digital Signature?
 11:05 pm
 abhisekhh1 said…
 To begin your eCommerce business in Singapore , the initial step is that internet business organizations in Singapore should be enlisted with the ACRA. This incorporates enlisting as a business element (for example an organization or a sole ownership) and enlisting for GST on the off chance that your business' yearly income surpasses $1 million.
 Additionally, Singapore-based internet business organizations, similar to each legitimate business, are expected to every year conform to a few guidelines and regulations. Organizations in Singapore should conform to different yearly consistence prerequisites. For instance, internet business organizations are expected to record a yearly return and examined fiscal summaries with ACRA. Resistance with such pertinent prerequisites (yearly consistence and regulatory undertakings change contingent upon made to order premise) will prompt a monetary punishment, or a disintegration of your organization in the Lion City.
 11:08 pm
 abhisekhh1 said…
 The scene of eCommerce business in Singapore is continually changing and the regulations and guidelines are much of the time complicated and hard to explore. Organizations should be current with the most recent guidelines and changes to stay away from any lawful complexities and give the wellbeing and security of web based looking for customers. Know more about legal issues faced by eCommerce business in Singapore .
 11:09 pm
 abhisekhh1 said…
 Singapore is based on its capacity to saddle globalization and is eminent for uprightness, quality, dependability, efficiency and implementation of protected innovation freedoms. Yet, carrying on with work isn't without its difficulties, and having nearby assistance on board is vital. With the high level and expanded utilization of online media, online business is turning into a quick arising pattern. Each five out of eight organizations are working internet, conveying web based business. However, being practical online doesn't mean you can get away from lawful issues. There are different legitimate Legal Issues Faced by eCommerce Business in Singapore too. Furthermore, in the event that these issues are not dealt with in time, they can prompt difficult issues for your business.
 11:11 pm
 shivam said…
 In Singapore, nobody rule administers every single cooperative arrangement. The rules are for the most part founded on the English contractual general set of laws. A lot of Singapore's business contracts are as yet in light of ancestors, or rules laid out by judges. Explicit regulation, then again, influence different areas of Contract Law.
 7:11 pm
 rohit said…

 Types of taxes in Poland

 In Poland, two kinds of administrations are accountable for the duty framework:
 One of the main states under which taxes like extract obligation, VAT, individual income charge, corporate income charge, and common exchange charge includes.
 What's more, the other is the neighborhood administration under which taxes like vehicle expense and land charge includes.
 In absolute there are twelve kinds of taxes in Poland, they are as per the following:

 Direct Tax:
 Inheritance and gifts charge
 Rural assessment
 Ranger service charge
 Charge on canines

 Types of taxes in Poland
 12:48 am
 rohit said…

 Common Stocks

 The protections that embody an individual's possession in a firm and their hang on the company's gathered incomes are known as common stocks. This stock element allows an opportunity to individuals to pick the company's executive board and later gives them casting a ballot rights to comprise business strategies.For the most part, over the long haul, common stocks are known to make high rate returns. The holders of common stocks are remunerated through profit pay which is given to them subsequent to conveying the accumulated increase to the investors of inclination

 Common Stocks

 9:05 pm
 rohit said…


 Business Licenses And Permits

 In the event that you're beginning another business, you should know about the few sorts of business permitting you'll require. This is to make sure that your organization is legitimately enlisted and is a working in a particular area. Various organizations have various rules. They are likewise impacted by the kind of corporate association and the significant market.

 Business Licenses And Permits
 9:49 pm
 rohit said…

 Officers Of A Corporation

 Top management professionals enrolled by the team's pioneer or leader board are alluded to as corporate officers of a corporation. The CEO (CEO), finance chief, cashier, presidential, bad habit chairman, and secretary are all examples.Leaders can be financial backers and chiefs, although they are not expected to be. They have the option to take action against the company, including the ability to sign contracts. An organization can have as many leaders as it wants, and an individual can stand firm on as many footholds as they want. In truth, in small organizations, exactly the same individual may possess all of the positions.

 Officers Of A Corporation
 2:32 pm
 shivam said…
 Singapore Legal System is known for its fair-mindedness, viability, and trustworthiness, making it perhaps of the best spot on the planet to lay out and work an organization. In its yearly Conducting Business study, the World Bank bunch recognized this, naming Singapore's administrative system as the ideal climate for business.
 7:22 pm
 shivam said…
 Required Documents for PF Registration
 Any organization that needs to apply for PF should present the accompanying reports:

 Association PAN card
 Authentication of joining
 Cross dropped check of association
 Address confirmation for the sake of the association. It very well may be: a rent understanding
 Water
 Power
 Phone bill

 Read More: Required Documents for PF Registration
 6:59 pm
 shivam said…
 It is urgent to decide a name that is remarkable and reasonable for your company. This is on the grounds that it provides your clients with the initial feeling of your business and assists you with standing apart from your rivals. It could create all the deviation in how your company develops.

 Read More: Singapore Company Name Approval
 7:13 pm
 murtaza said…
 Turkish Free Trade Zone

 A Turkish investor can incorporate an organization inside Turkey’s Turkish free trade zone. This free zone provides numerous advantages to the incorporation of a business. An entity that is registered within a free zone will benefit from tax incentives and other rewards from the state. Investors can also return funds back to their home country via an arrangement called the Turkish Free Trade Zone.

 company registration in Turkey
 9:37 pm
 shivam said…
 According to the report of the World Bank's 2020 on business-accommodating practices, India is standing at the Sixty-three situation out of 190 nations. India is improving its standing by 79 situations in five-time frames (2014-2019).

 Be that as it may, the essential purposes for this improvement in the ranking were the execution of India's Insolvency and Bankruptcy Code and Goods and Service Tax. Universally, and notwithstanding China, India is emerging as a promising destination to direct business.

 Read More: Top 10 Cities for doing Business in India
 7:00 pm
 murtaza said…
 Turkey is a country where you first need to choose the type of company that you want.

 Turkey permits you to establish a company without having more than one shareholder (both LLCs and C-Corps).

 It is much easier to set up LLC than C-corp, because it is not necessary to transfer money to the bank.

 Turkey Compliance for Company Registration
 9:47 pm
 shivam said…
 It is a common misconception that offshore companies do not pay taxes or operate tax-free. That is not true; all companies must pay taxes in some form, but the benefits include minimizing the tax liability by reducing the corporate tax rate and having no taxation on dividends earned.

 Read More: 5 Best Countries In 2022 For Offshore Company Formation
 7:13 pm
 Nino Nurmadi , S.Kom said…
 Nino Nurmadi, S.Kom
 Nino Nurmadi, S.Kom
 Nino Nurmadi, S.Kom
 Nino Nurmadi, S.Kom
 Nino Nurmadi, S.Kom
 Nino Nurmadi, S.Kom
 Nino Nurmadi, S.Kom
 Nino Nurmadi, S.Kom
 Nino Nurmadi, S.Kom
 Nino Nurmadi, S.Kom
 10:51 pm
 murtaza said…
 A Nominee Director & a formal director (who can both be part of the board or play a role as a company director) share the same obligations and responsibilities as the former under the Companies Act and Common Law.
 7:55 pm
 shivam said…
 Normally, a seaward organization implies laying out a part of that organization in another country. There are a few different explanations behind laying out a seaward organization as a venture and banking organization. They need to chip away at various ideas while having similar objectives.

 A seaward organization, right off the bat, is integrated to extend in view of the business activities all through the worldwide reach. This is finished for acquiring tax reductions from different nations. The choice connected with choosing a nation relies on the duty strategies followed there, work cost, cost, the technique of fuse, and so forth. They additionally finish their work by re-appropriating it to the work of different countries. They conclude the country in view of the expense of work.

 Furthermore, seaward venture accounts are additionally settled for creating high net benefits. They are set up seaward for partaking in the advantages of the great expense strategies, resources security, protection, and numerous others talked about underneath. For the most part, a holding organization or LLC are the most ideal as seaward speculation organizations.

 Read More: Types of Offshore Companies
 8:01 pm
 murtaza said…
 First, the notice needs to be published for calling the Board Meeting.
 The second is the notice to call a general meeting should be distributed by the business to each of the directors, auditors, and members. The notice must be approved by the Board.
 Extraordinary general meeting is scheduled for the due date as stated in the notice to adopt a special resolution in Section

 Objectives of Memorandum Of Association
 8:49 pm
 shivam said…
 India is located in Southern Asia and is bordered on the east by the Bay of Bengal, the west by the Arabian Sea, and the south by the Indian Ocean. Even though it lags behind other developing countries, India continues to provide considerable opportunities for foreign direct investment.

 Read More: Benefits to Register a Company in India
 7:26 pm
 murtaza said…
 There are a few points to consider when establishing the Delaware LLC for real estate investing. In the beginning, you’ll need to select a registered agent from Delaware who is accountable for obtaining the legal and tax documentation for the LLC.

 Advantages of Using a Delaware LLC
 10:29 pm
 rohit said…


 Starting a Trading Business in Singapore

 Want to learn more about trading yet don't have any idea how to begin? Or probably you already trade in Singapore yet want to work on your abilities?
 Trading businesses are the most common way of purchasing and selling items to make a benefit. In Singapore, it is feasible to bring items from overseas markets into Singapore or commodity items out of Singapore to the global market, or both.
 As in this article, will assist you in becoming a more profitable trader. As we have pointed out a couple of recommendations for starting a trading business in Singapore. We should find out what are they.

 Starting a Trading Business in Singapore
 11:20 pm
 murtaza said…
 Irrespective of contrary provisions in the articles of association or shareholders’ resolutions, the directors’ right to represent the company and bind it cannot be excluded with effect against third parties. However, this does not mean that any director may always bind the company.

 Directors of a Poland LLC 2022
 4:11 am
 rohit said…




 Start a Business in Europe

 Given the present status of the economy in Europe which includes slow development and political instability of each and every kind, BREXIT fallout, and so forth. This isn't the second to begin your business.
 Notwithstanding, the majority of Europe is known for its sluggish development in great times, although there are still chances to establish your business in Europe If you're aware of the realities and obstacles.
 One of the main things to keep in your mind is the fact that each European state has rules and laws for outsiders who are not part of the EU and are looking to establish the foundation of a business.
 The joblessness rate is still high in many European nations. This means you want to turn out self-sustaining revenue or the creation of occupations for others to defeat obstacles to gain approval to begin your own company across Europe.
 In this way, with next to no further ado we should get bounce into the article to find out about various things prior to planning to start a business in Europe.


 Start a Business in Europe
 11:56 am
 rohit said…


 Delaware LLC Merger

 A Delaware LLC merger is a technique of joining numerous LLCs to shape one element. It tends to be utilized in light of multiple factors, including to improve on activities and unite resources or lower costs. Assuming you're contemplating joining a current Delaware LLC, there are a few things you want to be aware.

 In any case, in this blog, we'll examine the rudiments of Delaware LLC Merger Your Business Should Know, and the most ideal way you can approach consolidating two restricted risk organizations.

 Delaware LLC Merger

 12:33 pm
 Commercial Projects said…
 Nice BLOG. Ashiana Amarah 93 Gurgaon
 by Ashiana Group real estate developers, where you can buy an apartment under a luxury residential project. The project has a total constructed area of 22.1 acres of land with 3BHK and 4BHK Flats spread over1200 units under S+13 and S+14 floors into 12 high-rise towers. These flats start from 1000 sq. ft. and 1408 sq. ft. If you are searching for a luxury residential project in sector 93. So Ashiana Amarah sector 93 Gurgaon is the best option for your investment. Here you can get your dream home in a peaceful environment.
 11:05 pm
 rohit said…
 Public Limited Company (PLC)

 A public limited company is a firm that is managed by chiefs and procured by partners. A PLC can give some measure of offers to the overall population. As PLC is even enrolled on the offer market and it hopes to be considerably more clear and public about its realities, highlights, and plan than a privately owned business.
 In any case, a PLCs stock or firm offer is acquainted with the overall population and could be purchased or recognized by any individual, either expressly during the pattern of the IPO or through exchanging the securities exchange. PLC is even perceived as a publicly held firm.

 Public Limited Company (PLC)
 12:11 am
 Properties in Gurgaon said…
 Nice blog. thanks for giving such a grateful information . if you wan to invest in luxurious residential project. then considered Elan Sector 106 Gurgaon. this project is located in Sector 106 . it cover the land area of 30 acres . they are offering 3 and 4 BHK Apartments.

 For More Details
 call: 9667-884-258
 3:21 pm
 murtaza said…
 A person’s account with the insurance with the Social Insurance Company includes a sub-account in which information is recorded about the amount that has been valued of premiums that have been paid for Pillar II which is the portion of the premium that is not being transferred at present to pension funds.

 Poland National Social Security(ZUS)
 8:33 pm
 rohit said…
 Operational Planning

 An organization needs a procedure plan, yet all the same that is sufficiently not. To guarantee that your association's bigger objectives are reachable, you really want an operational arrangement to deal with the everyday assignments.

 Operational plans don't need to be saved for huge organizations. People and independent companies can likewise benefit with operational planning.

 This article will make sense of, what is operational planning is and how to make one without feeling overpowered.


 Operational Planning
 12:18 pm
 re.rockspace.local login said…
 Rockspace wireless range extender allows a high-speed connection, In order to complete the configuration need to type the default IP Address or re.rockspace.local login in the URL box and search for it, You will redirect to the admin login portal. After login can make changes and set up easily.
 7:26 pm
 shivam said…
 A portion in the controlling of the company is what means equity. It is the quantity of income an owner is entitled to, if all of the liabilities and obligations are paid off and all of its securities are expropriated. One can prosper from a company’s stock investment through financial assets or share value development. Moreover, purchasing a corporation’s stock grants an investor the opportunity to vote on topics affecting the Executive board.

 Read More: Determinants of Equity
 7:30 pm
 rohit said…
 Strategic Planning

 Strategic planning is the most common way of creating extraordinary strategies, setting them in motion, and dissecting the presentation with regards to an organization's general future objectives. A thought underscores an organization's vision and mission that is being met through joining various areas like monetary bookkeeping, deals, and human asset the board.

 A strategic arrangement is the consequence of strategic reasoning. It as often as possible shows up in a planning paper. Representatives, customers, business partners, and investors will actually want to promptly talk about, comprehend, and execute these methodologies. Strategic planning is finished consistently by organizations to analyze the effect of advancing business sector, business, monetary, and administrative variables. By then, a strategic arrangement might be changed and revised to consolidate any future techniques.


 Strategic Planning


 10:20 pm
 rohit said…



 ABSD Singapore

 It is a legislative expense forced on the obtaining of two progressive private grounds. HDB condos, homegrown retail structures, chateaus, and rented resources are among these property. The buyer's home grant affects how extra purchaser's stamp obligation is determined.
 ABSD was taken on by the public authority to make lodging values available for Singapore occupants. They had the option to achieve this by controlling the quantity of private structures. It likewise endeavors to hinder workers and different associations from purchasing various homes. The ABSD might be repaid by the CPF. The ABSD would need to be paid straightforwardly. Maybe you'll have the option to get the cash from your CPF. In any case, you can buy with cash from your Conventional Consideration.

 ABSD Singapore
 12:45 pm
 shivam said…
 A Company limited by shares might have its capitalization restricted depending on the percentage of investors who loaned money on their interests. This restricts the financial position of a business and just the capital back if it goes bankrupt or suffers a significant financial failure.
 4:45 pm
 murtaza said…
 From 1979, the whole community of Polish people is required to be a part of the authorized registry. These days, every child receives his/her ID number at the time of birth. You should always remember that it is more than just a number.

 Poland PESEL Number
 4:20 pm
 shivam said…
 To describe the meaning of a general ledger in a sentence, it is the base and foundational record of your whole business system. It is produced out of the accounting entries you’ve made. These accounting record entries are done for every business transaction your company pulls off and are then organized in proper order.
 5:11 pm
 1 – 200 of 305 Newer Newest
 Post a Comment

 Popular posts from this blog

 Authenticating via Kerberos with Keycloak and Windows 2008 Active Directory

 July 15, 2015
 The following instructions show you how to configure Keycloak with Windows AD in order to use Kerberos authentication. Assumptions The Kerberos realm is VIRTUAL.LOCAL The hostname used to access Keycloak is virtual.local. This just means we are running Keycloak on the domain controller. In production virtual.local will be replaced with something like keycloak.dev.virtual.local or something like that, giving you a SPN of HTTP/keycloak.dev.virtual.local@VIRTUAL.LOCAL Configuration Create a windows domain account called Keycloak. Run the following command to assign a SPN to the user and generate a keytab file: ktpass -out keycloak.keytab -princ HTTP/virtual.local@VIRTUAL.LOCAL -mapUser Keycloak@VIRTUAL.LOCAL -pass password1! -kvno 0 -ptype KRB5_NT_PRINCIPAL -crypto RC4-HMAC-NT Verify the SPN has been assigned to the user with the command: setspn -l Keycloak Configure the LDAP settings in Keycloak like this. Since we are running Keycloak on the domain controller, we ref
 Read more

 Fixing OpenVPN "Authenticate/Decrypt packet error: cipher final failed"

 March 08, 2015
 When connecting to a VPN I was constant getting the error Mar 8 09:29:27 openvpn[1696]: Authenticate/Decrypt packet error: cipher final failed I had imported the supplied ovpn file and had followed all the other configuration steps, so this was quite frustrating. Then I saw this in the logs: Mar 8 09:31:07 openvpn[1790]: WARNING: 'cipher' is used inconsistently, local='cipher BF-CBC', remote='cipher AES-256-CBC' Changing my client to use "cipher AES-256-CBC" instead of the default (which apparently was cipher BF-CBC) fixed the issue.
 Read more
 Powered by Blogger
 Theme images by Radius Images
 Unknown Visit profile

 Archive

 * 2017 2
 + April 2
 * 2015 4
 + August 1
 + July 1
 + April 1
 + March 1
 * 2014 6
 + December 1
 + July 1
 + June 1
 + January 3
 * 2013 10
 + November 4
 o Three.js Tutorials
 o Three.js - 2 - Getting Started Part 2
 o MinHash for dummies
 o Three.js 1 - Getting Started
 + September 1
 + July 2
 + June 1
 + March 1
 + January 1
 * 2012 22
 + December 1
 + October 2
 + August 2
 + July 1
 + June 1
 + May 3
 + March 3
 + February 3
 + January 6
 * 2011 2
 + December 2
 Show more Show less

 Labels

 * three.js

 Report Abuse

Duplicate document detection is becoming increasingly important for businesses that have huge collections of email, web pages and documents with multiple copies that may or may not be kept up to date. 
MinHash is a fairly simple algorithm that from all my Googling has been explained very poorly in blogs or in the kind of mathematical terms that I forgot long ago. So in this article I will attempt to explain how MinHash works at a practical code level. 
Before I start, please take a look at http://infolab.stanford.edu/~ullman/mmds/ch3.pdf. That document goes into a lot of theory, and was ultimately where my understanding on MinHash came from. Unfortunately it approaches the algorithm from a theoretical standpoint, but if I gloss over some aspect of the MinHash algorithm here, you will almost certainly find a fuller explanation in the PDF. 
I'll also be using pseudo Java in these examples instead of traditional math. This means when I use terms like Set, I am referring to the group of classes that implement a Set in Java. Of course a set in Java shares a lot of properties with a set in maths, but keep in mind that this is written from a developers point of view. 
What does it mean when we talk about document similarity?  
The whole point of MinHash is to efficiently answer the question "How similar is this document to that document".
Before we can answer that question, we need to look at a more simple example of two sets of strings and determine how similar they are.
Here are our two sets:
 
Set a = new Set(["chair", "desk", "rug", "keyboard", "mouse"]);
 
Set b = new Set(["chair", "rug", "keyboard"]);
A measure of how similar these two sets are is known as the Jaccard Coefficient. It is calculated as number of common elements / (total number of elements - number of common elements).
In our case we have 3 common elements: "chair", "rug" and "keyboard". We have a total of 8 elements. So the Jaccard Coefficient  = 3 / (8 - 3) = 0.6, or 60%. http://www.planetcalc.com/1664/ is an online calculator that you can play around with to determine the similarity of two sets.
Documents as sets
While a document can be though of as a giant set of words, we don't just break down a document into individual words, place them in a set and calculate the similarity, because that looses the importance of the order of the words. The sets
 
Set a = new Set(["I", "went", "to", "work", "today"]);
 
Set b = new Set(["today", "I", "went", "to", "work"]);
would be considered 100% similar, even though they clearly are not.
Instead we break a document down into what are known as shingles. Each shingle contains a set number of words, and a document is broken down into total words - single length + 1 number of shingles. So if a document contained a single sentence of "The quick brown fox jumps over the lazy dog", that would be broken down into the following 5 word long shingles :
The quick brown fox jumps
quick brown fox jumps over
brown fox jumps over the
fox jumps over the lazy
jumps over the lazy dog
So our document as a set looks like:
 
Set a = new Set(["The quick brown fox jumps", "quick brown fox jumps over", "brown fox jumps over the", "fox jumps over the lazy", "jumps over the lazy dog"]);
These sets of shingles can then be compared for similarity using the Jaccard Coefficient.
Optimizing the process
So we now have a way to compare two documents for similarity, but it is not an efficient process. To find similar documents to document A in a directory of 10000 documents, we need compare each pair individually. This is obviously not going to scale well.
What we can do to reduce some cycles is compare sets of randomly selected shingles from two documents. So for a document that is 10000 words long, we break it down into 9996 shingles, and randomly select say 200 of those to represent the document. If the second document is 20000 words long, we boil that down from 19996 shingles to another set of 200 randomly selected shingles.
Now instead of matching 9996 shingles to 19996 other shingles, we are are comparing 200 shingles to another 200 shingles. We have reduced our workload at the expense of accuracy, but this is still good enough for most scenarios.
NOTE
So just how much accuracy did we sacrifice by comparing only a small subset of randomly selected shingles? I actually don't know, but I assume it sits on a bell curve where the number of random selections improves the accuracy to a point where more random selections won't provide any meaningful increase in accuracy. If you know the math behind this, please leave a comment.
Computing and saving the random shingle selections
So this is where MinHash comes in.
We could save the 200 randomly selected shingles, but storing variable length strings kinda sucks. It complicates database design and comparing strings is slow.
The clever part about MinHash is that it allows us to save integers instead of strings, and also takes the hassle out of randomly selecting shingles. It works like this.
1. Break down the document a set of shingles.
2. Calculate the hash value for every shingle.
3. Store the minimum hash value found in step 2.
4. Repeat steps 2 and 3 with different hash algorithms 199 more times to get a total of 200 min hash values.
At this point instead of 200 randomly selected shingles, we have 200 integer hash values. This is effectively a random selection of shingles, because a good hash algorithm is supposed to generate a number that is as likely to be large as it is likely to be small. This kind of distribution of hash codes is what hashing is all about, so selecting the smallest hash is, for all intents and purposes, a random selection of a shingle.
Um, 199 more hash algorithms? WTF!
So you see the String.hashCode() method, but where do these other 199 hash codes come from? This is the step that most explanations on the MinHash algorithm conveniently leave out.
The short answer is that you XOR the value returned by String.hashCode() with 199 random numbers to generate the 199 other hash code values. Just make sure that you are using the same 199 random numbers across all the documents.
Great, but I still have to compare every document to every other document. Can this be optimized?
This is where the second neat trick of MinHash comes in. 
Locality sensitive hashing (LSH) involves generating a hash code such that similar items will tend to get similar hash codes. This is the opposite of what .hashCode() does.
LSH allows you to precompute a hash code that is then quickly and easily compared to another precomputed LSH hash code to determine if two objects should be compared in more detail or quickly discarded.
We don't actually calculate a LSH hash code as such, but the idea of a boiling down a complex object (like our collection of minhash codes) into something that is quickly and easily compared with other complex objects is still applicable.
What we do is take the collection of minhash values, and categorize them into bands and row. For the sake of simplicity we'll assume each document has 20 minhash values. We will break them down into 5 bands with 4 rows each. Also for the sake of simplicity we'll assume that .hashCode() (and any number XORed with it) results in a number between 0 and 9.
So conceptually the minhash values from 5 documents in the first of the 5 bands and its rows looks like this.
Band One  
 
MinHash Algorithm One
MinHash Algorithm Two
MinHash Algorithm Three
MinHash Algorithm Four
Document One
1
3
6
0
Document Two
2
3
1
0
Document Three
1
3
6
0
Document Four
2
1
3
1
 
 
What we are looking for are rows within a band that are the same between documents. Document One and Document Three in this case both have rows with values 1, 3, 6, 0. This tells us that these two documents should be compared for their similarity.
Although it is not shown here, you should look through Bands Two - Five looking for documents that share rows. Any documents that share rows in any bands should be compared for their similarity. 
This is useful when you have a document, and you want to know which other documents to compare to it for similarity. I'll assume that the minhash values are stored in SQL, so to get out candidates for comparison you would write:
SELECT DocName 
FROM Documents
WHERE (
BandOneMinHashAlgorithmOne = 1 AND
BandOneMinHashAlgorithmTwo = 3 AND
BandOneMinHashAlgorithmThree = 6 AND
BandOneMinHashAlgorithmFour = 0
 
) OR
( 
BandTwoMinHashAlgorithmOne = # AND
BandTwoMinHashAlgorithmTwo = # AND
BandTwoMinHashAlgorithmThree = # AND
BandTwoMinHashAlgorithmFour = #
 
) OR ( 
BandThreeMinHashAlgorithmOne = # AND
BandThreeMinHashAlgorithmTwo = # AND
BandThreeMinHashAlgorithmThree = # AND
BandThreeMinHashAlgorithmFour = #
 
) OR ( 
BandFourMinHashAlgorithmOne = # AND
BandFourMinHashAlgorithmTwo = # AND
BandFourMinHashAlgorithmThree = # AND
BandFourMinHashAlgorithmFour = #
 
) OR ( 
BandFiveMinHashAlgorithmOne = # AND
BandFiveMinHashAlgorithmTwo = # AND
BandFiveMinHashAlgorithmThree = # AND
BandFiveMinHashAlgorithmFour = #
 
) 
This explanation completely glosses over why this works and what combination of bands and rows you should construct when looking for similar documents. If you want to get into that detail, take a look at http://infolab.stanford.edu/~ullman/mmds/ch3.pdf.
MinHash for dummies
http://matthewcasperson.blogspot.com/2013/11/minhash-for-dummies.html
https://iq.opengenus.org/minhash/
MinHash (Probabilistic Data Structure for Similarity)
2020-10-13
Ethan Z Booker
<div><section>
<p><a href="http://internship.opengenus.org">Open-Source Internship opportunity by OpenGenus for programmers. Apply now.</a></p>
<div><p>Lets assume you wanted to find how similar two sets are. You could simply brute force your way by going through the contents of one set and compare those elements with the other set. Sure this method can work but what if you wanted to check a bunch of other sets? This would be rather slow, especially if you are working with a lot of data.</p>
<h2>Jaccard Similarity</h2>
<p><mark>Some of you may know this equation and how to apply it, so you may skip this section.</mark></p>
<p></p>
<p>For those that are unfamilar with Jaccard similarity, then this will be important.</p>
<p>You should also know how math with sets, but I'll try my best to explain these operations.</p>
<p>A <strong>set</strong> is a collection of distinct elements.</p>
<ul>
<li>This means each element in the set can only appear once.</li>
<li>Invalid set: A = { 1, 1, 2, 3, 4, 4, 4, 5}, has duplicate 1's and 4's.</li>
<li>Valid set: A = { 1, 2, 3, 4, 5 }, has no duplicates</li>
<li>Valid set: A = { }, empty set</li>
</ul>
<p>The <strong>intersection</strong> between two sets results in a set that contains elements both sets A and B share in common.</p>
<ul>
<li>Given sets: A = { 1, 2, 3 }, B = { 3, 4, 5 }</li>
<li>A ∩ B = { 3 }.</li>
</ul>
<p>The <strong>union</strong> between two sets is both sets A and B combined together and removing duplicate copies of elements.</p>
<ul>
<li>Given sets: A = { 1, 2, 3 }, B = { 3, 4, 5 }</li>
<li>A ∪ B = { 1, 2, 3, 4, 5 }</li>
</ul>
<p>The <strong>size of a set</strong> is the number of elements in a given set denoted by <strong>| set |</strong> .</p>
<ul>
<li>Given set: A = { 1, 2, 3, 4, 5 }</li>
<li>| A | = 5, because there are 5 elements.</li>
</ul>
<p>The image above shows the equation of how to calculate the Jaccard similarity which is a numeric score to compare similarity between two sets.</p>
<p>The equation states that you need to calculate the size of the intersection between A and B then divide by the size of the union of A and B. This equation can be translated into the size of the intersection between A and B divided by size of A plus size of B minus the interersection between A and B.</p>
<p>Using the information above, you could work out simple sets to determine the Jaccard similarity number.</p>
<p>The problem stated at the beginning of the article briefly covered the idea of finding Jaccard similarity but rather in an obscure way, but nonetheless trying to find the exact value is too time consuming.</p>
<p>MinHash was originally an algorithm to quickly estimate the jaccard similarity between two sets but can be designed as a data structure that revolves around the algorithm. This is a probablistic data structure that quickly estimates how similar two sets are.</p>
<p>The idea behind MinHash is representing each set as a signature. A signature preserves a permutation of a bit array representation of a set. By using hash functions that simulate a permutation, the probability of collisions against all permutations results to the Jaccard similarity.</p>
<p>This is hard to grasp, so I will walk you through what is happening.</p>
<h2>Probablistic Nature</h2>
<p>The probablistic nature behind this data structure is purely through the hash functions in the signature matrix. You will get a better understanding when you walk through the steps, but for now bare with me. The has functions in the signature matrix determine the performance of the data structure.</p>
<p>Not having enough hash functions will cause small amount of comparisons to properly gauge similarity between two sets due to all the values probably colliding. However, it's essential to create/use high quality distributed hash algorithms (could look them up) as it's unlikely to have a similar value during similarity comparison time. The more high quality hash functions you have, the better the evaluation of similarity will result, but there is a threshold, so you have to test your results and see.</p>
<p>Regardless, a hash function is the pivotal part needed but there aren't enough out there as you may want a lot. If you need more hash functions then you could use 1 hash function and go through the process of salting, which is basically rehashing a hash code over and over. Or you could create your own way to manipulate the hash code through proper bit manipulation but salting is a very easy and efficient solution. These salted hash codes would still result be good enough to act as a hash function that hashed those values.</p>
<p>Despite having quick performance, since hash functions are limited to a certain range of values and collisions are bound to happen, the similarity is not always accurate. I can't fully explain the error rate, however in the resource section, the L5-Minhash link has a more in-depth answer also Wikipedia states the true error rate.</p>
<p>This was a lot of information, the most important thing to note is that good hash functions are pivotal in the performance of this data structure as are most probablistic data structures.</p>
<h2>What the process looks like</h2>
<p>So what exactly does the MinHash data structure do? Well it's an algorithm but can be converted into a data structure and I will explain the process of creating it.</p>
<p></p>
<p>Above is the picture of the steps needed for the data structure to work. If you get confused, I will explain more in-depth the following sections.</p>
<ol>
<li>Get a collection of sets then create an input matrix known which are just rows of bit arrays.</li>
</ol>
<ul>
<li>This bit arrays will be the length of the universal set size (the total number of unique values).</li>
</ul>
<ol>
<li>Create a signature matrix filled with max value.</li>
<li>Iterate through the input matrix and whenever you see a non-zero value, find the corresponding set it bit belongs to and pass index value through the set of hash functions in the signature matrix and take the minimum value.</li>
</ol>
<h2>Step 1) Building each bit array representation</h2>
<p>The initial step is to build a bit array for each set, however we need to know how big to make it. In order to do so, you need to know the universal set size which is the size of the union of all sets that will be used later to compare.</p>
<p>Lets assume we have 3 sets</p>
<ul>
<li>A = { 1, 3, 5, 7 }</li>
<li>B = { 0, 2, 8, 10 }</li>
<li>C = { 4, 5, 6, 8, 9, 10 }</li>
<li>Universal Set ( A ∪ B ∪ C ) = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }</li>
</ul>
<p>Since the size of the universal set is 11, we will make each bit array size 11. Then you will go through each element in a set and get the hash code then bound that hash code with the total size of the universal set. Once you find the bounded hash code, you will represent that element as present denoting it a value that is not 0, such as 1.</p>
<p>In this case, let's assume the hash code of a number is the number itself. This would result in bit arrays:</p>
<ul>
<li>Bit array A = [0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0 ]</li>
<li>Bit array B = [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1 ]</li>
<li>Bit array C = [0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1 ]</li>
</ul>
<h3>Universal Set Size</h3>
<pre><code>private int getUniversalSetSize(Set&lt;T&gt;... sets) {
	Set&lt;T&gt; universalSet = new HashSet&lt;&gt;();
	for (Set&lt;T&gt; set : sets) {
	universalSet.addAll(set);
	}
	return universalSet.size();
}
</code></pre>
<p>The code above is an example of how one might find the universal size of all sets unioned together.</p>
<h3>Building Bit Arrays</h3>
<pre><code>private int[][] buildBinaryDocSet(Set&lt;T&gt;... sets) {
	int[][] binaryDocSet = new int[sets.length][totalFeatures()];
	for (int setIdx = 0; setIdx &lt; sets.length; setIdx++) {
	for (T feature : sets[setIdx]) {
	binaryDocSet[setIdx][bound(feature.hashCode())] = 1;
	}
	}
	return binaryDocSet;
}
</code></pre>
<p>We are simply iterating through each set and updating the bit array to represent out set.</p>
<ul>
<li>totalFeatures() is the universal set size.</li>
<li>bound(hashcode) is simply hashcode % universal set size</li>
</ul>
<h2>Step 2 Building the Signature Matrix</h2>
<p>After building the bit array representations, this is where minhash matrix is built.<br/>
Rows of the matrix are denoted by a hash function.<br/>
Columns of the matrix are denoted by the sets indices.</p>
<pre><code>private int[][] buildSignatureMatrix() {
	int[][] sigMatrix = initSigMatrix();
	for (int feature = 0; feature &lt; totalFeatures(); feature++) {
	for (int document = 0; document &lt; totalDocuments(); document++) {
	if (binaryDocSet[document][feature] != 0) {
	computeSigHashes(sigMatrix, document, feature);
	}
	}
	}
	return sigMatrix;
}
</code></pre>
<p>To clarify:</p>
<ul>
<li>feature and features refers to elements of a set</li>
<li>document refers to a specific index of a set.</li>
</ul>
<p>The idea behind this method is to go through each bit array and whenever we see a non-zero value, we will update our signature matrix calling computeSigHashes function.</p>
<p>It's important to initialize the matrix with all maxiumum values because we will be calling Math.min function to preserve the property of a signature matrix.</p>
<pre><code>private void computeSigHashes(int[][] sigMatrix, int document, int feature) {
	for (int hasher = 0; hasher &lt; totalHashFunctions(); hasher++) {
	sigMatrix[hasher][document] = Math.min(sigMatrix[hasher][document], bound(hashers[hasher].hash(feature)));
	}
}
</code></pre>
<p>Go through each hash function and the associated set index and then select the minimum value between the current value in the signature matrix and the bounded hashed index.</p>
<h2>Similarities</h2>
<p>After building the signature table, calculating an estimate of the Jaccard similarty will be easy.</p>
<pre><code>public double similarity(int docIndex1, int docIndex2) {
	int similar = 0;
	for (int hasher = 0; hasher &lt; totalHashFunctions(); hasher++) {
	if (signatureMatrix[hasher][docIndex1] == signatureMatrix[hasher][docIndex2]) {
	similar++;
	}
	}
	return (double) similar / totalHashFunctions();
}
</code></pre>
<p>Go down each row of the matrix and compare the set index for both. If they have the same value, increment a running count.<br/>
Lastly, divide the running count by the total rows (aka total number of hash functions).</p>
<h2>Code</h2>
<p>Here is the full code of all the segments, I have renamed some of the terms because originally this algorithm was developed for web searches but has since then found other applications.</p>
<pre><code>import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class MinHash&lt;T&gt; {
	public interface Hasher {
	int hash(int item);
	}
	private int totalFeatures;
	private int[][] binaryDocSet;
	private int[][] signatureMatrix;
	private Hasher[] hashers;
	@SafeVarargs
	public MinHash(Hasher[] hashers, Set&lt;T&gt;... sets) {
	this.hashers = hashers;
	totalFeatures = getUniversalSetSize(sets);
	binaryDocSet = buildBinaryDocSet(sets);
	signatureMatrix = buildSignatureMatrix();
	}
	@SafeVarargs
	private int getUniversalSetSize(Set&lt;T&gt;... sets) {
	Set&lt;T&gt; universalSet = new HashSet&lt;&gt;();
	for (Set&lt;T&gt; set : sets) {
	universalSet.addAll(set);
	}
	return universalSet.size();
	}
	//Better to store in a sparse matrix
	@SafeVarargs
	private int[][] buildBinaryDocSet(Set&lt;T&gt;... sets) {
	int[][] binaryDocSet = new int[sets.length][totalFeatures()];
	for (int setIdx = 0; setIdx &lt; sets.length; setIdx++) {
	for (T feature : sets[setIdx]) {
	binaryDocSet[setIdx][bound(feature.hashCode())] = 1;
	}
	}
	return binaryDocSet;
	}
	private int[][] buildSignatureMatrix() {
	int[][] sigMatrix = initSigMatrix();
	for (int feature = 0; feature &lt; totalFeatures(); feature++) {
	for (int document = 0; document &lt; totalDocuments(); document++) {
	if (binaryDocSet[document][feature] != 0) {
	computeSigHashes(sigMatrix, document, feature);
	}
	}
	}
	return sigMatrix;
	}
	private int[][] initSigMatrix() {
	int[][] sigMatrix = new int[totalHashFunctions()][totalDocuments()];
	for (int[] vector : sigMatrix) {
	Arrays.fill(vector, Integer.MAX_VALUE);
	}
	return sigMatrix;
	}
	private void computeSigHashes(int[][] sigMatrix, int document, int feature) {
	for (int hasher = 0; hasher &lt; totalHashFunctions(); hasher++) {
	sigMatrix[hasher][document] = Math.min(sigMatrix[hasher][document], bound(hashers[hasher].hash(feature)));
	}
	}
	public double similarity(int docIndex1, int docIndex2) {
	int similar = 0;
	for (int hasher = 0; hasher &lt; totalHashFunctions(); hasher++) {
	if (signatureMatrix[hasher][docIndex1] == signatureMatrix[hasher][docIndex2]) {
	similar++;
	}
	}
	return (double) similar / totalHashFunctions();
	}
	private int bound(int hash) {
	return hash % totalFeatures();
	}
	public int totalFeatures() {
	return totalFeatures;
	}
	public int totalDocuments() {
	return binaryDocSet.length;
	}
	public int totalHashFunctions() {
	return hashers.length;
	}
	public static void main(String[] arsgs) {
	Hasher h1 = num -&gt; (22 * num + 5) % 31;
	Hasher h2 = num -&gt; (30 * num + 2) % 31;
	Hasher h3 = num -&gt; (21 * num + 23) % 31;
	Hasher h4 = num -&gt; (15 * num + 6) % 31;
	Hasher[] hashers = { h1, h2, h3, h4 };
	Set&lt;Integer&gt; doc1 = new HashSet&lt;&gt;(Arrays.asList(8, 15, 16));
	Set&lt;Integer&gt; doc2 = new HashSet&lt;&gt;(Arrays.asList(1, 5, 7, 10, 11, 15, 16, 17));
	Set&lt;Integer&gt; doc3 = new HashSet&lt;&gt;(Arrays.asList(0, 1, 2, 3, 4, 5, 7, 9, 12, 17));
	Set&lt;Integer&gt; doc4 = new HashSet&lt;&gt;(Arrays.asList(1, 5, 6, 13, 14, 15));
	Set&lt;Integer&gt; doc5 = new HashSet&lt;&gt;(Arrays.asList(1, 2, 5, 9, 13, 15, 18));
	MinHash&lt;Integer&gt; minhash = new MinHash&lt;&gt;(hashers, doc1, doc2, doc3, doc4, doc5);
	System.out.println(minhash.similarity(1, 2)); //doc2, doc3
	System.out.println(minhash.similarity(3, 4)); //doc4, doc5
	System.out.println(minhash.similarity(0, 2)); //doc1, doc3
	}
}
</code></pre>
<p>This code shows you an example of sets usings numbers from 0 through 18.</p>
<h2>Pros and Cons</h2>
<ul>
<li>The minhash similarity number is an estimate of the Jaccard similarity, so sometimes there is a margin of error.</li>
<li>MinHash has many different variations such as B-bit which uses bits to save a good amount of memory rather than using purely arrays of ints while still preserving easy implementation.</li>
<li>The more refined quality hash functions that you provide, the less the error of similarity will be but at the cost of more memory.</li>
<li>You must define your own permutation hash functions which means you need to have an understanding of how quality hash functions are created.
<ul>
<li>Often a prime number is involved.</li>
</ul>
</li>
</ul>
<h2>Applications</h2>
<ul>
<li>Near-duplicates detection</li>
<li>Search industry, machine learning systems, content matching, and etc.</li>
</ul>
<h2>Resources</h2>
<ul>
<li><a href="https://www.cs.utah.edu/~jeffp/teaching/cs5955/L5-Minhash.pdf">https://www.cs.utah.edu/~jeffp/teaching/cs5955/L5-Minhash.pdf</a></li>
<li><a href="http://www.cs.cmu.edu/~guyb/realworld/slidesS13/minhash.pdf">http://www.cs.cmu.edu/~guyb/realworld/slidesS13/minhash.pdf</a></li>
</ul>
</div>
</section></div>||||I|||| ×
 Home Discussions Write at Opengenus IQ
 ×
 ☰
 * FREE ALGO BOOK
 * About
 * Track your progress
 * Deep Learning (FREE)
 * Python Projects
 * Join our Internship 🎓
 * RANDOM
 * 100+ Graph Algorithms
 * 100+ DP Problems
 * 50+ Linked List Problems
 * 50+ Array Problems
 * One Liner
 * 50+ Binary Tree problems
 * Home
 * Rust Projects
 ×

 Search anything:

 Interesting posts
 * Top Competitive Programmers
 * Unsolved Problems in Algorithms
 * Top patent holders in India
 * How to get Developer Job in Japan?
 * [INTERNSHIP]
 * STORY: Most Profitable Software Patents
 * How to earn by filing Patents?
 * Richest Programmers in the World
 * STORY: Multiplication from 1950 to 2022
 * Position of India at ICPC World Finals (1999 to 2021)
 * Most Dangerous Line of Code 💀
 * Age of All Programming Languages
 * How to earn money online as a Programmer?
 * STORY: Kolmogorov N^2 Conjecture Disproved
 * STORY: man who refused $1M for his discovery
 * STORY: Man behind VIM
 * STORY: Galactic algorithm
 * STORY: Inventor of Linked List
 * Practice Interview Questions
 * List of 50+ Binary Tree Problems
 * List of 100+ Dynamic Programming Problems
 * List of 50+ Array Problems
 * 11 Greedy Algorithm Problems [MUST]
 * List of 50+ Linked List Problems
 * 100+ Graph Algorithms and Techniques
 Data Structures tutorial
 * Anagram Trees
 * Mean of Array problem solved with Treap
 * Ghost Town problem solved with Treap Data Structure
 * Swarm Intelligence for Distributed Data Structures
 * B Tree in C++ with OOP and template
 * Fenwick Tree vs Segment Tree
 * Kinetic Heap
 * Data Structures (DS) and Quick Revision
 * Applications of 24 Different Data Structures
 * (a,b) Tree Data Structure
 * Abstract Data Type in Data Structure
 * Binary Search Tree with Parent Pointer
 * Circular Doubly Linked List
 * Introduction to Tree Data Structure
 * Array Data Structure

 MinHash (Probabilistic Data Structure for Similarity)

 Data Structures probabilistic algorithm

 More Less
 Up

 Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

 Lets assume you wanted to find how similar two sets are. You could simply brute force your way by going through the contents of one set and compare those elements with the other set. Sure this method can work but what if you wanted to check a bunch of other sets? This would be rather slow, especially if you are working with a lot of data.

 Jaccard Similarity

 Some of you may know this equation and how to apply it, so you may skip this section.

 For those that are unfamilar with Jaccard similarity, then this will be important.

 You should also know how math with sets, but I'll try my best to explain these operations.

 A set is a collection of distinct elements.

 * This means each element in the set can only appear once.
 * Invalid set: A = { 1, 1, 2, 3, 4, 4, 4, 5}, has duplicate 1's and 4's.
 * Valid set: A = { 1, 2, 3, 4, 5 }, has no duplicates
 * Valid set: A = { }, empty set

 The intersection between two sets results in a set that contains elements both sets A and B share in common.

 * Given sets: A = { 1, 2, 3 }, B = { 3, 4, 5 }
 * A ∩ B = { 3 }.

 The union between two sets is both sets A and B combined together and removing duplicate copies of elements.

 * Given sets: A = { 1, 2, 3 }, B = { 3, 4, 5 }
 * A ∪ B = { 1, 2, 3, 4, 5 }

 The size of a set is the number of elements in a given set denoted by | set | .

 * Given set: A = { 1, 2, 3, 4, 5 }
 * | A | = 5, because there are 5 elements.

 The image above shows the equation of how to calculate the Jaccard similarity which is a numeric score to compare similarity between two sets.

 The equation states that you need to calculate the size of the intersection between A and B then divide by the size of the union of A and B. This equation can be translated into the size of the intersection between A and B divided by size of A plus size of B minus the interersection between A and B.

 Using the information above, you could work out simple sets to determine the Jaccard similarity number.

 The problem stated at the beginning of the article briefly covered the idea of finding Jaccard similarity but rather in an obscure way, but nonetheless trying to find the exact value is too time consuming.

 MinHash

 MinHash was originally an algorithm to quickly estimate the jaccard similarity between two sets but can be designed as a data structure that revolves around the algorithm. This is a probablistic data structure that quickly estimates how similar two sets are.

 The idea behind MinHash is representing each set as a signature. A signature preserves a permutation of a bit array representation of a set. By using hash functions that simulate a permutation, the probability of collisions against all permutations results to the Jaccard similarity.

 This is hard to grasp, so I will walk you through what is happening.

 Probablistic Nature

 The probablistic nature behind this data structure is purely through the hash functions in the signature matrix. You will get a better understanding when you walk through the steps, but for now bare with me. The has functions in the signature matrix determine the performance of the data structure.

 Not having enough hash functions will cause small amount of comparisons to properly gauge similarity between two sets due to all the values probably colliding. However, it's essential to create/use high quality distributed hash algorithms (could look them up) as it's unlikely to have a similar value during similarity comparison time. The more high quality hash functions you have, the better the evaluation of similarity will result, but there is a threshold, so you have to test your results and see.

 Regardless, a hash function is the pivotal part needed but there aren't enough out there as you may want a lot. If you need more hash functions then you could use 1 hash function and go through the process of salting, which is basically rehashing a hash code over and over. Or you could create your own way to manipulate the hash code through proper bit manipulation but salting is a very easy and efficient solution. These salted hash codes would still result be good enough to act as a hash function that hashed those values.

 Despite having quick performance, since hash functions are limited to a certain range of values and collisions are bound to happen, the similarity is not always accurate. I can't fully explain the error rate, however in the resource section, the L5-Minhash link has a more in-depth answer also Wikipedia states the true error rate.

 This was a lot of information, the most important thing to note is that good hash functions are pivotal in the performance of this data structure as are most probablistic data structures.

 What the process looks like

 So what exactly does the MinHash data structure do? Well it's an algorithm but can be converted into a data structure and I will explain the process of creating it.

 Above is the picture of the steps needed for the data structure to work. If you get confused, I will explain more in-depth the following sections.

 1. Get a collection of sets then create an input matrix known which are just rows of bit arrays.
 * This bit arrays will be the length of the universal set size (the total number of unique values).
 1. Create a signature matrix filled with max value.
 2. Iterate through the input matrix and whenever you see a non-zero value, find the corresponding set it bit belongs to and pass index value through the set of hash functions in the signature matrix and take the minimum value.

 Step 1) Building each bit array representation

 The initial step is to build a bit array for each set, however we need to know how big to make it. In order to do so, you need to know the universal set size which is the size of the union of all sets that will be used later to compare.

 Lets assume we have 3 sets

 * A = { 1, 3, 5, 7 }
 * B = { 0, 2, 8, 10 }
 * C = { 4, 5, 6, 8, 9, 10 }
 * Universal Set ( A ∪ B ∪ C ) = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

 Since the size of the universal set is 11, we will make each bit array size 11. Then you will go through each element in a set and get the hash code then bound that hash code with the total size of the universal set. Once you find the bounded hash code, you will represent that element as present denoting it a value that is not 0, such as 1.

 In this case, let's assume the hash code of a number is the number itself. This would result in bit arrays:

 * Bit array A = [0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0 ]
 * Bit array B = [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1 ]
 * Bit array C = [0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1 ]

 Universal Set Size

 private int getUniversalSetSize(Set<T>... sets) {
 		Set<T> universalSet = new HashSet<>();
 		for (Set<T> set : sets) {
 			universalSet.addAll(set);
 		}
 		return universalSet.size();
 }
 

 The code above is an example of how one might find the universal size of all sets unioned together.

 Building Bit Arrays

 private int[][] buildBinaryDocSet(Set<T>... sets) {
 		int[][] binaryDocSet = new int[sets.length][totalFeatures()];
 
 		for (int setIdx = 0; setIdx < sets.length; setIdx++) {
 			for (T feature : sets[setIdx]) {
 				binaryDocSet[setIdx][bound(feature.hashCode())] = 1;
 			}
 		}
 
 		return binaryDocSet;
 }
 

 We are simply iterating through each set and updating the bit array to represent out set.

 * totalFeatures() is the universal set size.
 * bound(hashcode) is simply hashcode % universal set size

 Step 2 Building the Signature Matrix

 After building the bit array representations, this is where minhash matrix is built.
 Rows of the matrix are denoted by a hash function.
 Columns of the matrix are denoted by the sets indices.

 private int[][] buildSignatureMatrix() {
 		int[][] sigMatrix = initSigMatrix();
 
 		for (int feature = 0; feature < totalFeatures(); feature++) {
 			for (int document = 0; document < totalDocuments(); document++) {
 				if (binaryDocSet[document][feature] != 0) {
 					computeSigHashes(sigMatrix, document, feature);
 				}
 			}
 		}
 
 		return sigMatrix;
 }
 

 To clarify:

 * feature and features refers to elements of a set
 * document refers to a specific index of a set.

 The idea behind this method is to go through each bit array and whenever we see a non-zero value, we will update our signature matrix calling computeSigHashes function.

 It's important to initialize the matrix with all maxiumum values because we will be calling Math.min function to preserve the property of a signature matrix.

 private void computeSigHashes(int[][] sigMatrix, int document, int feature) {
 		for (int hasher = 0; hasher < totalHashFunctions(); hasher++) {
 			sigMatrix[hasher][document] = Math.min(sigMatrix[hasher][document], bound(hashers[hasher].hash(feature)));
 		}
 }
 

 Go through each hash function and the associated set index and then select the minimum value between the current value in the signature matrix and the bounded hashed index.

 Similarities

 After building the signature table, calculating an estimate of the Jaccard similarty will be easy.

 public double similarity(int docIndex1, int docIndex2) {
 		int similar = 0;
 		for (int hasher = 0; hasher < totalHashFunctions(); hasher++) {
 			if (signatureMatrix[hasher][docIndex1] == signatureMatrix[hasher][docIndex2]) {
 				similar++;
 			}
 		}
 
 		return (double) similar / totalHashFunctions();
 }
 

 Go down each row of the matrix and compare the set index for both. If they have the same value, increment a running count.
 Lastly, divide the running count by the total rows (aka total number of hash functions).

 Code

 Here is the full code of all the segments, I have renamed some of the terms because originally this algorithm was developed for web searches but has since then found other applications.

 import java.util.Arrays;
 import java.util.HashSet;
 import java.util.Set;
 
 public class MinHash<T> {
 	public interface Hasher {
 		int hash(int item);
 	}
 
 	private int totalFeatures;
 	private int[][] binaryDocSet;
 	private int[][] signatureMatrix;
 	private Hasher[] hashers;
 
 	@SafeVarargs
 	public MinHash(Hasher[] hashers, Set<T>... sets) {
 		this.hashers = hashers;
 		totalFeatures = getUniversalSetSize(sets);
 		binaryDocSet = buildBinaryDocSet(sets);
 		signatureMatrix = buildSignatureMatrix();
 	}
 
 	@SafeVarargs
 	private int getUniversalSetSize(Set<T>... sets) {
 		Set<T> universalSet = new HashSet<>();
 		for (Set<T> set : sets) {
 			universalSet.addAll(set);
 		}
 		return universalSet.size();
 	}
 
 	//Better to store in a sparse matrix
 	@SafeVarargs
 	private int[][] buildBinaryDocSet(Set<T>... sets) {
 		int[][] binaryDocSet = new int[sets.length][totalFeatures()];
 
 		for (int setIdx = 0; setIdx < sets.length; setIdx++) {
 			for (T feature : sets[setIdx]) {
 				binaryDocSet[setIdx][bound(feature.hashCode())] = 1;
 			}
 		}
 
 		return binaryDocSet;
 	}
 
 	private int[][] buildSignatureMatrix() {
 		int[][] sigMatrix = initSigMatrix();
 
 		for (int feature = 0; feature < totalFeatures(); feature++) {
 			for (int document = 0; document < totalDocuments(); document++) {
 				if (binaryDocSet[document][feature] != 0) {
 					computeSigHashes(sigMatrix, document, feature);
 				}
 			}
 		}
 
 		return sigMatrix;
 	}
 
 	private int[][] initSigMatrix() {
 		int[][] sigMatrix = new int[totalHashFunctions()][totalDocuments()];
 		for (int[] vector : sigMatrix) {
 			Arrays.fill(vector, Integer.MAX_VALUE);
 		}
 		return sigMatrix;
 	}
 
 	private void computeSigHashes(int[][] sigMatrix, int document, int feature) {
 		for (int hasher = 0; hasher < totalHashFunctions(); hasher++) {
 			sigMatrix[hasher][document] = Math.min(sigMatrix[hasher][document], bound(hashers[hasher].hash(feature)));
 		}
 	}
 
 	public double similarity(int docIndex1, int docIndex2) {
 		int similar = 0;
 		for (int hasher = 0; hasher < totalHashFunctions(); hasher++) {
 			if (signatureMatrix[hasher][docIndex1] == signatureMatrix[hasher][docIndex2]) {
 				similar++;
 			}
 		}
 
 		return (double) similar / totalHashFunctions();
 	}
 
 	private int bound(int hash) {
 		return hash % totalFeatures();
 	}
 
 	public int totalFeatures() {
 		return totalFeatures;
 	}
 
 	public int totalDocuments() {
 		return binaryDocSet.length;
 	}
 
 	public int totalHashFunctions() {
 		return hashers.length;
 	}
 
 	public static void main(String[] arsgs) {
 		Hasher h1 = num -> (22 * num + 5) % 31;
 		Hasher h2 = num -> (30 * num + 2) % 31;
 		Hasher h3 = num -> (21 * num + 23) % 31;
 		Hasher h4 = num -> (15 * num + 6) % 31;
 		Hasher[] hashers = { h1, h2, h3, h4 };
 		
 		Set<Integer> doc1 = new HashSet<>(Arrays.asList(8, 15, 16));
 		Set<Integer> doc2 = new HashSet<>(Arrays.asList(1, 5, 7, 10, 11, 15, 16, 17));
 		Set<Integer> doc3 = new HashSet<>(Arrays.asList(0, 1, 2, 3, 4, 5, 7, 9, 12, 17));
 		Set<Integer> doc4 = new HashSet<>(Arrays.asList(1, 5, 6, 13, 14, 15));
 		Set<Integer> doc5 = new HashSet<>(Arrays.asList(1, 2, 5, 9, 13, 15, 18));
 		
 		MinHash<Integer> minhash = new MinHash<>(hashers, doc1, doc2, doc3, doc4, doc5);
 		System.out.println(minhash.similarity(1, 2)); //doc2, doc3
 		System.out.println(minhash.similarity(3, 4)); //doc4, doc5
 		System.out.println(minhash.similarity(0, 2)); //doc1, doc3
 	}
 }
 

 This code shows you an example of sets usings numbers from 0 through 18.

 Pros and Cons

 * The minhash similarity number is an estimate of the Jaccard similarity, so sometimes there is a margin of error.
 * MinHash has many different variations such as B-bit which uses bits to save a good amount of memory rather than using purely arrays of ints while still preserving easy implementation.
 * The more refined quality hash functions that you provide, the less the error of similarity will be but at the cost of more memory.
 * You must define your own permutation hash functions which means you need to have an understanding of how quality hash functions are created.
 + Often a prime number is involved.

 Applications

 * Near-duplicates detection
 * Search industry, machine learning systems, content matching, and etc.

 Resources

 * https://www.cs.utah.edu/~jeffp/teaching/cs5955/L5-Minhash.pdf
 * http://www.cs.cmu.edu/~guyb/realworld/slidesS13/minhash.pdf

 Ethan Z. Booker

 Software Developer, Intern at OpenGenus | Student at University of Wisconsin - La Crosse

 Read More

 Improved & Reviewed by:


 Ue Kiao, PhD
 — OpenGenus IQ: Computing Expertise & Legacy —

 Data Structures

 * Anagram Trees
 * Task Scheduler - Algorithm and Data Structure Project [in JavaScript]
 * Mean of Array problem solved with Treap
 See all 229 posts →
 Data Structures

 LogLog (Probabilistic Data Structure for Cardinality)

 LogLog is a Probabilistic Data Structure that uses the idea of hashing to compute Cardinality of a given set.

 Ethan Z. Booker
 Data Structures

 Probabilistic Data Structures

 This is a general overview of probabilistic data structures (with examples of data structures over 5 different categories).

 Ethan Z. Booker
 OpenGenus IQ: Computing Expertise & Legacy
 —
 MinHash (Probabilistic Data Structure for Similarity)
 🔍
 Share this
 OpenGenus IQ © 2024 All rights reserved ™
 Contact - Email: team@opengenus.org
 Primary Address: JR Shinjuku Miraina Tower, Tokyo, Shinjuku 160-0022, JP
 Office #2: Commercial Complex D4, Delhi, Delhi 110017, IN
 Top Posts LinkedIn Twitter
 Android App
 Apply for Internship
Open-Source Internship opportunity by OpenGenus for programmers. Apply now. 
 Lets assume you wanted to find how similar two sets are. You could simply brute force your way by going through the contents of one set and compare those elements with the other set. Sure this method can work but what if you wanted to check a bunch of other sets? This would be rather slow, especially if you are working with a lot of data.
Jaccard Similarity
 Some of you may know this equation and how to apply it, so you may skip this section. 
 
For those that are unfamilar with Jaccard similarity, then this will be important.
You should also know how math with sets, but I'll try my best to explain these operations.
A set is a collection of distinct elements.
This means each element in the set can only appear once.
Invalid set: A = { 1, 1, 2, 3, 4, 4, 4, 5}, has duplicate 1's and 4's.
Valid set: A = { 1, 2, 3, 4, 5 }, has no duplicates
Valid set: A = { }, empty set
The intersection between two sets results in a set that contains elements both sets A and B share in common.
Given sets: A = { 1, 2, 3 }, B = { 3, 4, 5 }
A ∩ B = { 3 }.
The union between two sets is both sets A and B combined together and removing duplicate copies of elements.
Given sets: A = { 1, 2, 3 }, B = { 3, 4, 5 }
A ∪ B = { 1, 2, 3, 4, 5 }
The size of a set is the number of elements in a given set denoted by | set | .
Given set: A = { 1, 2, 3, 4, 5 }
| A | = 5, because there are 5 elements.
The image above shows the equation of how to calculate the Jaccard similarity which is a numeric score to compare similarity between two sets.
The equation states that you need to calculate the size of the intersection between A and B then divide by the size of the union of A and B. This equation can be translated into the size of the intersection between A and B divided by size of A plus size of B minus the interersection between A and B.
Using the information above, you could work out simple sets to determine the Jaccard similarity number.
The problem stated at the beginning of the article briefly covered the idea of finding Jaccard similarity but rather in an obscure way, but nonetheless trying to find the exact value is too time consuming.
MinHash was originally an algorithm to quickly estimate the jaccard similarity between two sets but can be designed as a data structure that revolves around the algorithm. This is a probablistic data structure that quickly estimates how similar two sets are.
The idea behind MinHash is representing each set as a signature. A signature preserves a permutation of a bit array representation of a set. By using hash functions that simulate a permutation, the probability of collisions against all permutations results to the Jaccard similarity.
This is hard to grasp, so I will walk you through what is happening.
Probablistic Nature
The probablistic nature behind this data structure is purely through the hash functions in the signature matrix. You will get a better understanding when you walk through the steps, but for now bare with me. The has functions in the signature matrix determine the performance of the data structure.
Not having enough hash functions will cause small amount of comparisons to properly gauge similarity between two sets due to all the values probably colliding. However, it's essential to create/use high quality distributed hash algorithms (could look them up) as it's unlikely to have a similar value during similarity comparison time. The more high quality hash functions you have, the better the evaluation of similarity will result, but there is a threshold, so you have to test your results and see.
Regardless, a hash function is the pivotal part needed but there aren't enough out there as you may want a lot. If you need more hash functions then you could use 1 hash function and go through the process of salting, which is basically rehashing a hash code over and over. Or you could create your own way to manipulate the hash code through proper bit manipulation but salting is a very easy and efficient solution. These salted hash codes would still result be good enough to act as a hash function that hashed those values.
Despite having quick performance, since hash functions are limited to a certain range of values and collisions are bound to happen, the similarity is not always accurate. I can't fully explain the error rate, however in the resource section, the L5-Minhash link has a more in-depth answer also Wikipedia states the true error rate.
This was a lot of information, the most important thing to note is that good hash functions are pivotal in the performance of this data structure as are most probablistic data structures.
What the process looks like
So what exactly does the MinHash data structure do? Well it's an algorithm but can be converted into a data structure and I will explain the process of creating it.
 
Above is the picture of the steps needed for the data structure to work. If you get confused, I will explain more in-depth the following sections.
Get a collection of sets then create an input matrix known which are just rows of bit arrays.
This bit arrays will be the length of the universal set size (the total number of unique values).
Create a signature matrix filled with max value.
Iterate through the input matrix and whenever you see a non-zero value, find the corresponding set it bit belongs to and pass index value through the set of hash functions in the signature matrix and take the minimum value.
Step 1) Building each bit array representation
The initial step is to build a bit array for each set, however we need to know how big to make it. In order to do so, you need to know the universal set size which is the size of the union of all sets that will be used later to compare.
Lets assume we have 3 sets
A = { 1, 3, 5, 7 }
B = { 0, 2, 8, 10 }
C = { 4, 5, 6, 8, 9, 10 }
Universal Set ( A ∪ B ∪ C ) = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
Since the size of the universal set is 11, we will make each bit array size 11. Then you will go through each element in a set and get the hash code then bound that hash code with the total size of the universal set. Once you find the bounded hash code, you will represent that element as present denoting it a value that is not 0, such as 1.
In this case, let's assume the hash code of a number is the number itself. This would result in bit arrays:
Bit array A = [0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0 ]
Bit array B = [1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1 ]
Bit array C = [0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1 ]
Universal Set Size
 private int getUniversalSetSize(Set&lt;T&gt;... sets) {
	Set&lt;T&gt; universalSet = new HashSet&lt;&gt;();
	for (Set&lt;T&gt; set : sets) {
	universalSet.addAll(set);
	}
	return universalSet.size();
}
 
The code above is an example of how one might find the universal size of all sets unioned together.
Building Bit Arrays
 private int[][] buildBinaryDocSet(Set&lt;T&gt;... sets) {
	int[][] binaryDocSet = new int[sets.length][totalFeatures()];
	for (int setIdx = 0; setIdx &lt; sets.length; setIdx++) {
	for (T feature : sets[setIdx]) {
	binaryDocSet[setIdx][bound(feature.hashCode())] = 1;
	}
	}
	return binaryDocSet;
}
 
We are simply iterating through each set and updating the bit array to represent out set.
totalFeatures() is the universal set size.
bound(hashcode) is simply hashcode % universal set size
Step 2 Building the Signature Matrix
After building the bit array representations, this is where minhash matrix is built.
Rows of the matrix are denoted by a hash function.
Columns of the matrix are denoted by the sets indices.
 private int[][] buildSignatureMatrix() {
	int[][] sigMatrix = initSigMatrix();
	for (int feature = 0; feature &lt; totalFeatures(); feature++) {
	for (int document = 0; document &lt; totalDocuments(); document++) {
	if (binaryDocSet[document][feature] != 0) {
	computeSigHashes(sigMatrix, document, feature);
	}
	}
	}
	return sigMatrix;
}
 
To clarify:
feature and features refers to elements of a set
document refers to a specific index of a set.
The idea behind this method is to go through each bit array and whenever we see a non-zero value, we will update our signature matrix calling computeSigHashes function.
It's important to initialize the matrix with all maxiumum values because we will be calling Math.min function to preserve the property of a signature matrix.
 private void computeSigHashes(int[][] sigMatrix, int document, int feature) {
	for (int hasher = 0; hasher &lt; totalHashFunctions(); hasher++) {
	sigMatrix[hasher][document] = Math.min(sigMatrix[hasher][document], bound(hashers[hasher].hash(feature)));
	}
}
 
Go through each hash function and the associated set index and then select the minimum value between the current value in the signature matrix and the bounded hashed index.
Similarities
After building the signature table, calculating an estimate of the Jaccard similarty will be easy.
 public double similarity(int docIndex1, int docIndex2) {
	int similar = 0;
	for (int hasher = 0; hasher &lt; totalHashFunctions(); hasher++) {
	if (signatureMatrix[hasher][docIndex1] == signatureMatrix[hasher][docIndex2]) {
	similar++;
	}
	}
	return (double) similar / totalHashFunctions();
}
 
Go down each row of the matrix and compare the set index for both. If they have the same value, increment a running count.
Lastly, divide the running count by the total rows (aka total number of hash functions).
Code
Here is the full code of all the segments, I have renamed some of the terms because originally this algorithm was developed for web searches but has since then found other applications.
 import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
public class MinHash&lt;T&gt; {
	public interface Hasher {
	int hash(int item);
	}
	private int totalFeatures;
	private int[][] binaryDocSet;
	private int[][] signatureMatrix;
	private Hasher[] hashers;
	@SafeVarargs
	public MinHash(Hasher[] hashers, Set&lt;T&gt;... sets) {
	this.hashers = hashers;
	totalFeatures = getUniversalSetSize(sets);
	binaryDocSet = buildBinaryDocSet(sets);
	signatureMatrix = buildSignatureMatrix();
	}
	@SafeVarargs
	private int getUniversalSetSize(Set&lt;T&gt;... sets) {
	Set&lt;T&gt; universalSet = new HashSet&lt;&gt;();
	for (Set&lt;T&gt; set : sets) {
	universalSet.addAll(set);
	}
	return universalSet.size();
	}
	//Better to store in a sparse matrix
	@SafeVarargs
	private int[][] buildBinaryDocSet(Set&lt;T&gt;... sets) {
	int[][] binaryDocSet = new int[sets.length][totalFeatures()];
	for (int setIdx = 0; setIdx &lt; sets.length; setIdx++) {
	for (T feature : sets[setIdx]) {
	binaryDocSet[setIdx][bound(feature.hashCode())] = 1;
	}
	}
	return binaryDocSet;
	}
	private int[][] buildSignatureMatrix() {
	int[][] sigMatrix = initSigMatrix();
	for (int feature = 0; feature &lt; totalFeatures(); feature++) {
	for (int document = 0; document &lt; totalDocuments(); document++) {
	if (binaryDocSet[document][feature] != 0) {
	computeSigHashes(sigMatrix, document, feature);
	}
	}
	}
	return sigMatrix;
	}
	private int[][] initSigMatrix() {
	int[][] sigMatrix = new int[totalHashFunctions()][totalDocuments()];
	for (int[] vector : sigMatrix) {
	Arrays.fill(vector, Integer.MAX_VALUE);
	}
	return sigMatrix;
	}
	private void computeSigHashes(int[][] sigMatrix, int document, int feature) {
	for (int hasher = 0; hasher &lt; totalHashFunctions(); hasher++) {
	sigMatrix[hasher][document] = Math.min(sigMatrix[hasher][document], bound(hashers[hasher].hash(feature)));
	}
	}
	public double similarity(int docIndex1, int docIndex2) {
	int similar = 0;
	for (int hasher = 0; hasher &lt; totalHashFunctions(); hasher++) {
	if (signatureMatrix[hasher][docIndex1] == signatureMatrix[hasher][docIndex2]) {
	similar++;
	}
	}
	return (double) similar / totalHashFunctions();
	}
	private int bound(int hash) {
	return hash % totalFeatures();
	}
	public int totalFeatures() {
	return totalFeatures;
	}
	public int totalDocuments() {
	return binaryDocSet.length;
	}
	public int totalHashFunctions() {
	return hashers.length;
	}
	public static void main(String[] arsgs) {
	Hasher h1 = num -&gt; (22 * num + 5) % 31;
	Hasher h2 = num -&gt; (30 * num + 2) % 31;
	Hasher h3 = num -&gt; (21 * num + 23) % 31;
	Hasher h4 = num -&gt; (15 * num + 6) % 31;
	Hasher[] hashers = { h1, h2, h3, h4 };
	Set&lt;Integer&gt; doc1 = new HashSet&lt;&gt;(Arrays.asList(8, 15, 16));
	Set&lt;Integer&gt; doc2 = new HashSet&lt;&gt;(Arrays.asList(1, 5, 7, 10, 11, 15, 16, 17));
	Set&lt;Integer&gt; doc3 = new HashSet&lt;&gt;(Arrays.asList(0, 1, 2, 3, 4, 5, 7, 9, 12, 17));
	Set&lt;Integer&gt; doc4 = new HashSet&lt;&gt;(Arrays.asList(1, 5, 6, 13, 14, 15));
	Set&lt;Integer&gt; doc5 = new HashSet&lt;&gt;(Arrays.asList(1, 2, 5, 9, 13, 15, 18));
	MinHash&lt;Integer&gt; minhash = new MinHash&lt;&gt;(hashers, doc1, doc2, doc3, doc4, doc5);
	System.out.println(minhash.similarity(1, 2)); //doc2, doc3
	System.out.println(minhash.similarity(3, 4)); //doc4, doc5
	System.out.println(minhash.similarity(0, 2)); //doc1, doc3
	}
}
 
This code shows you an example of sets usings numbers from 0 through 18.
Pros and Cons
The minhash similarity number is an estimate of the Jaccard similarity, so sometimes there is a margin of error.
MinHash has many different variations such as B-bit which uses bits to save a good amount of memory rather than using purely arrays of ints while still preserving easy implementation.
The more refined quality hash functions that you provide, the less the error of similarity will be but at the cost of more memory.
You must define your own permutation hash functions which means you need to have an understanding of how quality hash functions are created.
Often a prime number is involved.
Applications
Near-duplicates detection
Search industry, machine learning systems, content matching, and etc.
Resources
 https://www.cs.utah.edu/~jeffp/teaching/cs5955/L5-Minhash.pdf 
 http://www.cs.cmu.edu/~guyb/realworld/slidesS13/minhash.pdf
MinHash (Probabilistic Data Structure for Similarity)
https://iq.opengenus.org/minhash/
https://www.jeremykun.com/2015/12/28/load-balancing-and-the-power-of-hashing/
Load Balancing and the Power of Hashing
2015-12-28
None
<div><p>This article was ported from my old Wordpress blog <a href="https://jeremykun.wpcomstaging.com/2015/12/28/load-balancing-and-the-power-of-hashing/">here,</a> If you see any issues with the rendering or layout, please <a href="mailto:mathintersectprogramming@gmail.com">send me an email</a>.</p><div><p>Here’s a bit of folklore I often hear (and retell) that’s somewhere between a joke and deep wisdom: if you’re doing a software interview that involves some algorithms problem that seems hard, your best bet is to use hash tables.</p><p>More succinctly put: Google loves hash tables.</p><p>As someone with a passion for math and theoretical CS, it’s kind of silly and reductionist. But if you actually work with terabytes of data that can’t fit on a single machine, it also makes sense.</p><p>But to understand why hash tables are so applicable, you should have at least a fuzzy understanding of the math that goes into it, which is surprisingly unrelated to the actual act of hashing. Instead it’s the guarantees that a “random enough” hash provides that makes it so useful. The basic intuition is that if you have an algorithm that works well assuming the input data is completely random, then you can probably get a good guarantee by preprocessing the input by hashing.</p><p>In this post I’ll explain the details, and show the application to an important problem that one often faces in dealing with huge amounts of data: how to allocate resources efficiently (load balancing). As usual, all of the code used in the making of this post <a href="https://github.com/j2kun/load-balancing">is available on Github</a>.</p><p>Next week, I’ll follow this post up with another application of hashing to estimating the number of distinct items in a set that’s too large to store in memory.</p><h2>Families of Hash Functions<a href="#families-of-hash-functions"></a></h2><p>To emphasize which specific properties of hash functions are important for a given application, we start by introducing an abstraction: a hash function is just some computable function that accepts strings as input and produces numbers between 1 and as output. We call the set of allowed inputs (for “Universe”). A <em>family</em> of hash functions is just a set of possible hash functions to choose from. We’ll use a scripty for our family, and so every hash function in is a function .</p><p>You can use a single hash function to maintain an unordered set of objects in a computer. The reason this is a problem that needs solving is because if you were to store items sequentially in a list, and if you want to determine if a specific item is already in the list, you need to potentially check every item in the list (or do something fancier). In any event, without hashing you have to spend some non-negligible amount of time searching. With hashing, you can choose the location of an element based on the value of its hash . If you pick your hash function well, then you’ll have very few collisions and can deal with them efficiently. The <a href="https://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_linked_lists">relevant section on Wikipedia</a> has more about the various techniques to deal with collisions in hash tables specifically, but we want to move beyond that in this post.</p><p>Here we have a family of random hash functions. So what’s the use of having many hash functions? You can pick a hash randomly from a “good” family of hash functions. While this doesn’t seem so magical, it has the informal property that it makes arbitrary data “random enough,” so that an algorithm which you designed to work with truly random data will also work with the hashes of arbitrary data. Moreover, even if an adversary knows and knows that you’re picking a hash function at random, there’s no way for the adversary to manufacture problems by feeding bad data. With overwhelming probability the worst-case scenario will not occur. Our first example of this is in load-balancing.</p><h2>Load balancing and 2-uniformity<a href="#load-balancing-and-2-uniformity"></a></h2><p>You can imagine load balancing in two ways, concretely and mathematically. In the concrete version you have a public-facing server that accepts requests from users, and forwards them to a back-end server which processes them and sends a response to the user. When you have a billion users and a million servers, you want to forward the requests in such a way that no server gets too many requests, or else the users will experience delays. Moreover, you’re worried that the League of Tanzanian Hackers is trying to take down your website by sending you requests in a carefully chosen order so as to screw up your load balancing algorithm.</p><p>The mathematical version of this problem usually goes with the metaphor of balls and bins. You have some collection of balls and bins in which to put the balls, and you want to put the balls into the bins. But there’s a twist: an adversary is throwing balls at you, and you have to put them into the bins before the next ball comes, so you don’t have time to remember (or count) how many balls are in each bin already. You only have time to do a small bit of mental arithmetic, sending ball to bin where is some simple function. Moreover, whatever rule you pick for distributing the balls in the bins, the adversary knows it and will throw balls at you in the worst order possible.</p><figure><figcaption><p>A young man applying his knowledge of balls and bins. That’s totally what he’s doing.</p></figcaption></figure><p>There is one obvious approach: why not just pick a uniformly random bin for each ball? The problem here is that we need the choice to be persistent. That is, if the adversary throws the same ball at us a second time, we need to put it in the same bin as the first time, and it doesn’t count toward the overall load. This is where the ball/bin metaphor breaks down. In the request/server picture, there is data specific to each user stored on the back-end server between requests (a session), and you need to make sure that data is not lost for some reasonable period of time. And if we were to save a uniform random choice after each request, we’d need to store a number for every request, which is too much. In short, we need the mapping to be persistent, but we also want it to be “like random” in effect.</p><p>So what do you do? The idea is to take a “good” family of hash functions , pick one uniformly at random for the whole game, and when you get a request/ball send it to server/bin . Note that in this case, the adversary knows your universal family ahead of time, <em>and</em> it knows your algorithm of committing to <em>some</em> single randomly chosen , but the adversary does not know which particular you chose.</p><p>The property of a family of hash functions that makes this strategy work is called <em>2-universality</em>.</p><p><strong>Definition:</strong> A family of functions from some universe . is called <em>2-universal</em> if, for every two distinct , the probability over the random choice of a hash function from that is at most . In notation,</p><p>I’ll give an example of such a family shortly, but let’s apply this to our load balancing problem. Our load-balancing algorithm would fail if, with even some modest probability, there is some server that receives many more than its fair share () of the requests. If is 2-universal, then we can compute an upper bound on the expected load of a given server, say server 1. Specifically, pick any element which hashes to 1 under our randomly chosen . Then we can compute an upper bound on the expected number of other elements that hash to 1. In this computation we’ll only use the fact that expectation splits over sums, and the definition of 2-universal. Call the random variable which is zero when and one when , and call . In words, simply represents the number of inputs that hash to 1. Then</p><figure></figure><p>So in expectation we can expect server 1 gets its fair share of requests. And clearly this doesn’t depend on the output hash being 1; it works for any server. There are two obvious questions.</p><ol><li>How do we measure the risk that, despite the expectation we computed above, <em>some</em> server is overloaded?</li><li>If it seems like (1) is on track to happen, what can you do?</li></ol><p>For 1 we’re asking to compute, for a given deviation , the probability that . This makes more sense if we jump to multiplicative factors, since it’s usually okay for a server to bear twice or three times its usual load, but not like times more than it’s usual load. (Industry experts, please correct me if I’m wrong! I’m far from an expert on the practical details of load balancing.)</p><p>So we want to know what is the probability that for some small number , and we want this to get small quickly as grows. This is where the <a href="http://jeremykun.com/2013/04/15/probabilistic-bounds-a-primer/">Chebyshev inequality</a> becomes useful. For those who don’t want to click the link, for our sitauation Chebyshev’s inequality is the statement that, for any random variable </p><p>So all we need to do is compute the variance of the load of a server. It’s a bit of a hairy calculation to write down, but rest assured it doesn’t use anything fancier than the linearity of expectation and 2-universality. Let’s dive in. We start by writing the definition of variance as an expectation, and then we split up into its parts, expand the product and group the parts.</p><p>The easy part is , it’s just , and the hard part is . So let’s compute that</p><figure></figure><p>In order to continue (and get a reasonable bound) we need an additional property of our hash family which is not immediately spelled out by 2-universality. Specifically, we need that for every and , . In other words, each hash function should evenly split the inputs across servers.</p><p>The reason this helps is because we can split into . Using 2-universality to bound the left term, this quantity is at most , and since there are total terms in the double sum above, the whole thing is at most . Note that in our big-O analysis we’re assuming is much bigger than .</p><p>Sweeping some of the details inside the big-O, this means that our variance is , and so our bound on the deviation of from its expectation by a multiplicative factor of is at most .</p><p>Now we computed a bound on the probability that a <em>single</em> server is not overloaded, but if we want to extend that to the worst-case server, the typical probability technique is to take the <em>union bound</em> over all servers. This means we just add up all the individual bounds and ignore how they relate. So the probability that <em>some</em> server has a load more than a multiplicative factor of is bounded from above . This is only less than one when , so all we can say with this analysis is that (with some small constant probability) no server will have a load worse than times more than the expected load.</p><p>So we have this analysis that seems not so good. If we have a million servers then the worst load on one server could potentially be a thousand times higher than the expected load. This doesn’t scale, and the problem could be in any (or all) of three places:</p><ol><li>Our analysis is weak, and we should use tighter bounds because the true max load is actually much smaller.</li><li>Our hash families don’t have strong enough properties, and we should beef those up to get tighter bounds.</li><li>The whole algorithm sucks and needs to be improved.</li></ol><p>It turns out all three are true. One heuristic solution is easy and avoids all math. Have some second server (which does not process requests) count hash collisions. When some server exceeds a factor of more than the expected load, send a message to the load balancer to randomly pick a new hash function from and for any requests that don’t have existing sessions (this is included in the request data), use the new hash function. Once the old sessions expire, switch any new incoming requests from those IPs over to the new hash function.</p><p>But there are much better solutions out there. Unfortunately their analyses are too long for a blog post (they fill multiple research papers). Fortunately their descriptions and guarantees are easy to describe, and they’re easy to program. The basic idea goes by the name “the power of two choices,” which we explored on this blog in a completely different context of <a href="http://jeremykun.com/2015/02/02/the-giant-component-and-explosive-percolation/">random graphs</a>.</p><p>In more detail, the idea is that you start by picking <em>two</em> random hash functions , and when you get a new request, you compute both hashes, inspect the load of the two servers indexed by those hashes, and send the request to the server with the smaller load.</p><p>This has the disadvantage of requiring bidirectional talk between the load balancer and the server, rather than obliviously forwarding requests. But the advantage is an <em>exponential</em> decrease in the worst-case maximum load. In particular, the following theorem holds for the case where the hashes are fully random.</p><p><strong>Theorem:</strong> Suppose one places balls into bins in order according to the following procedure: for each ball pick two uniformly random and independent integers , and place the ball into the bin with the smallest current size. If there are ties pick the bin with the smaller index. Then with high probability the largest bin has no more than balls.</p><p>This theorem appears to have been proved in a few different forms, with the best analysis being by <a href="http://www.cc.gatech.edu/~vigoda/RandAlgs/BCSV.pdf">Berenbrink et al</a>. You can improve the constant on the by computing more than 2 hashes. How does this relate to a good family of hash functions, which is not quite fully random? Let’s explore the answer by implementing the algorithm in python.</p><h2>An example of universal hash functions, and the load balancing algorithm<a href="#an-example-of-universal-hash-functions-and-the-load-balancing-algorithm"></a></h2><p>In order to implement the load balancer, we need to have some good hash functions under our belt. We’ll go with the simplest example of a hash function that’s easy to prove nice properties for. Specifically each hash in our family just performs some arithmetic modulo a random prime.</p><p><strong>Definition:</strong> Pick any prime , and for any and define . Let .</p><p>This family of hash functions is 2-universal.</p><p><strong>Theorem:</strong> For every ,</p><p><em>Proof.</em> To say that is to say that for some integer . I.e., the two remainders of and are equivalent mod . The ’s cancel and we can solve for </p><p>Since , there are possible choices for . Moreover, there is no point to pick bigger than since we’re working modulo . So there are possible values for the right hand side of the above equation. So if we chose them uniformly at random, (remember, is fixed ahead of time, so the only choice is ), then there is a out of chance that the equality holds, which is at most . (To be exact you should account for taking a floor of when does not evenly divide , but it only decreases the overall probability.)</p><p>If and were equal then this would be even more trivial: it’s just the fact that there is a unique line passing through any two distinct points. While that’s obviously true from standard geometry, it is also true when you work with arithmetic modulo a prime. In fact, it works using <a href="http://jeremykun.com/2014/02/26/finite-fields-a-primer/">arithmetic over any field</a>.</p><p>Implementing these hash functions is easier than shooting fish in a barrel.</p><div><pre><code></code></pre></div><p>To encapsulate the process a little bit we implemented a <code>UniversalHashFamily</code> class which computes a <a href="http://jeremykun.com/2013/06/16/miller-rabin-primality-test/">random probable prime</a> to use as the modulus and stores . The interested reader can see <a href="https://github.com/j2kun/load-balancing">the Github repository</a> for more.</p><p>If we try to run this and feed in a large range of inputs, we can see how the outputs are distributed. In this example is a hundred thousand and is a hundred (it’s not two terabytes, but give me some slack it’s a demo and I’ve only got my desktop!). So the expected bin size for any 2-universal family is just about 1,000.</p><div><pre><code></code></pre></div><p>Indeed, the max is very close to the expected value.</p><p>But this example is misleading, because the point of this was that some adversary would try to screw us over by picking a worst-case input. If the adversary knew exactly which was chosen (which it doesn’t) then the worst case input would be the set of all inputs that have the given hash output value. Let’s see it happen live.</p><div><pre><code></code></pre></div><p>The expected size of a bin is 12, but as expected this is 100 times worse (linearly worse in ). But if we instead pick a random after the bad inputs are chosen, the result is much better.</p><div><pre><code></code></pre></div><p>However, if you re-ran this test many times, you’d eventually get unlucky and draw the hash function for which this actually is the worst input, and get a single huge bin. Other times you can get a bad hash in which two or three bins have all the inputs.</p><p>An interesting question is, what is really the worst-case input for this algorithm? I suspect it’s characterized by some choice of hash output values, taking all inputs for the chosen outputs. If this is the case, then there’s a tradeoff between the number of inputs you pick and how egregious the worst bin is. As an exercise to the reader, empirically estimate this tradeoff and find the best worst-case input for the adversary. Also, for your choice of parameters, estimate by simulation the probability that the max bin is three times larger than the expected value.</p><p>Now that we’ve played around with the basic hashing algorithm and made a family of 2-universal hashes, let’s see the power of two choices. Recall, this algorithm picks <em>two</em> random hash functions and sends an input to the bin with the smallest size. This obviously generalizes to choices, although the theoretical guarantee only improves by a constant factor, so let’s implement the more generic version.</p><div><pre><code></code></pre></div><p>And if we test this with the bad inputs (as used previously, all the inputs that hash to 9), as a typical output we get</p><div><pre><code></code></pre></div><p>And a typical list of bin maxima is</p><div><pre><code></code></pre></div><p>Those big bumps are the times when we picked an unlucky hash function, which is scarily large, although this bad event would be proportionally less likely as you scale up. But in the good case the load is clearly more even than the previous example, and the max load would get linearly smaller as you pick between a larger set of randomly chosen hashes (obviously).</p><p>Coupling this with the technique of switching hash functions when you start to observe a large deviation, and you have yourself an elegant solution.</p><p>In addition to load balancing, hashing has a ton of applications. Remember, the main key that you may want to use hashing is when you have an algorithm that works well when the input data is random. This comes up in streaming and sublinear algorithms, in data structure design and analysis, and many other places. We’ll be covering those applications in future posts on this blog.</p><p>Until then!</p></div></div>||||I|||| / Math ∩ Programming / Posts
 * Main Content
 * Primers
 * All articles
 * About
 * rss

Load Balancing and the Power of Hashing

 #chebyshev #hashing #load balancing #mathematics #programming #python
 2015-12-28


 This article was ported from my old Wordpress blog here, If you see any issues with the rendering or layout, please send me an email.

 Here’s a bit of folklore I often hear (and retell) that’s somewhere between a joke and deep wisdom: if you’re doing a software interview that involves some algorithms problem that seems hard, your best bet is to use hash tables.

 More succinctly put: Google loves hash tables.

 As someone with a passion for math and theoretical CS, it’s kind of silly and reductionist. But if you actually work with terabytes of data that can’t fit on a single machine, it also makes sense.

 But to understand why hash tables are so applicable, you should have at least a fuzzy understanding of the math that goes into it, which is surprisingly unrelated to the actual act of hashing. Instead it’s the guarantees that a “random enough” hash provides that makes it so useful. The basic intuition is that if you have an algorithm that works well assuming the input data is completely random, then you can probably get a good guarantee by preprocessing the input by hashing.

 In this post I’ll explain the details, and show the application to an important problem that one often faces in dealing with huge amounts of data: how to allocate resources efficiently (load balancing). As usual, all of the code used in the making of this post is available on Github.

 Next week, I’ll follow this post up with another application of hashing to estimating the number of distinct items in a set that’s too large to store in memory.

 Families of Hash Functions

 To emphasize which specific properties of hash functions are important for a given application, we start by introducing an abstraction: a hash function is just some computable function that accepts strings as input and produces numbers between 1 and n as output. We call the set of allowed inputs U (for “Universe”). A family of hash functions is just a set of possible hash functions to choose from. We’ll use a scripty H for our family, and so every hash function h in H is a function h:U→{1,…,n}.

 You can use a single hash function h to maintain an unordered set of objects in a computer. The reason this is a problem that needs solving is because if you were to store items sequentially in a list, and if you want to determine if a specific item is already in the list, you need to potentially check every item in the list (or do something fancier). In any event, without hashing you have to spend some non-negligible amount of time searching. With hashing, you can choose the location of an element x∈U based on the value of its hash h(x). If you pick your hash function well, then you’ll have very few collisions and can deal with them efficiently. The relevant section on Wikipedia has more about the various techniques to deal with collisions in hash tables specifically, but we want to move beyond that in this post.

 Here we have a family of random hash functions. So what’s the use of having many hash functions? You can pick a hash randomly from a “good” family of hash functions. While this doesn’t seem so magical, it has the informal property that it makes arbitrary data “random enough,” so that an algorithm which you designed to work with truly random data will also work with the hashes of arbitrary data. Moreover, even if an adversary knows H and knows that you’re picking a hash function at random, there’s no way for the adversary to manufacture problems by feeding bad data. With overwhelming probability the worst-case scenario will not occur. Our first example of this is in load-balancing.

 Load balancing and 2-uniformity

 You can imagine load balancing in two ways, concretely and mathematically. In the concrete version you have a public-facing server that accepts requests from users, and forwards them to a back-end server which processes them and sends a response to the user. When you have a billion users and a million servers, you want to forward the requests in such a way that no server gets too many requests, or else the users will experience delays. Moreover, you’re worried that the League of Tanzanian Hackers is trying to take down your website by sending you requests in a carefully chosen order so as to screw up your load balancing algorithm.

 The mathematical version of this problem usually goes with the metaphor of balls and bins. You have some collection of m balls and n bins in which to put the balls, and you want to put the balls into the bins. But there’s a twist: an adversary is throwing balls at you, and you have to put them into the bins before the next ball comes, so you don’t have time to remember (or count) how many balls are in each bin already. You only have time to do a small bit of mental arithmetic, sending ball i to bin f(i) where f is some simple function. Moreover, whatever rule you pick for distributing the balls in the bins, the adversary knows it and will throw balls at you in the worst order possible.

 A young man applying his knowledge of balls and bins. That’s totally what he’s doing.

 There is one obvious approach: why not just pick a uniformly random bin for each ball? The problem here is that we need the choice to be persistent. That is, if the adversary throws the same ball at us a second time, we need to put it in the same bin as the first time, and it doesn’t count toward the overall load. This is where the ball/bin metaphor breaks down. In the request/server picture, there is data specific to each user stored on the back-end server between requests (a session), and you need to make sure that data is not lost for some reasonable period of time. And if we were to save a uniform random choice after each request, we’d need to store a number for every request, which is too much. In short, we need the mapping to be persistent, but we also want it to be “like random” in effect.

 So what do you do? The idea is to take a “good” family of hash functions H, pick one h∈H uniformly at random for the whole game, and when you get a request/ball x∈U send it to server/bin h(x). Note that in this case, the adversary knows your universal family H ahead of time, and it knows your algorithm of committing to some single randomly chosen h∈H, but the adversary does not know which particular h you chose.

 The property of a family of hash functions that makes this strategy work is called 2-universality.

 Definition: A family of functions H from some universe U→{1,…,n}. is called 2-universal if, for every two distinct x,y∈U, the probability over the random choice of a hash function h from H that h(x)=h(y) is at most 1/n. In notation,

 Prh∈H[h(x)=h(y)]≤1n

 I’ll give an example of such a family shortly, but let’s apply this to our load balancing problem. Our load-balancing algorithm would fail if, with even some modest probability, there is some server that receives many more than its fair share (m/n) of the m requests. If H is 2-universal, then we can compute an upper bound on the expected load of a given server, say server 1. Specifically, pick any element x which hashes to 1 under our randomly chosen h. Then we can compute an upper bound on the expected number of other elements that hash to 1. In this computation we’ll only use the fact that expectation splits over sums, and the definition of 2-universal. Call 1h(y)=1 the random variable which is zero when h(y)≠1 and one when h(y)=1, and call X=∑y∈U1h(y)=1. In words, X simply represents the number of inputs that hash to 1. Then

 So in expectation we can expect server 1 gets its fair share of requests. And clearly this doesn’t depend on the output hash being 1; it works for any server. There are two obvious questions.

 1. How do we measure the risk that, despite the expectation we computed above, some server is overloaded?
 2. If it seems like (1) is on track to happen, what can you do?

 For 1 we’re asking to compute, for a given deviation t, the probability that X–E[X]>t. This makes more sense if we jump to multiplicative factors, since it’s usually okay for a server to bear twice or three times its usual load, but not like n times more than it’s usual load. (Industry experts, please correct me if I’m wrong! I’m far from an expert on the practical details of load balancing.)

 So we want to know what is the probability that X–E[X]>t⋅E[X] for some small number t, and we want this to get small quickly as t grows. This is where the Chebyshev inequality becomes useful. For those who don’t want to click the link, for our sitauation Chebyshev’s inequality is the statement that, for any random variable X

 Pr[|X–E[X]|>tE[X]]≤Var[X]t2E2[X].

 So all we need to do is compute the variance of the load of a server. It’s a bit of a hairy calculation to write down, but rest assured it doesn’t use anything fancier than the linearity of expectation and 2-universality. Let’s dive in. We start by writing the definition of variance as an expectation, and then we split X up into its parts, expand the product and group the parts.

 Var[X]=E[(X–E[X])2]=E[X2]–(E[X])2

 The easy part is (E[X])2, it’s just (1+(m−1)/n)2, and the hard part is E[X2]. So let’s compute that

 In order to continue (and get a reasonable bound) we need an additional property of our hash family which is not immediately spelled out by 2-universality. Specifically, we need that for every h and i, Prx[h(x)=i]=O(1n). In other words, each hash function should evenly split the inputs across servers.

 The reason this helps is because we can split Pr[h(x)=h(y)=1] into Pr[h(x)=h(y)∣h(x)=1]⋅Pr[h(x)=1]. Using 2-universality to bound the left term, this quantity is at most 1/n2, and since there are (m2) total terms in the double sum above, the whole thing is at most O(m/n+m2/n2)=O(m2/n2). Note that in our big-O analysis we’re assuming m is much bigger than n.

 Sweeping some of the details inside the big-O, this means that our variance is O(m2/n2), and so our bound on the deviation of X from its expectation by a multiplicative factor of t is at most O(1/t2).

 Now we computed a bound on the probability that a single server is not overloaded, but if we want to extend that to the worst-case server, the typical probability technique is to take the union bound over all servers. This means we just add up all the individual bounds and ignore how they relate. So the probability that some server has a load more than a multiplicative factor of t is bounded from above O(n/t2). This is only less than one when t=Ω(n), so all we can say with this analysis is that (with some small constant probability) no server will have a load worse than n times more than the expected load.

 So we have this analysis that seems not so good. If we have a million servers then the worst load on one server could potentially be a thousand times higher than the expected load. This doesn’t scale, and the problem could be in any (or all) of three places:

 1. Our analysis is weak, and we should use tighter bounds because the true max load is actually much smaller.
 2. Our hash families don’t have strong enough properties, and we should beef those up to get tighter bounds.
 3. The whole algorithm sucks and needs to be improved.

 It turns out all three are true. One heuristic solution is easy and avoids all math. Have some second server (which does not process requests) count hash collisions. When some server exceeds a factor of t more than the expected load, send a message to the load balancer to randomly pick a new hash function from H and for any requests that don’t have existing sessions (this is included in the request data), use the new hash function. Once the old sessions expire, switch any new incoming requests from those IPs over to the new hash function.

 But there are much better solutions out there. Unfortunately their analyses are too long for a blog post (they fill multiple research papers). Fortunately their descriptions and guarantees are easy to describe, and they’re easy to program. The basic idea goes by the name “the power of two choices,” which we explored on this blog in a completely different context of random graphs.

 In more detail, the idea is that you start by picking two random hash functions h1,h2∈H, and when you get a new request, you compute both hashes, inspect the load of the two servers indexed by those hashes, and send the request to the server with the smaller load.

 This has the disadvantage of requiring bidirectional talk between the load balancer and the server, rather than obliviously forwarding requests. But the advantage is an exponential decrease in the worst-case maximum load. In particular, the following theorem holds for the case where the hashes are fully random.

 Theorem: Suppose one places m balls into n bins in order according to the following procedure: for each ball pick two uniformly random and independent integers 1≤i,j≤n, and place the ball into the bin with the smallest current size. If there are ties pick the bin with the smaller index. Then with high probability the largest bin has no more than Θ(m/n)+O(log⁡log⁡(n)) balls.

 This theorem appears to have been proved in a few different forms, with the best analysis being by Berenbrink et al. You can improve the constant on the log⁡log⁡n by computing more than 2 hashes. How does this relate to a good family of hash functions, which is not quite fully random? Let’s explore the answer by implementing the algorithm in python.

 An example of universal hash functions, and the load balancing algorithm

 In order to implement the load balancer, we need to have some good hash functions under our belt. We’ll go with the simplest example of a hash function that’s easy to prove nice properties for. Specifically each hash in our family just performs some arithmetic modulo a random prime.

 Definition: Pick any prime p>m, and for any 1≤a<p and 0≤b≤n define ha,b(x)=(ax+bmodp)modm. Let H={ha,b∣0≤b<p,1≤a<p}.

 This family of hash functions is 2-universal.

 Theorem: For every x≠y∈{0,…,p},

 Prh∈H[h(x)=h(y)]≤1/p

 Proof. To say that h(x)=h(y) is to say that ax+b=ay+b+i⋅mmodp for some integer i. I.e., the two remainders of ax+b and ay+b are equivalent mod m. The b’s cancel and we can solve for a

 a=im(x−y)−1modp

 Since a≠0, there are p−1 possible choices for a. Moreover, there is no point to pick i bigger than p/m since we’re working modulo p. So there are (p−1)/m possible values for the right hand side of the above equation. So if we chose them uniformly at random, (remember, x−y is fixed ahead of time, so the only choice is a,i), then there is a (p−1)/m out of p−1 chance that the equality holds, which is at most 1/m. (To be exact you should account for taking a floor of (p−1)/m when m does not evenly divide p−1, but it only decreases the overall probability.)

 ◻

 If m and p were equal then this would be even more trivial: it’s just the fact that there is a unique line passing through any two distinct points. While that’s obviously true from standard geometry, it is also true when you work with arithmetic modulo a prime. In fact, it works using arithmetic over any field.

 Implementing these hash functions is easier than shooting fish in a barrel.

 import random
 
 def draw(p, m):
 a = random.randint(1, p-1)
 b = random.randint(0, p-1)
 
 return lambda x: ((a*x + b) % p) % m
 

 To encapsulate the process a little bit we implemented a UniversalHashFamily class which computes a random probable prime to use as the modulus and stores m. The interested reader can see the Github repository for more.

 If we try to run this and feed in a large range of inputs, we can see how the outputs are distributed. In this example m is a hundred thousand and n is a hundred (it’s not two terabytes, but give me some slack it’s a demo and I’ve only got my desktop!). So the expected bin size for any 2-universal family is just about 1,000.

 >>> m = 100000
 >>> n = 100
 >>> H = UniversalHashFamily(numBins=n, primeBounds=[n, 2*n])
 >>> results = []
 >>> for simulation in range(100):
 ... bins = [0] * n
 ... h = H.draw()
 ... for i in range(m):
 ... bins[h(i)] += 1
 ... results.append(max(bins))
 ...
 >>> max(bins) # a single run
 1228
 >>> min(bins)
 613
 >>> max(results) # the max bin size over all runs
 1228
 >>> min(results)
 1227
 

 Indeed, the max is very close to the expected value.

 But this example is misleading, because the point of this was that some adversary would try to screw us over by picking a worst-case input. If the adversary knew exactly which h was chosen (which it doesn’t) then the worst case input would be the set of all inputs that have the given hash output value. Let’s see it happen live.

 >>> h = H.draw()
 >>> badInputs = [i for i in range(m) if h(i) == 9]
 >>>; len(badInputs)
 1227
 >>> testInputs(n,m,badInputs,hashFunction=h)
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1227, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
 

 The expected size of a bin is 12, but as expected this is 100 times worse (linearly worse in n). But if we instead pick a random h after the bad inputs are chosen, the result is much better.

 >>> testInputs(n,m,badInputs) # randomly picks a hash
 [19, 20, 20, 19, 18, 18, 17, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 19, 18, 17, 17, 16, 16, 16, 16, 17, 18, 18, 19, 20, 20, 19, 18, 17, 17, 16, 16, 16, 16, 8, 8, 9, 9, 10, 10, 10, 10, 9, 9, 8, 8, 8, 8, 8, 8, 9, 9, 10, 10, 10, 10, 9, 9, 8, 8, 8, 8, 8, 8, 9, 9, 10, 10, 10, 10, 9, 8, 8, 8, 8, 8, 8, 8, 9, 9, 10, 10, 10, 10, 9, 8, 8, 8, 8, 8, 8, 8, 9, 9, 10]
 

 However, if you re-ran this test many times, you’d eventually get unlucky and draw the hash function for which this actually is the worst input, and get a single huge bin. Other times you can get a bad hash in which two or three bins have all the inputs.

 An interesting question is, what is really the worst-case input for this algorithm? I suspect it’s characterized by some choice of hash output values, taking all inputs for the chosen outputs. If this is the case, then there’s a tradeoff between the number of inputs you pick and how egregious the worst bin is. As an exercise to the reader, empirically estimate this tradeoff and find the best worst-case input for the adversary. Also, for your choice of parameters, estimate by simulation the probability that the max bin is three times larger than the expected value.

 Now that we’ve played around with the basic hashing algorithm and made a family of 2-universal hashes, let’s see the power of two choices. Recall, this algorithm picks two random hash functions and sends an input to the bin with the smallest size. This obviously generalizes to k choices, although the theoretical guarantee only improves by a constant factor, so let’s implement the more generic version.

 class ChoiceHashFamily(object):
 def __init__(self, hashFamily, queryBinSize, numChoices=2):
 self.queryBinSize = queryBinSize
 self.hashFamily = hashFamily
 self.numChoices = numChoices
 
 def draw(self):
 hashes = [self.hashFamily.draw()
 for _ in range(self.numChoices)]
 
 def h(x):
 indices = [h(x) for h in hashes]
 counts = [self.queryBinSize(i) for i in indices]
 count, index = min([(c,i) for (c,i) in zip(counts,indices)])
 return index
 
 return h
 

 And if we test this with the bad inputs (as used previously, all the inputs that hash to 9), as a typical output we get

 >>> bins
 [15, 16, 15, 15, 16, 14, 16, 14, 16, 15, 16, 15, 15, 15, 17, 14, 16, 14, 16, 16, 15, 16, 15, 16, 15, 15, 17, 15, 16, 15, 15, 15, 15, 16, 15, 14, 16, 14, 16, 15, 15, 15, 14, 16, 15, 15, 15, 14, 17, 14, 15, 15, 14, 16, 13, 15, 14, 15, 15, 15, 14, 15, 13, 16, 14, 16, 15, 15, 15, 16, 15, 15, 13, 16, 14, 15, 15, 16, 14, 15, 15, 15, 11, 13, 11, 12, 13, 14, 13, 11, 11, 12, 14, 14, 13, 10, 16, 12, 14, 10]
 

 And a typical list of bin maxima is

 >>> results
 [16, 16, 16, 18, 17, 365, 18, 16, 16, 365, 18, 17, 17, 17, 17, 16, 16, 17, 18, 16, 17, 18, 17, 16, 17, 17, 18, 16, 18, 17, 17, 17, 17, 18, 18, 17, 17, 16, 17, 365, 17, 18, 16, 16, 18, 17, 16, 18, 365, 16, 17, 17, 16, 16, 18, 17, 17, 17, 17, 17, 18, 16, 18, 16, 16, 18, 17, 17, 365, 16, 17, 17, 17, 17, 16, 17, 16, 17, 16, 16, 17, 17, 16, 365, 18, 16, 17, 17, 17, 17, 17, 18, 17, 17, 16, 18, 18, 17, 17, 17]
 

 Those big bumps are the times when we picked an unlucky hash function, which is scarily large, although this bad event would be proportionally less likely as you scale up. But in the good case the load is clearly more even than the previous example, and the max load would get linearly smaller as you pick between a larger set of randomly chosen hashes (obviously).

 Coupling this with the technique of switching hash functions when you start to observe a large deviation, and you have yourself an elegant solution.

 In addition to load balancing, hashing has a ton of applications. Remember, the main key that you may want to use hashing is when you have an algorithm that works well when the input data is random. This comes up in streaming and sublinear algorithms, in data structure design and analysis, and many other places. We’ll be covering those applications in future posts on this blog.

 Until then!


 ← Previous: The Inequality Next: Hashing to Estimate the Size of a Stream →
This article was ported from my old Wordpress blog here, If you see any issues with the rendering or layout, please send me an email.  Here’s a bit of folklore I often hear (and retell) that’s somewhere between a joke and deep wisdom: if you’re doing a software interview that involves some algorithms problem that seems hard, your best bet is to use hash tables. More succinctly put: Google loves hash tables. As someone with a passion for math and theoretical CS, it’s kind of silly and reductionist. But if you actually work with terabytes of data that can’t fit on a single machine, it also makes sense. But to understand why hash tables are so applicable, you should have at least a fuzzy understanding of the math that goes into it, which is surprisingly unrelated to the actual act of hashing. Instead it’s the guarantees that a “random enough” hash provides that makes it so useful. The basic intuition is that if you have an algorithm that works well assuming the input data is completely random, then you can probably get a good guarantee by preprocessing the input by hashing. In this post I’ll explain the details, and show the application to an important problem that one often faces in dealing with huge amounts of data: how to allocate resources efficiently (load balancing). As usual, all of the code used in the making of this post is available on Github. Next week, I’ll follow this post up with another application of hashing to estimating the number of distinct items in a set that’s too large to store in memory. Families of Hash Functions   To emphasize which specific properties of hash functions are important for a given application, we start by introducing an abstraction: a hash function is just some computable function that accepts strings as input and produces numbers between 1 and as output. We call the set of allowed inputs (for “Universe”). A family of hash functions is just a set of possible hash functions to choose from. We’ll use a scripty for our family, and so every hash function in is a function . You can use a single hash function to maintain an unordered set of objects in a computer. The reason this is a problem that needs solving is because if you were to store items sequentially in a list, and if you want to determine if a specific item is already in the list, you need to potentially check every item in the list (or do something fancier). In any event, without hashing you have to spend some non-negligible amount of time searching. With hashing, you can choose the location of an element based on the value of its hash . If you pick your hash function well, then you’ll have very few collisions and can deal with them efficiently. The relevant section on Wikipedia has more about the various techniques to deal with collisions in hash tables specifically, but we want to move beyond that in this post. Here we have a family of random hash functions. So what’s the use of having many hash functions? You can pick a hash randomly from a “good” family of hash functions. While this doesn’t seem so magical, it has the informal property that it makes arbitrary data “random enough,” so that an algorithm which you designed to work with truly random data will also work with the hashes of arbitrary data. Moreover, even if an adversary knows and knows that you’re picking a hash function at random, there’s no way for the adversary to manufacture problems by feeding bad data. With overwhelming probability the worst-case scenario will not occur. Our first example of this is in load-balancing. Load balancing and 2-uniformity   You can imagine load balancing in two ways, concretely and mathematically. In the concrete version you have a public-facing server that accepts requests from users, and forwards them to a back-end server which processes them and sends a response to the user. When you have a billion users and a million servers, you want to forward the requests in such a way that no server gets too many requests, or else the users will experience delays. Moreover, you’re worried that the League of Tanzanian Hackers is trying to take down your website by sending you requests in a carefully chosen order so as to screw up your load balancing algorithm. The mathematical version of this problem usually goes with the metaphor of balls and bins. You have some collection of balls and bins in which to put the balls, and you want to put the balls into the bins. But there’s a twist: an adversary is throwing balls at you, and you have to put them into the bins before the next ball comes, so you don’t have time to remember (or count) how many balls are in each bin already. You only have time to do a small bit of mental arithmetic, sending ball to bin where is some simple function. Moreover, whatever rule you pick for distributing the balls in the bins, the adversary knows it and will throw balls at you in the worst order possible.   A young man applying his knowledge of balls and bins. That’s totally what he’s doing.   There is one obvious approach: why not just pick a uniformly random bin for each ball? The problem here is that we need the choice to be persistent. That is, if the adversary throws the same ball at us a second time, we need to put it in the same bin as the first time, and it doesn’t count toward the overall load. This is where the ball/bin metaphor breaks down. In the request/server picture, there is data specific to each user stored on the back-end server between requests (a session), and you need to make sure that data is not lost for some reasonable period of time. And if we were to save a uniform random choice after each request, we’d need to store a number for every request, which is too much. In short, we need the mapping to be persistent, but we also want it to be “like random” in effect. So what do you do? The idea is to take a “good” family of hash functions , pick one uniformly at random for the whole game, and when you get a request/ball send it to server/bin . Note that in this case, the adversary knows your universal family ahead of time, and it knows your algorithm of committing to some single randomly chosen , but the adversary does not know which particular you chose. The property of a family of hash functions that makes this strategy work is called 2-universality.  Definition: A family of functions from some universe . is called 2-universal if, for every two distinct , the probability over the random choice of a hash function from that is at most . In notation, I’ll give an example of such a family shortly, but let’s apply this to our load balancing problem. Our load-balancing algorithm would fail if, with even some modest probability, there is some server that receives many more than its fair share () of the requests. If is 2-universal, then we can compute an upper bound on the expected load of a given server, say server 1. Specifically, pick any element which hashes to 1 under our randomly chosen . Then we can compute an upper bound on the expected number of other elements that hash to 1. In this computation we’ll only use the fact that expectation splits over sums, and the definition of 2-universal. Call the random variable which is zero when and one when , and call . In words, simply represents the number of inputs that hash to 1. Then   So in expectation we can expect server 1 gets its fair share of requests. And clearly this doesn’t depend on the output hash being 1; it works for any server. There are two obvious questions.  How do we measure the risk that, despite the expectation we computed above, some server is overloaded? If it seems like (1) is on track to happen, what can you do?  For 1 we’re asking to compute, for a given deviation , the probability that . This makes more sense if we jump to multiplicative factors, since it’s usually okay for a server to bear twice or three times its usual load, but not like times more than it’s usual load. (Industry experts, please correct me if I’m wrong! I’m far from an expert on the practical details of load balancing.) So we want to know what is the probability that for some small number , and we want this to get small quickly as grows. This is where the Chebyshev inequality becomes useful. For those who don’t want to click the link, for our sitauation Chebyshev’s inequality is the statement that, for any random variable  So all we need to do is compute the variance of the load of a server. It’s a bit of a hairy calculation to write down, but rest assured it doesn’t use anything fancier than the linearity of expectation and 2-universality. Let’s dive in. We start by writing the definition of variance as an expectation, and then we split up into its parts, expand the product and group the parts. The easy part is , it’s just , and the hard part is . So let’s compute that   In order to continue (and get a reasonable bound) we need an additional property of our hash family which is not immediately spelled out by 2-universality. Specifically, we need that for every and , . In other words, each hash function should evenly split the inputs across servers. The reason this helps is because we can split into . Using 2-universality to bound the left term, this quantity is at most , and since there are total terms in the double sum above, the whole thing is at most . Note that in our big-O analysis we’re assuming is much bigger than . Sweeping some of the details inside the big-O, this means that our variance is , and so our bound on the deviation of from its expectation by a multiplicative factor of is at most . Now we computed a bound on the probability that a single server is not overloaded, but if we want to extend that to the worst-case server, the typical probability technique is to take the union bound over all servers. This means we just add up all the individual bounds and ignore how they relate. So the probability that some server has a load more than a multiplicative factor of is bounded from above . This is only less than one when , so all we can say with this analysis is that (with some small constant probability) no server will have a load worse than times more than the expected load. So we have this analysis that seems not so good. If we have a million servers then the worst load on one server could potentially be a thousand times higher than the expected load. This doesn’t scale, and the problem could be in any (or all) of three places:  Our analysis is weak, and we should use tighter bounds because the true max load is actually much smaller. Our hash families don’t have strong enough properties, and we should beef those up to get tighter bounds. The whole algorithm sucks and needs to be improved.  It turns out all three are true. One heuristic solution is easy and avoids all math. Have some second server (which does not process requests) count hash collisions. When some server exceeds a factor of more than the expected load, send a message to the load balancer to randomly pick a new hash function from and for any requests that don’t have existing sessions (this is included in the request data), use the new hash function. Once the old sessions expire, switch any new incoming requests from those IPs over to the new hash function. But there are much better solutions out there. Unfortunately their analyses are too long for a blog post (they fill multiple research papers). Fortunately their descriptions and guarantees are easy to describe, and they’re easy to program. The basic idea goes by the name “the power of two choices,” which we explored on this blog in a completely different context of random graphs. In more detail, the idea is that you start by picking two random hash functions , and when you get a new request, you compute both hashes, inspect the load of the two servers indexed by those hashes, and send the request to the server with the smaller load. This has the disadvantage of requiring bidirectional talk between the load balancer and the server, rather than obliviously forwarding requests. But the advantage is an exponential decrease in the worst-case maximum load. In particular, the following theorem holds for the case where the hashes are fully random.  Theorem: Suppose one places balls into bins in order according to the following procedure: for each ball pick two uniformly random and independent integers , and place the ball into the bin with the smallest current size. If there are ties pick the bin with the smaller index. Then with high probability the largest bin has no more than balls. This theorem appears to have been proved in a few different forms, with the best analysis being by Berenbrink et al. You can improve the constant on the by computing more than 2 hashes. How does this relate to a good family of hash functions, which is not quite fully random? Let’s explore the answer by implementing the algorithm in python. An example of universal hash functions, and the load balancing algorithm   In order to implement the load balancer, we need to have some good hash functions under our belt. We’ll go with the simplest example of a hash function that’s easy to prove nice properties for. Specifically each hash in our family just performs some arithmetic modulo a random prime.  Definition: Pick any prime , and for any and define . Let . This family of hash functions is 2-universal.  Theorem: For every ,  Proof. To say that is to say that for some integer . I.e., the two remainders of and are equivalent mod . The ’s cancel and we can solve for  Since , there are possible choices for . Moreover, there is no point to pick bigger than since we’re working modulo . So there are possible values for the right hand side of the above equation. So if we chose them uniformly at random, (remember, is fixed ahead of time, so the only choice is ), then there is a out of chance that the equality holds, which is at most . (To be exact you should account for taking a floor of when does not evenly divide , but it only decreases the overall probability.) If and were equal then this would be even more trivial: it’s just the fact that there is a unique line passing through any two distinct points. While that’s obviously true from standard geometry, it is also true when you work with arithmetic modulo a prime. In fact, it works using arithmetic over any field. Implementing these hash functions is easier than shooting fish in a barrel.       To encapsulate the process a little bit we implemented a UniversalHashFamily class which computes a random probable prime to use as the modulus and stores . The interested reader can see the Github repository for more. If we try to run this and feed in a large range of inputs, we can see how the outputs are distributed. In this example is a hundred thousand and is a hundred (it’s not two terabytes, but give me some slack it’s a demo and I’ve only got my desktop!). So the expected bin size for any 2-universal family is just about 1,000.       Indeed, the max is very close to the expected value. But this example is misleading, because the point of this was that some adversary would try to screw us over by picking a worst-case input. If the adversary knew exactly which was chosen (which it doesn’t) then the worst case input would be the set of all inputs that have the given hash output value. Let’s see it happen live.       The expected size of a bin is 12, but as expected this is 100 times worse (linearly worse in ). But if we instead pick a random after the bad inputs are chosen, the result is much better.       However, if you re-ran this test many times, you’d eventually get unlucky and draw the hash function for which this actually is the worst input, and get a single huge bin. Other times you can get a bad hash in which two or three bins have all the inputs. An interesting question is, what is really the worst-case input for this algorithm? I suspect it’s characterized by some choice of hash output values, taking all inputs for the chosen outputs. If this is the case, then there’s a tradeoff between the number of inputs you pick and how egregious the worst bin is. As an exercise to the reader, empirically estimate this tradeoff and find the best worst-case input for the adversary. Also, for your choice of parameters, estimate by simulation the probability that the max bin is three times larger than the expected value. Now that we’ve played around with the basic hashing algorithm and made a family of 2-universal hashes, let’s see the power of two choices. Recall, this algorithm picks two random hash functions and sends an input to the bin with the smallest size. This obviously generalizes to choices, although the theoretical guarantee only improves by a constant factor, so let’s implement the more generic version.       And if we test this with the bad inputs (as used previously, all the inputs that hash to 9), as a typical output we get       And a typical list of bin maxima is       Those big bumps are the times when we picked an unlucky hash function, which is scarily large, although this bad event would be proportionally less likely as you scale up. But in the good case the load is clearly more even than the previous example, and the max load would get linearly smaller as you pick between a larger set of randomly chosen hashes (obviously). Coupling this with the technique of switching hash functions when you start to observe a large deviation, and you have yourself an elegant solution. In addition to load balancing, hashing has a ton of applications. Remember, the main key that you may want to use hashing is when you have an algorithm that works well when the input data is random. This comes up in streaming and sublinear algorithms, in data structure design and analysis, and many other places. We’ll be covering those applications in future posts on this blog. Until then!
Load Balancing and the Power of Hashing
https://jeremykun.com/2015/12/28/load-balancing-and-the-power-of-hashing/?utm_content=buffer51931&utm_medium=social&utm_source=twitter.com&utm_campaign=buffer
http://benwhitmore.altervista.org/simhash-and-solving-the-hamming-distance-problem-explained/?doing_wp_cron=1644764641.0774369239807128906250
Simhash and solving the hamming distance problem: explained
2019-08-06
Ben Whitmore
<div><article>
	 
	<div>
	<p>Simhashes are a clever means of rapidly finding near-identical documents (or other items) within a large corpus, without having to individually compare every document to every other document. Using simhashes for any sizable corpus involves two parts: generating the simhash itself, and <em>solving the Hamming distance problem</em>. Neither is much use without the other. Unlike minhashes, the simhash approach doesn’t really allow full <em>similarity detection</em>, because the range of similarity it is sensitive to is so small. It’s better described as <em>near-duplicate detection</em>. Google have patented simhash (though not the Hamming distance solution, as far as I know).</p>
<p>As well as its other limitations simhash is substantially more complex than minhash and harder to tune. Its real benefit is that it performs way faster than minhash, even on enormous corpuses, and typically requires less storage.</p>
<h2>Generating the simhash</h2>
<p>A simhash is a single sequence of bits (usually 64 bits) generated from a set of features in such a way that changing a small fraction of those features will cause the resulting hash to change only a small fraction of its bits; whereas changing all features will cause the resulting hash to look completely different (roughly half its bits will change).</p>
<p>As with any similarity detection scheme, its success depends on choosing sensible features. Let’s say you’re comparing documents: a typical feature to choose might be <a href="https://en.wikipedia.org/wiki/W-shingling">shingles</a> of words, with whitespacing and case normalized. You might add in other features, such as document title, text styled as headings, and so on.</p>
<p>Each feature must be hashed using a cheap but good standard (non-cryptographic) hash such as <a href="https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function#FNV-1a_hash">FNV-1a</a>, with the same bit-length as your intended simhash.</p>
<p>To combine the many feature hashes into a single simhash, you calculate a kind of bitwise average of them all. It’s very simple. Take the first bit of every feature hash and average them. You get some value between 0 and 1. Round that value to 0 if it’s less than 0.5, and otherwise to 1. That gives you the first bit of your simhash. Do the same for the second bit of every feature hash, to yield the second bit of your simhash. And so on.</p>
<figure><figcaption>Feature hashes are combined into a bitwise average, then those averages are rounded to yield the bits of the simhash.</figcaption></figure>
<p>You can see that changing just one feature hash out of thousands may not change many (or any) bits in the simhash, whereas changing a lot of feature hashes will have a larger effect.</p>
<p>Comparing two documents for (estimated) similarity is now as simple as determining the Hamming distance between the two simhashes, which can be calculated <a href="https://en.wikipedia.org/wiki/Hamming_weight#Efficient_implementation">very efficiently</a>. Unfortunately, in most situations you don’t need to compare one single document to another single document; you need to compare every document to every other one. Even with such an efficient calculation of hamming distance, to find all near-duplicates in a corpus of 10 million documents would require 10M×(10M-1)/2 = nearly 50 trillion comparisons, which is completely unworkable. This is why simhashing isn’t much use without “solving the hamming distance problem”, described below. The solution to that problem only works for quite small hamming distances: typically 2 to 7 bits difference, depending on your storage capacity, speed requirements and corpus size.</p>
<p>For this reason, a lot of careful tuning goes into trying to make the simhashes sensitive to those features we consider most important and less sensitive to others. This involves choosing suitable features for hashing and suitable methods of normalizing features (such as lowercasing text and simplifying whitespacing). It also involves giving higher or lower <em>weights</em> to certain features: we thus calculate each bit of the simhash as a (rounded) <a href="https://en.wikipedia.org/wiki/Weighted_arithmetic_mean">weighted average</a>.</p>
<p>An example of a kind of feature you might want to exclude is advertising text in a webpage. There are some simple tricks for reducing the influence of advertising text, such as only taking shingles that include at least one <a href="https://en.wikipedia.org/wiki/Stop_words">stopword</a> (since advertisements typically contain few stopwords). But you may have to do more complex feature detection.</p>
<p>The method of calculating a simhash is described in slightly different terms in Google’s patents. As they describe it, you keep a tally for every bit, which starts at zero. For each bit of each feature hash, if it is 1, <em>add</em> that feature’s weight to the corresponding tally; or if it is zero <em>subtract</em> its weight from the tally. From the final tallies, set your simhash bit to 1 where the corresponding tally is &gt;0, otherwise set it to 0. This is illustrated below:</p>
<figure><figcaption>In this example features are extracted and turned into weighted hashes; then the weights for each bit of each feature are added (up-arrow) or subtracted (down-arrow) in each bit’s tally. The bits of the simhash are determined by the sign of each of the tally totals. The feature hashes are coloured so you can see how each contributes to the tallies.</figcaption></figure>
<p>It’s a little more cumbersome to describe the algorithm this way, but it should be clear that it is exactly equivalent to a bitwise rounded weighted average.</p>
<p>I recommend you keep weights for particular types of feature constant. E.g., don’t weight shingles more highly near the beginning of the document and gradually less and less toward the end. Otherwise relatively small changes in position of text, such as inserting an extra paragraph early in the document, can have a substantial impact on the simhash.</p>
<p>There’s probably not a lot of choice in the bit-length of your simhashes. I recommend 64 bits. 128 bits would be overkill for almost any purpose, and 32 bits is insufficient for most purposes. Remember that 32 bits only stores a little over 4 billion values, which may sound like a lot, but is ripe for collisions. Let’s say your hash is 32 bits long and k is 4. For any given fingerprint there are 41,449 bit-patterns that are within k bits Hamming distance of it, and any document that happens to have one of those fingerprints as a result of a hash collision will be detected as similar. With a corpus of 100,000 documents you’d already be getting frequent collisions.</p>
<h2>A word on images</h2>
<p>Simhash, minhash and the like can be used for detecting similar images, <em>if</em> you choose sensible features to generate your feature hashes from. The features should be derived in such a way that similar images are likely to contain many <em>identical</em> features. This is far from straightforward. Depending on what you want to consider ‘similar’, the features may need to be robust to changes in scale, orientation, colour balance, blur/sharpness, etc.</p>
<p>You may want to treat images embedded in a document as features of that document, and generate simple binary hashes of them (as in the example above). If you do so, be aware that any change, visible or otherwise, will result in a different feature hash.</p>
<p>Now comes the really clever bit, that relieves us of having to individually compare every simhash with every other simhash in order to find all duplicates in the corpus. This is what saves us from performing 50 trillion Hamming distance calculations to deduplicate our corpus of 10 million documents! The explanation in Google’s <a href="http://www2007.org/papers/paper215.pdf">paper</a> is difficult to follow, and I couldn’t find a simpler explanation, so I’m creating one here. I’ll stick to the original paper’s terminology and notation, to avoid confusion.</p>
<p>Let’s say we’re a Google web crawler, and we find a new document with fingerprint (simhash) F. It so happens that we’ve previously encountered another document with a very similar fingerprint G that differs by at most k=3 bits.</p>
<figure><figcaption>Fingerprint F: generated from our incoming document</figcaption></figure>
<figure><figcaption>Fingerprint G: from a previously-encountered document</figcaption></figure>
<figure><figcaption>Only 3 bits differ between the two.</figcaption></figure>
<p>If we divide the 64 bits into 6 blocks, we know that the differing bits can occur in no more than 3 of those blocks:</p>
<p></p>
<p>We can then permute these 6 blocks so that the three blocks containing differing bits all move into the low-order bits:</p>
<p></p>
<p>The permuted F we’ll call F′, and the permuted G we’ll call G′. Notice that in the first 3 blocks (totalling 32 bits), F′ and G′ are identical.</p>
<p>Now, we have kept a table of the permuted hashes of all the documents we’ve previously encountered. All the hashes in that table have had exactly the same permutation applied, and the table is <em>sorted</em>. That means that all the permuted hashes that share their first 32 bits with our permuted fingerprint F′ are in a single contiguous section of the table, and we can find them rapidly using binary search, or even more efficiently, interpolation search.</p>
<p>Once we’ve found permuted hashes that share the first 32 bits, we still need to compare the low order bits to determine total Hamming distance. Then we’ve found our similar documents.</p>
<p>“Wait!”, I hear you say. The permutation we’ve chosen may work for this example, but what about all the other fingerprints whose 1, 2 or 3 differing bits fall in different blocks? Well, that’s why we actually store 20 such tables, each with a different permutation, so that in each table a different combination of 3 blocks is pushed into the low bits. COMB(6,3) = 20. When we look for similar fingerprints to F, we’ll have to generate 20 different permutations of it and search in each of the 20 tables.</p>
<figure><figcaption>Permutation schemes for 20 different tables to push different blocks into the low-end bits</figcaption></figure>
<p>But let’s return to F′ and G′ and this particular permuted table. Interpolation search has yielded a set of candidates that we have to calculate Hamming distance on. That’s a fairly cheap operation, but still could be time-consuming if there are a lot of candidates. So how many candidates should we expect, on average?</p>
<p>Well, Google indexes around 8 billion documents, which is roughly 2<sup>34</sup>. So our table contains around 2<sup>34</sup> fingerprints. On average there will be just one document that shares the highest 34 bits with F′, or 4 that share the highest 32 bits (since 2<sup>34-32</sup> = 4). So on average, we’ll only have to calculate hamming distance for 4 candidates (within this table). Nice!</p>
<p>There’s another way to explain this: Imagine we have 2<sup>34</sup> truly random fingerprints, in sorted order. If we take just the first 34 bits of these fingerprints (shaded green below), they will amount to ‘almost a counter’, since most of the possible numbers will be represented and only a minority of possible numbers will be repeated. If we take just the least significant 30 bits, though, they will look “almost random”.</p>
<figure><figcaption>A small section of the table. The upper 34 bits in green are ‘almost a counter’. The lower 30 bits appear virtually random. And there’s G′ with its differing bits highlighted.</figcaption></figure>
<p>But we’re only matching the first 32 bits, so we find on average 4 candidates per query.</p>
<p></p>
<p>Because 64 isn’t evenly divisible by 6, our blocks are 11, 11, 11, 11, 10 and 10 bits wide. That means our different tables will need to be searched with different numbers of high-end bits: 31, 32 or 33 depending on the permutation, yielding 8, 4 or 2 candidates on average.</p>
<p>By performing this same cheap search on each of the 20 tables we can be certain we have found every fingerprint that differs by at most k=3 bits.</p>
<h3>Storing the tables</h3>
<p>For fast response, tables should be held in main memory. Each of the permuted tables should store <em>only</em> permuted hashes, and a separate table should contain mappings from the unpermuted hashes back to document IDs.</p>
<p>The most compact storage for the hash tables is as a sorted list (and Google’s paper describes how to further compress the table). If you want to insert new entries as you go then you’ll need trees (quite a bit more storage required), or else you could keep most entries in sorted lists and new entries in trees and check both, and periodically merge the trees back into the sorted lists.</p>
<p>If you don’t have to detect similarities as soon as new documents arrive, there are nice efficiencies to be gained. Not only can you store the tables as more compact sorted lists, you can also find all similarities in a single pass through all tables, by just finding every group of hashes permuted hashes that shares the first d bits, and checking their Hamming distances.</p>
<p>In Google’s <a href="http://www2007.org/papers/paper215.pdf">paper</a> they recommend a means of compacting a sorted list still further, exploiting the fact that many of the high-end bits don’t change much from one entry to the next. I’ve never bothered with this, but if you’re really struggling with storage, bear it in mind.</p>
<h3>Other configurations</h3>
<p>Aside from the 6-block configuration discussed above, there are other configurations that give different memory/processing trade-offs with k=3. For instance, 4 blocks (of 16 bits each) requires only 4 permuted tables (since COMB(4,3) = 4).</p>
<figure><figcaption>Four blocks of 16 bits each, with k = 3</figcaption></figure>
<p>Given there are only 16 bits we are doing the table search on, we can expect on average 2<sup>34-16</sup> = 262,144 results per query for each table, or about a million hamming checks per query overall.</p>
<p>In the example above, we match on 16 bits, leaving 48 non-match bits. We could further subdivide each table, by splitting the 48 non-match bits into 4 blocks of 12 bits each and permuting them in turn, for a total of 16 tables:</p>
<p></p>
<p>Now we can match on the first 28 bits, using 16 tables and getting on average 2<sup>34-28</sup> = 64 results per query.</p>
<p>There are several such table variants described in Google’s paper, each offering a different trade-off between number of tables required, and average number of candidate matches per query.</p>
<p>Many applications won’t need to index 2<sup>34</sup> documents, and could increase k a little. For instance, let’s say you only expect to index around 2<sup>23</sup> (~8 million) documents. You could readily increase the possible Hamming distance up to k = 6, by dividing the hash into 8 blocks (28 tables). On average you’d be getting 128 candidates per query for each table, meaning you’d have to perform about 3,500 hamming distance checks in total per query.</p>
<figure><figcaption>An example permutation scheme to detect hamming distances of up to 6 bits, which would still be reasonably efficient for a corpus of 8 million documents.</figcaption></figure>
<p>You will need to find a table arrangement that works best for you. Decide on the bit-length of your simhashes; test the simhashes you produce from your documents to determine how many bits of Hamming distance you need to allow (k); and determine how large your corpus is expected to grow and thus how many bits would be “almost a counter”. Then you can figure out a suitable permutation scheme that balances storage size against processing time.</p>
<p>If you find that you need to detect more bits difference than this approach can accommodate, you are probably looking for full <em>similarity detection</em> rather than <em>near-duplicate detection</em>, and should investigate algorithms such as minhash.</p>
	</div> 
	</article>||||I|||| The Briar

 From the mind of Ben Whitmore

 * Home

 Simhash and solving the hamming distance problem: explained

 Posted on 6 August 20196 August 2019 by Ben Whitmore
 Facebook

 Simhashes are a clever means of rapidly finding near-identical documents (or other items) within a large corpus, without having to individually compare every document to every other document. Using simhashes for any sizable corpus involves two parts: generating the simhash itself, and solving the Hamming distance problem. Neither is much use without the other. Unlike minhashes, the simhash approach doesn’t really allow full similarity detection, because the range of similarity it is sensitive to is so small. It’s better described as near-duplicate detection. Google have patented simhash (though not the Hamming distance solution, as far as I know).

 As well as its other limitations simhash is substantially more complex than minhash and harder to tune. Its real benefit is that it performs way faster than minhash, even on enormous corpuses, and typically requires less storage.

 Generating the simhash

 A simhash is a single sequence of bits (usually 64 bits) generated from a set of features in such a way that changing a small fraction of those features will cause the resulting hash to change only a small fraction of its bits; whereas changing all features will cause the resulting hash to look completely different (roughly half its bits will change).

 As with any similarity detection scheme, its success depends on choosing sensible features. Let’s say you’re comparing documents: a typical feature to choose might be shingles of words, with whitespacing and case normalized. You might add in other features, such as document title, text styled as headings, and so on.

 Each feature must be hashed using a cheap but good standard (non-cryptographic) hash such as FNV-1a, with the same bit-length as your intended simhash.

 To combine the many feature hashes into a single simhash, you calculate a kind of bitwise average of them all. It’s very simple. Take the first bit of every feature hash and average them. You get some value between 0 and 1. Round that value to 0 if it’s less than 0.5, and otherwise to 1. That gives you the first bit of your simhash. Do the same for the second bit of every feature hash, to yield the second bit of your simhash. And so on.

 Feature hashes are combined into a bitwise average, then those averages are rounded to yield the bits of the simhash.

 You can see that changing just one feature hash out of thousands may not change many (or any) bits in the simhash, whereas changing a lot of feature hashes will have a larger effect.

 Comparing two documents for (estimated) similarity is now as simple as determining the Hamming distance between the two simhashes, which can be calculated very efficiently. Unfortunately, in most situations you don’t need to compare one single document to another single document; you need to compare every document to every other one. Even with such an efficient calculation of hamming distance, to find all near-duplicates in a corpus of 10 million documents would require 10M×(10M-1)/2 = nearly 50 trillion comparisons, which is completely unworkable. This is why simhashing isn’t much use without “solving the hamming distance problem”, described below. The solution to that problem only works for quite small hamming distances: typically 2 to 7 bits difference, depending on your storage capacity, speed requirements and corpus size.

 For this reason, a lot of careful tuning goes into trying to make the simhashes sensitive to those features we consider most important and less sensitive to others. This involves choosing suitable features for hashing and suitable methods of normalizing features (such as lowercasing text and simplifying whitespacing). It also involves giving higher or lower weights to certain features: we thus calculate each bit of the simhash as a (rounded) weighted average.

 An example of a kind of feature you might want to exclude is advertising text in a webpage. There are some simple tricks for reducing the influence of advertising text, such as only taking shingles that include at least one stopword (since advertisements typically contain few stopwords). But you may have to do more complex feature detection.

 The method of calculating a simhash is described in slightly different terms in Google’s patents. As they describe it, you keep a tally for every bit, which starts at zero. For each bit of each feature hash, if it is 1, add that feature’s weight to the corresponding tally; or if it is zero subtract its weight from the tally. From the final tallies, set your simhash bit to 1 where the corresponding tally is >0, otherwise set it to 0. This is illustrated below:

 In this example features are extracted and turned into weighted hashes; then the weights for each bit of each feature are added (up-arrow) or subtracted (down-arrow) in each bit’s tally. The bits of the simhash are determined by the sign of each of the tally totals. The feature hashes are coloured so you can see how each contributes to the tallies.

 It’s a little more cumbersome to describe the algorithm this way, but it should be clear that it is exactly equivalent to a bitwise rounded weighted average.

 I recommend you keep weights for particular types of feature constant. E.g., don’t weight shingles more highly near the beginning of the document and gradually less and less toward the end. Otherwise relatively small changes in position of text, such as inserting an extra paragraph early in the document, can have a substantial impact on the simhash.

 There’s probably not a lot of choice in the bit-length of your simhashes. I recommend 64 bits. 128 bits would be overkill for almost any purpose, and 32 bits is insufficient for most purposes. Remember that 32 bits only stores a little over 4 billion values, which may sound like a lot, but is ripe for collisions. Let’s say your hash is 32 bits long and k is 4. For any given fingerprint there are 41,449 bit-patterns that are within k bits Hamming distance of it, and any document that happens to have one of those fingerprints as a result of a hash collision will be detected as similar. With a corpus of 100,000 documents you’d already be getting frequent collisions.

 A word on images

 Simhash, minhash and the like can be used for detecting similar images, if you choose sensible features to generate your feature hashes from. The features should be derived in such a way that similar images are likely to contain many identical features. This is far from straightforward. Depending on what you want to consider ‘similar’, the features may need to be robust to changes in scale, orientation, colour balance, blur/sharpness, etc.

 You may want to treat images embedded in a document as features of that document, and generate simple binary hashes of them (as in the example above). If you do so, be aware that any change, visible or otherwise, will result in a different feature hash.

 Solving the Hamming distance problem

 Now comes the really clever bit, that relieves us of having to individually compare every simhash with every other simhash in order to find all duplicates in the corpus. This is what saves us from performing 50 trillion Hamming distance calculations to deduplicate our corpus of 10 million documents! The explanation in Google’s paper is difficult to follow, and I couldn’t find a simpler explanation, so I’m creating one here. I’ll stick to the original paper’s terminology and notation, to avoid confusion.

 Let’s say we’re a Google web crawler, and we find a new document with fingerprint (simhash) F. It so happens that we’ve previously encountered another document with a very similar fingerprint G that differs by at most k=3 bits.

 Fingerprint F: generated from our incoming document

 Fingerprint G: from a previously-encountered document

 Only 3 bits differ between the two.

 If we divide the 64 bits into 6 blocks, we know that the differing bits can occur in no more than 3 of those blocks:

 We can then permute these 6 blocks so that the three blocks containing differing bits all move into the low-order bits:

 The permuted F we’ll call F′, and the permuted G we’ll call G′. Notice that in the first 3 blocks (totalling 32 bits), F′ and G′ are identical.

 Now, we have kept a table of the permuted hashes of all the documents we’ve previously encountered. All the hashes in that table have had exactly the same permutation applied, and the table is sorted. That means that all the permuted hashes that share their first 32 bits with our permuted fingerprint F′ are in a single contiguous section of the table, and we can find them rapidly using binary search, or even more efficiently, interpolation search.

 Once we’ve found permuted hashes that share the first 32 bits, we still need to compare the low order bits to determine total Hamming distance. Then we’ve found our similar documents.

 “Wait!”, I hear you say. The permutation we’ve chosen may work for this example, but what about all the other fingerprints whose 1, 2 or 3 differing bits fall in different blocks? Well, that’s why we actually store 20 such tables, each with a different permutation, so that in each table a different combination of 3 blocks is pushed into the low bits. COMB(6,3) = 20. When we look for similar fingerprints to F, we’ll have to generate 20 different permutations of it and search in each of the 20 tables.

 Permutation schemes for 20 different tables to push different blocks into the low-end bits

 But let’s return to F′ and G′ and this particular permuted table. Interpolation search has yielded a set of candidates that we have to calculate Hamming distance on. That’s a fairly cheap operation, but still could be time-consuming if there are a lot of candidates. So how many candidates should we expect, on average?

 Well, Google indexes around 8 billion documents, which is roughly 234. So our table contains around 234 fingerprints. On average there will be just one document that shares the highest 34 bits with F′, or 4 that share the highest 32 bits (since 234-32 = 4). So on average, we’ll only have to calculate hamming distance for 4 candidates (within this table). Nice!

 There’s another way to explain this: Imagine we have 234 truly random fingerprints, in sorted order. If we take just the first 34 bits of these fingerprints (shaded green below), they will amount to ‘almost a counter’, since most of the possible numbers will be represented and only a minority of possible numbers will be repeated. If we take just the least significant 30 bits, though, they will look “almost random”.

 A small section of the table. The upper 34 bits in green are ‘almost a counter’. The lower 30 bits appear virtually random. And there’s G′ with its differing bits highlighted.

 But we’re only matching the first 32 bits, so we find on average 4 candidates per query.

 Because 64 isn’t evenly divisible by 6, our blocks are 11, 11, 11, 11, 10 and 10 bits wide. That means our different tables will need to be searched with different numbers of high-end bits: 31, 32 or 33 depending on the permutation, yielding 8, 4 or 2 candidates on average.

 By performing this same cheap search on each of the 20 tables we can be certain we have found every fingerprint that differs by at most k=3 bits.

 Storing the tables

 For fast response, tables should be held in main memory. Each of the permuted tables should store only permuted hashes, and a separate table should contain mappings from the unpermuted hashes back to document IDs.

 The most compact storage for the hash tables is as a sorted list (and Google’s paper describes how to further compress the table). If you want to insert new entries as you go then you’ll need trees (quite a bit more storage required), or else you could keep most entries in sorted lists and new entries in trees and check both, and periodically merge the trees back into the sorted lists.

 If you don’t have to detect similarities as soon as new documents arrive, there are nice efficiencies to be gained. Not only can you store the tables as more compact sorted lists, you can also find all similarities in a single pass through all tables, by just finding every group of hashes permuted hashes that shares the first d bits, and checking their Hamming distances.

 In Google’s paper they recommend a means of compacting a sorted list still further, exploiting the fact that many of the high-end bits don’t change much from one entry to the next. I’ve never bothered with this, but if you’re really struggling with storage, bear it in mind.

 Other configurations

 Aside from the 6-block configuration discussed above, there are other configurations that give different memory/processing trade-offs with k=3. For instance, 4 blocks (of 16 bits each) requires only 4 permuted tables (since COMB(4,3) = 4).

 Four blocks of 16 bits each, with k = 3

 Given there are only 16 bits we are doing the table search on, we can expect on average 234-16 = 262,144 results per query for each table, or about a million hamming checks per query overall.

 In the example above, we match on 16 bits, leaving 48 non-match bits. We could further subdivide each table, by splitting the 48 non-match bits into 4 blocks of 12 bits each and permuting them in turn, for a total of 16 tables:

 Now we can match on the first 28 bits, using 16 tables and getting on average 234-28 = 64 results per query.

 There are several such table variants described in Google’s paper, each offering a different trade-off between number of tables required, and average number of candidate matches per query.

 Many applications won’t need to index 234 documents, and could increase k a little. For instance, let’s say you only expect to index around 223 (~8 million) documents. You could readily increase the possible Hamming distance up to k = 6, by dividing the hash into 8 blocks (28 tables). On average you’d be getting 128 candidates per query for each table, meaning you’d have to perform about 3,500 hamming distance checks in total per query.

 An example permutation scheme to detect hamming distances of up to 6 bits, which would still be reasonably efficient for a corpus of 8 million documents.

 You will need to find a table arrangement that works best for you. Decide on the bit-length of your simhashes; test the simhashes you produce from your documents to determine how many bits of Hamming distance you need to allow (k); and determine how large your corpus is expected to grow and thus how many bits would be “almost a counter”. Then you can figure out a suitable permutation scheme that balances storage size against processing time.

 If you find that you need to detect more bits difference than this approach can accommodate, you are probably looking for full similarity detection rather than near-duplicate detection, and should investigate algorithms such as minhash.

 Algorithms , Programming
 Previous Entries The Song of Solomon: a frank translation Next Entries COVID-19 Ozone Therapy notes

 Leave a Reply

 Comment

 Name *

 Email *

 Website

 Save my name, email, and website in this browser for the next time I comment.

 This site uses Akismet to reduce spam. Learn how your comment data is processed.

 Archives

 * August 2021
 * June 2020
 * April 2020
 * August 2019
 * July 2018
 * November 2015
 * November 2014
 * September 2014
 * August 2014

 Meta

 * Log in

 Create a website and earn with Altervista - Disclaimer - Report Abuse

Simhashes are a clever means of rapidly finding near-identical documents (or other items) within a large corpus, without having to individually compare every document to every other document. Using simhashes for any sizable corpus involves two parts: generating the simhash itself, and solving the Hamming distance problem. Neither is much use without the other. Unlike minhashes, the simhash approach doesn’t really allow full similarity detection, because the range of similarity it is sensitive to is so small. It’s better described as near-duplicate detection. Google have patented simhash (though not the Hamming distance solution, as far as I know).
As well as its other limitations simhash is substantially more complex than minhash and harder to tune. Its real benefit is that it performs way faster than minhash, even on enormous corpuses, and typically requires less storage.
Generating the simhash
A simhash is a single sequence of bits (usually 64 bits) generated from a set of features in such a way that changing a small fraction of those features will cause the resulting hash to change only a small fraction of its bits; whereas changing all features will cause the resulting hash to look completely different (roughly half its bits will change).
As with any similarity detection scheme, its success depends on choosing sensible features. Let’s say you’re comparing documents: a typical feature to choose might be shingles of words, with whitespacing and case normalized. You might add in other features, such as document title, text styled as headings, and so on.
Each feature must be hashed using a cheap but good standard (non-cryptographic) hash such as FNV-1a, with the same bit-length as your intended simhash.
To combine the many feature hashes into a single simhash, you calculate a kind of bitwise average of them all. It’s very simple. Take the first bit of every feature hash and average them. You get some value between 0 and 1. Round that value to 0 if it’s less than 0.5, and otherwise to 1. That gives you the first bit of your simhash. Do the same for the second bit of every feature hash, to yield the second bit of your simhash. And so on.
 Feature hashes are combined into a bitwise average, then those averages are rounded to yield the bits of the simhash. 
You can see that changing just one feature hash out of thousands may not change many (or any) bits in the simhash, whereas changing a lot of feature hashes will have a larger effect.
Comparing two documents for (estimated) similarity is now as simple as determining the Hamming distance between the two simhashes, which can be calculated very efficiently. Unfortunately, in most situations you don’t need to compare one single document to another single document; you need to compare every document to every other one. Even with such an efficient calculation of hamming distance, to find all near-duplicates in a corpus of 10 million documents would require 10M×(10M-1)/2 = nearly 50 trillion comparisons, which is completely unworkable. This is why simhashing isn’t much use without “solving the hamming distance problem”, described below. The solution to that problem only works for quite small hamming distances: typically 2 to 7 bits difference, depending on your storage capacity, speed requirements and corpus size.
For this reason, a lot of careful tuning goes into trying to make the simhashes sensitive to those features we consider most important and less sensitive to others. This involves choosing suitable features for hashing and suitable methods of normalizing features (such as lowercasing text and simplifying whitespacing). It also involves giving higher or lower weights to certain features: we thus calculate each bit of the simhash as a (rounded) weighted average.
An example of a kind of feature you might want to exclude is advertising text in a webpage. There are some simple tricks for reducing the influence of advertising text, such as only taking shingles that include at least one stopword (since advertisements typically contain few stopwords). But you may have to do more complex feature detection.
The method of calculating a simhash is described in slightly different terms in Google’s patents. As they describe it, you keep a tally for every bit, which starts at zero. For each bit of each feature hash, if it is 1, add that feature’s weight to the corresponding tally; or if it is zero subtract its weight from the tally. From the final tallies, set your simhash bit to 1 where the corresponding tally is &gt;0, otherwise set it to 0. This is illustrated below:
 In this example features are extracted and turned into weighted hashes; then the weights for each bit of each feature are added (up-arrow) or subtracted (down-arrow) in each bit’s tally. The bits of the simhash are determined by the sign of each of the tally totals. The feature hashes are coloured so you can see how each contributes to the tallies. 
It’s a little more cumbersome to describe the algorithm this way, but it should be clear that it is exactly equivalent to a bitwise rounded weighted average.
I recommend you keep weights for particular types of feature constant. E.g., don’t weight shingles more highly near the beginning of the document and gradually less and less toward the end. Otherwise relatively small changes in position of text, such as inserting an extra paragraph early in the document, can have a substantial impact on the simhash.
There’s probably not a lot of choice in the bit-length of your simhashes. I recommend 64 bits. 128 bits would be overkill for almost any purpose, and 32 bits is insufficient for most purposes. Remember that 32 bits only stores a little over 4 billion values, which may sound like a lot, but is ripe for collisions. Let’s say your hash is 32 bits long and k is 4. For any given fingerprint there are 41,449 bit-patterns that are within k bits Hamming distance of it, and any document that happens to have one of those fingerprints as a result of a hash collision will be detected as similar. With a corpus of 100,000 documents you’d already be getting frequent collisions.
A word on images
Simhash, minhash and the like can be used for detecting similar images, if you choose sensible features to generate your feature hashes from. The features should be derived in such a way that similar images are likely to contain many identical features. This is far from straightforward. Depending on what you want to consider ‘similar’, the features may need to be robust to changes in scale, orientation, colour balance, blur/sharpness, etc.
You may want to treat images embedded in a document as features of that document, and generate simple binary hashes of them (as in the example above). If you do so, be aware that any change, visible or otherwise, will result in a different feature hash.
Now comes the really clever bit, that relieves us of having to individually compare every simhash with every other simhash in order to find all duplicates in the corpus. This is what saves us from performing 50 trillion Hamming distance calculations to deduplicate our corpus of 10 million documents! The explanation in Google’s paper is difficult to follow, and I couldn’t find a simpler explanation, so I’m creating one here. I’ll stick to the original paper’s terminology and notation, to avoid confusion.
Let’s say we’re a Google web crawler, and we find a new document with fingerprint (simhash) F. It so happens that we’ve previously encountered another document with a very similar fingerprint G that differs by at most k=3 bits.
 Fingerprint F: generated from our incoming document 
 Fingerprint G: from a previously-encountered document 
 Only 3 bits differ between the two. 
If we divide the 64 bits into 6 blocks, we know that the differing bits can occur in no more than 3 of those blocks:
 
We can then permute these 6 blocks so that the three blocks containing differing bits all move into the low-order bits:
 
The permuted F we’ll call F′, and the permuted G we’ll call G′. Notice that in the first 3 blocks (totalling 32 bits), F′ and G′ are identical.
Now, we have kept a table of the permuted hashes of all the documents we’ve previously encountered. All the hashes in that table have had exactly the same permutation applied, and the table is sorted. That means that all the permuted hashes that share their first 32 bits with our permuted fingerprint F′ are in a single contiguous section of the table, and we can find them rapidly using binary search, or even more efficiently, interpolation search.
Once we’ve found permuted hashes that share the first 32 bits, we still need to compare the low order bits to determine total Hamming distance. Then we’ve found our similar documents.
“Wait!”, I hear you say. The permutation we’ve chosen may work for this example, but what about all the other fingerprints whose 1, 2 or 3 differing bits fall in different blocks? Well, that’s why we actually store 20 such tables, each with a different permutation, so that in each table a different combination of 3 blocks is pushed into the low bits. COMB(6,3) = 20. When we look for similar fingerprints to F, we’ll have to generate 20 different permutations of it and search in each of the 20 tables.
 Permutation schemes for 20 different tables to push different blocks into the low-end bits 
But let’s return to F′ and G′ and this particular permuted table. Interpolation search has yielded a set of candidates that we have to calculate Hamming distance on. That’s a fairly cheap operation, but still could be time-consuming if there are a lot of candidates. So how many candidates should we expect, on average?
Well, Google indexes around 8 billion documents, which is roughly 234. So our table contains around 234 fingerprints. On average there will be just one document that shares the highest 34 bits with F′, or 4 that share the highest 32 bits (since 234-32 = 4). So on average, we’ll only have to calculate hamming distance for 4 candidates (within this table). Nice!
There’s another way to explain this: Imagine we have 234 truly random fingerprints, in sorted order. If we take just the first 34 bits of these fingerprints (shaded green below), they will amount to ‘almost a counter’, since most of the possible numbers will be represented and only a minority of possible numbers will be repeated. If we take just the least significant 30 bits, though, they will look “almost random”.
 A small section of the table. The upper 34 bits in green are ‘almost a counter’. The lower 30 bits appear virtually random. And there’s G′ with its differing bits highlighted. 
But we’re only matching the first 32 bits, so we find on average 4 candidates per query.
 
Because 64 isn’t evenly divisible by 6, our blocks are 11, 11, 11, 11, 10 and 10 bits wide. That means our different tables will need to be searched with different numbers of high-end bits: 31, 32 or 33 depending on the permutation, yielding 8, 4 or 2 candidates on average.
By performing this same cheap search on each of the 20 tables we can be certain we have found every fingerprint that differs by at most k=3 bits.
Storing the tables
For fast response, tables should be held in main memory. Each of the permuted tables should store only permuted hashes, and a separate table should contain mappings from the unpermuted hashes back to document IDs.
The most compact storage for the hash tables is as a sorted list (and Google’s paper describes how to further compress the table). If you want to insert new entries as you go then you’ll need trees (quite a bit more storage required), or else you could keep most entries in sorted lists and new entries in trees and check both, and periodically merge the trees back into the sorted lists.
If you don’t have to detect similarities as soon as new documents arrive, there are nice efficiencies to be gained. Not only can you store the tables as more compact sorted lists, you can also find all similarities in a single pass through all tables, by just finding every group of hashes permuted hashes that shares the first d bits, and checking their Hamming distances.
In Google’s paper they recommend a means of compacting a sorted list still further, exploiting the fact that many of the high-end bits don’t change much from one entry to the next. I’ve never bothered with this, but if you’re really struggling with storage, bear it in mind.
Other configurations
Aside from the 6-block configuration discussed above, there are other configurations that give different memory/processing trade-offs with k=3. For instance, 4 blocks (of 16 bits each) requires only 4 permuted tables (since COMB(4,3) = 4).
 Four blocks of 16 bits each, with k = 3 
Given there are only 16 bits we are doing the table search on, we can expect on average 234-16 = 262,144 results per query for each table, or about a million hamming checks per query overall.
In the example above, we match on 16 bits, leaving 48 non-match bits. We could further subdivide each table, by splitting the 48 non-match bits into 4 blocks of 12 bits each and permuting them in turn, for a total of 16 tables:
 
Now we can match on the first 28 bits, using 16 tables and getting on average 234-28 = 64 results per query.
There are several such table variants described in Google’s paper, each offering a different trade-off between number of tables required, and average number of candidate matches per query.
Many applications won’t need to index 234 documents, and could increase k a little. For instance, let’s say you only expect to index around 223 (~8 million) documents. You could readily increase the possible Hamming distance up to k = 6, by dividing the hash into 8 blocks (28 tables). On average you’d be getting 128 candidates per query for each table, meaning you’d have to perform about 3,500 hamming distance checks in total per query.
 An example permutation scheme to detect hamming distances of up to 6 bits, which would still be reasonably efficient for a corpus of 8 million documents. 
You will need to find a table arrangement that works best for you. Decide on the bit-length of your simhashes; test the simhashes you produce from your documents to determine how many bits of Hamming distance you need to allow (k); and determine how large your corpus is expected to grow and thus how many bits would be “almost a counter”. Then you can figure out a suitable permutation scheme that balances storage size against processing time.
If you find that you need to detect more bits difference than this approach can accommodate, you are probably looking for full similarity detection rather than near-duplicate detection, and should investigate algorithms such as minhash.
Simhash and solving the hamming distance problem: explained
http://benwhitmore.altervista.org/simhash-and-solving-the-hamming-distance-problem-explained/?doing_wp_cron=1644764641.0774369239807128906250