1
$\begingroup$

In the paper on MinWise independent permutations (MinWise independent permutations), the authors say that it is often convenient to consider permutations rather than hash functions (Pg-3).

While I understand that for a set X to be minwise independent, all elements in it must have the same probability of becoming the minimum element of its image under a randomly chosen hash function ∏, the part that I don't understand is where the authors say that ∏ could be conveniently taken as a permutation instead of a hash function.

Is there any example of it that anybody could provide that could help me understand this part better? How is the mapping of an element from the set X using a permutation supposed to function? I understand the purpose. But since I cant figure out the permutation analogy, I'm unable to find out how this works in practice.

What I understand of this paper is something like this - To reduce the dimensionality of a set, we can generate (a fixed number of) minwise independent permutations, and for all these different permutations we can find out a minimum hash value. Since each element of the permutation is equally likely to be the minimum hash value, this minimum hash value can be then taken to (in a way) represent the set, hence representing the document on a scale of our choice. So no matter what number of words documents contain, if we generate 100 minwise independent permutations, we can represent the document in 100 words (or items from the universe set).

Thanks.

$\endgroup$

4 Answers 4

1
$\begingroup$

For the purpose of min-wise hashing, the only goal of the permutation (or hash function) is to map the initial bag of numbers into another bag, so that we can then pick off the min as the 'hash value'. So for this purpose, you should think of the permutation as merely a function that takes [1..n] and maps it to [1..n] (sending every element to its image under the permutation).

Are you concerned about the relative sizes of the domain and range ?

$\endgroup$
2
  • $\begingroup$ Thanks for your response. I'm more or less comfortable with the idea, but I'm still a little bit confused about the details. Mentioning that we consider a set Sn, and for any set F $\subseteq$ Sn, if for any set X $\subseteq$ [n] and for any x $\in$ X, when $\pi$ is chosen at random in F, the mentioned condition (of the probability of the image of any x from X being the minimum value as 1/|X|) holds true. How exactly is the $\pi$ defined "from" F? Yes I'd appreciate if a word is mentioned about the domain/range. Thanks again $\endgroup$
    – Siddhant
    Apr 25, 2010 at 19:47
  • $\begingroup$ I suppose we could just assume that by permutations, the authors mean a different permutation of the input set generated on application of the hash function. Now onto how MinHashing works. :-) $\endgroup$
    – Siddhant
    Apr 26, 2010 at 20:37
0
$\begingroup$

The function could possibly be an index array of size n. For example, F[1,...,n] =[2,1,4,5...]. The total number of all these functions would be n!. The position of 1 implies the minimum hashed integer. For example, F[2] = 1 implies that 2 will be mapped into the minimum hash value (1). If we randomly choose F, it is easy to see that 1 appears in each position of the array equally likely. So the minwise independence condition holds. Hopefully this helps.

$\endgroup$
0
$\begingroup$

How is the minimum element of a permutation different from simply a randomly chosen element of the original bag (or set)?

$\endgroup$
0
$\begingroup$

A permutation is the equivalent of an unbiased "good" hash function because it has even distribution. Since a permutation maps (1,2,...,n) $\to$ permuted-list-of(1,2,..., n), if the original set $A$ is an unbiased random selection of the range $1$ to $n$, then the likelihood that the $B$="permutation-hash" of $A$ will contain the minimum-value of $1$ to $n$ is the size of the set $A$ divided by $n$.

If the hash function is equitable and well-distributed, then the range of input values will be "hashed" into and map into the output range in an evenly distributed fashion. If the domain is a group of 256 characters, and the hash is a function which outputs 8 characters, then you want the domain to be partitioned into as closely-equal-sized subsets based on the what the hash of the domain words are.

A hash normally reduces the size of the object being hashed, thus because of the pigeonhole priniciple, at least one element of the range of the hash must map to more than one item in the domain. An equitable hash attempts to minimize the variance in the size of the bins which the domain is partitioned into. An inequitable hash leads to some of the bins being very different in size from the other bins. Thus a hash is usually a one-way mapping: given the hash of a message, it is not possible to determine what the original message consisted of, even though it may be possible to deduce what partition the message is part of (the partition whose hash digest is ...)

For example, the hash function EVEN-ODD, equivalently called REMAINDER-MODULO-2, is easily calculated by looking at the last (lowermost) bit of the message. If the range is a subset of $\mathbb{Z}$, e.g. the numbers $1...n$, then EVEN-ODD is an equitable hash, as the size of the partitions will differ by at most $1$.

A permutation is equivalent to performing a hash which does not reduce the size of the domain as it maps into the range, it performs a bijection. As such, the size of each partition is $1$, the variance of the sizes of the partitions is $0$, and these partitions are as equitably sized as possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.