min-wise independent linear permutations

MaRDI QIDQ1977373zbMATH OpenFDO

Authors Tom Bohman, Colin Cooper, Alan Frieze

Publication date 11 May 2000

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/120644, http://www.emis.de/journals/EJC/Volume_7/Abstracts/v7i1r26.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

AltaVista Web index algorithmapproximate min-wise independencedetection and filtering of near-duplicate documentsmin-wise independent linear permutations

Mathematics Subject Classification ID

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

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.

Recommendations

• Min-wise independent permutations
• scientific article; zbMATH DE number 1563190
• scientific article; zbMATH DE number 1775418
• Publication:4941822
• scientific article; zbMATH DE number 1445298

Cited in

(10)

• Min-wise independent permutations
• scientific article; zbMATH DE number 1615265 (Why is no real title available?)
• Low discrepancy sets yield approximate min-wise independent permutation families
• scientific article; zbMATH DE number 1775418 (Why is no real title available?)
• Streaming techniques and data aggregation in networks of tiny artefacts
• scientific article; zbMATH DE number 1563190 (Why is no real title available?)
• scientific article; zbMATH DE number 1418262 (Why is no real title available?)
• scientific article; zbMATH DE number 1418263 (Why is no real title available?)
• scientific article; zbMATH DE number 1445298 (Why is no real title available?)
• The exact probability law for the approximated similarity from the Minhashing method

This page was built for publication: min-wise independent linear permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1977373)