Exponential time improvement for min-wise based algorithms

In this paper we extend the notion of min-wise independent family of hash functions by defining a k-min-wise independent family of hash functions. Informally, under this definition, all subsets of size k of any fixed set X have an equal chance to have the minimal hash values among all the elements in X, when the probability is over the random choice of hash function from the family. This property measures the randomness of the family, as choosing a truly random function, obviously, satisfies the definition for k = |X|. We define and give an efficient time and space construction of approximately k-min-wise independent family of hash functions by extending Indyk’s construction of approximately min-wise independent [1]. The number of words needed to represent each function is O(k log log ( 1