min-wise independent linear permutations (Q1977373)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | min-wise independent linear permutations |
scientific article |
Statements
min-wise independent linear permutations (English)
0 references
11 May 2000
0 references
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.
0 references
min-wise independent linear permutations
0 references
detection and filtering of near-duplicate documents
0 references
AltaVista Web index algorithm
0 references
approximate min-wise independence
0 references