Bohmann, Tom; Cooper, Colin; Frieze, Alan 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. Reviewer: Neculai Curteanu (Iaşi) Cited in 1 Document 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.) Keywords:min-wise independent linear permutations; detection and filtering of near-duplicate documents; AltaVista Web index algorithm; approximate min-wise independence PDFBibTeX XMLCite \textit{T. Bohmann} et al., Electron. J. Comb. 7, No. 1, Research paper R26, 6 p. (2000; Zbl 0949.60016) Full Text: EuDML EMIS