### Abstract

A family of permutations F of [n] = {1, 2, . . . ,n} is (ε, k)-min-wise independent if for every nonempty subset X of at most k elements of [n], and for any x ∈ X, the probability that in a random element π of F, π(x) is the minimum element of π(X), deviates from 1/|X| by at most ε/|X|. This notion can be defined for the uniform case, when the elements of F are picked according to a uniform distribution, or for the more general, biased case, in which the elements of F are chosen according to a given distribution D. It is known that this notion is a useful tool for indexing replicated documents on the web. We show that even in the more general, biased case, for all admissible k and ε and all large n, the size of F must satisfy |F| > Ω(k/ε^{2} log(1/ε) log n), as well as |F| > Ω(k^{2}/ε log (1/ε) log n). This improves the best known previous estimates even for the uniform case.

Original language | English (US) |
---|---|

Pages (from-to) | 384-389 |

Number of pages | 6 |

Journal | Random Structures and Algorithms |

Volume | 31 |

Issue number | 3 |

DOIs | |

State | Published - Oct 2007 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
- Applied Mathematics

### Keywords

- Linear algebra method
- Min-wise independence
- Resemblance

## Fingerprint Dive into the research topics of 'On (ε, k)-min-wise independent permutations'. Together they form a unique fingerprint.

## Cite this

*Random Structures and Algorithms*,

*31*(3), 384-389. https://doi.org/10.1002/rsa.20184