×

min-wise independent linear permutations. (English) Zbl 0949.60016

Electron. J. Comb. 7, No. 1, Research paper R26, 6 p. (2000); printed version J. Comb. 7, No. 1 (2000).
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.

MSC:

60C05 Combinatorial probability
68P20 Information storage and retrieval of data
62G20 Asymptotic properties of nonparametric inference
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: EuDML EMIS