Hashing by doing modulo $m$ for $m=p^2$ for a prime $p$ instead of using a prime $m$ - is it that bad?

Question

I am doing an exercise from a Big Data course I'm taking on Coursera (this exercise is for experimenting with a big-data problem and is not for any credit or homework) , the assignment was described briefly:

Your task is to quickly find the number of pairs of sentences that are at the word-level edit distance at most 1. Two sentences S1 and S2 they are at edit distance 1 if S1 can be transformed to S2 by: adding, removing or substituting a single word.

I am then given a large txt file that contains about $10^6$ sentences.

The way I tried to attack this problem:

Observation $1$: If the length of two sentences is greater then $1$ then they are not at an edit distance $1$.

Observation $2$: Let $A_1,...,A_5$ be five consecutive words from a sentences and let $B_1,...,B_5$ be another five consecutive words chosen from different indexes (that is if we label the words of a sentence then $B_i$ and $A_j$ does not share an index.

• Five is a small arbitrary number I chose

I used something like a curried syntax to get a hashtable that keeps a 3-touple: $(X,Y,Z)$

Where I mapped each sentence as follows:

• $X$ is the number of words the sentence have.

• $Y$ is obtained by a hash function on the content of the words (I will soon describe this hash function)

• $Z$ is a list of integers containing the index of the line in the document [the line number] that was mapped to $(X,Y)$

In C# this corresponds to an object of a type

Dictionary< int, Dictionary< int, List< int>>>

So I kept two Hashtables of the above form, where I took the first five words to hash and get $Y$ and words $6-10$ to hash and get another value of $Y$.

Then given a sentence - compute the two $Y$ values it would of gotten and look at buckets with length that differs at at most $1$ from this sentence length and share one $Y$ value this sentence.

Let me describe the hashing function I used to get $Y$ -

1. I took the $A_i$ (similarly with the $B_i$) and concatenated them

2. I looked at this string as a byte array (that is by the bits that takes to represent the numbers) I then applied a the SHA-1 hash function on it (there are no security reasons for this but I wanted something that hashes well)

3. I took the last $4$ bytes in the SHA-1 hash and I looked at it as a positive integer (by looking at the last $32$ bits and considering it as an integer then applying the absolute value function). Call this result $R$

   4. $Y= R\%p^{2}$

where $p$ was chosen as follows: I counted how many lines of a given length $l$ appear (say $n_l$), for lines of length $l$ I chose $p$ s.t $$\frac{n_l}{p^2}\leq 3$$

the following is a Histogram showing $n_l$ as a function of $l$

which should give some indication of the values chosen for $p$.

However - There are too many collisions - I get about $6$ elements in each bucket.

I took one example of such a bucket and I printed those sentences (I hoped they are similar so they would have a good reason to be mapped to the same bucket) by they are very different from one another. This is a printscreen of those sentences printed to the console.

Question: Why do I get a large number of collisions ?($6$ in average on $10^5$ buckets I considered where if I had even distribution I would expect $3$ from the choice of $p$, some buckets have a few tens of elements in them)

Could the problem be that I used modulo a square of a prime and not a prime ? is it that significant?

Answer 1

There are a lot of things which could have gone wrong, but it is really hard to say, especially since you don't tell us the bad values of $n_l$ and $p^2$. So for now, here are some comments:

1. SHA1 is slow relative to non-cryptographic hashes. If you are lucky then your programming language already has a fast hash implementation.

2. There is no need to take the absolute value of the last 32 bits. Instead, consider it as an unsigned integer (unless you're using a language such as Java which doesn't have them).

3. Since the last 32 bits of the SHA1 hash are very random, you can take them modulo any modulus that you want (assuming it is small compared to $2^{32}$). There is no particular advantage in choosing a prime or a prime power.

4. Due to the random nature of the hash, you don't expect sentence snippets falling into the same bucket to have anything in common, unless they're exactly equal.

5. If everything is random and $n_l/p^2$ is very small compared to $n_l$ then you expect the distribution of balls in each bucket to be roughly Poisson with expectation $n_l/p^2$. Assuming this, for $n_l/p^2 = 3$, the probably to get at least 6 balls in some bucket is roughly $0.084$, so you would expect this fraction of buckets to contain at least 6 balls. Assuming a maximum value of roughly $100,000$ buckets (my estimate from your graph), you expect to see 7 buckets having at least 12 balls. You shouldn't be getting buckets with a few tens of elements, though: the probability of having any bucket with at least 20 balls is at most $8 \cdot 10^{-6}$, for example.

In view of this, I suggest you pick some particular experiment and compare the distribution of the number of balls in buckets to the corresponding Poisson distribution. If you find any major discrepancy (an ill-defined concept), let us know the exact values of $n_l$ and $p^2$ you used.

Answer 2

There are some reason why people would like to use modulo prime hashing. Assume we need a hash from $\{1,\ldots,n\}$ to $\{1,\ldots,m\}$, one popular choice is $h(n) = (an+b)\mod p\mod m$, where $p$ is a prime greater than $n$ and $a,b$ are randomly chosen from $\{1,\ldots,p\}$. Hashing function $h$ has a advantage that $h(x)$ is almost uniform and $h(i),h(j)$ are almost independent. Such property is called 2-universal, which is very useful. This is why you may have seen $h$ in the textbook.

While 2-universal, and other ideal properties of hashing, is useful only if you are fighting against malevolent input. On the opposite, when the input is random, any function that maps equal number of keys to different bucket is equivalent good. You do not need those heavy hash e.g. SHA1. You should use some lightweight hash functions, while I'd recommend you to use more buckets, e.g. $2^{32}$, to avoid collision. C# would take care of the space, you dont need to mind it.

Finally, when people use hashing, they typically use it to speed up accession. While in your homework, hashing can be used more constructively. There exists some hash function $h_1,h_2$, which can be computed in linear time, such that the collisions between $h_{*}(s_i), h_{*}(s_j)$ hints $s_i,s_j$ has word-level edit distance at most 1.