In the paper on MinWise independent permutations ([MinWise independent permutations](http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/BroderCFM-minwise.pdf)), 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.



How is a permutation taken as an equivalent of a hash function in MinWise independent permutations?
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 ? 


