How is a permutation taken as an equivalent of a hash function in MinWise independent permutations?

Question

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.

Answer 1

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 ?

Answer 2

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.

Answer 3

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

Answer 4

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.