min-wise independent linear permutations (Q1977373)

The aim of the paper is to improve a result on the (exponentially large) family of min-wise independent (linear) permutations which (under some relaxations) are essential to the algorithm used in practice by the AltaVista Web index software to detect and filter near-duplicate documents. The authors obtain a new formula that approximates the expectations over a subset of permutations chosen uniformly at random from the set of min-wise independent linear permutations. This result shows that a simply chosen random linear permutation will suffice for an average set from the point of view of approximate min-wise independence.