min-wise independent linear permutations
type: Item
instance of: scholarly article
title: min-wise independent linear permutations
zbMATH Open document ID: 0949.60016
author: Tom Bohman
author: Colin Cooper
author: Alan Frieze
published in: The Electronic Journal of Combinatorics
publication date: 2000-05-11T00:00:00Z
full work available at URL: https://eudml.org/doc/120644
full work available at URL: v7i1r26.html
review text: 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.
reviewed by: Neculai Curteanu
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 62G20
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 1446319
zbMATH Keywords: min-wise independent linear permutations
zbMATH Keywords: detection and filtering of near-duplicate documents
zbMATH Keywords: AltaVista Web index algorithm
zbMATH Keywords: approximate min-wise independence
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1446319