The search functionality is under construction.

The search functionality is under construction.

A family *F* of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. We say that a family *F* of permutations on {0,1,. . . ,*n*-1} is **min-wise independent** if for any *X* *n*-1} and any *x* *X*, Pr[min {π(*X*)} = π(*x*)]= ||*X*||^{-1} when π is chosen uniformly at random from *F*, where ||*A*|| is the cardinality of a finite set *A*. We also say that a family *F* of permutations on {0,1,. . . ,*n*-1} is *d*-**wise independent** if for any distinct *x*_{1},*x*_{2},. . . ,*x*_{d} *n*-1} and any distinct *y*_{1},*y*_{2},. . . ,*y*_{d} *n*-1}, Pr[_{i=1}^{d} π(*x*_{i}) = π(*y*_{i})]= 1/{*n*(*n*-1)・・・ (*n*-*d*+1)} when π is chosen uniformly at random from *F* (note that nontrivial constructions of *d*-wise independent family *F* of permutations on {0,1,. . . ,*n*-1} are known only for *d*=2,3). Recently, Broder, et al. showed that any family *F* of pairwise (2-wise) independent permutations behaves close to a family of min-wise independent permutations, i.e., for any *X* *n*-1} such that 3 *X*||=*k**n*-2 and any *x* *X*, (lower bound) Pr[min {π(*X*)}=π(*x*)]*k*-1)}; (upper bound) Pr[min {π(*X*)}=π(*x*)]*O*(1/*k*). In this paper, we extend these bounds to 3-wise independent permutation family and show that any family of 3-wise independent permutations behaves closer to a family of min-wise independent permutations, i.e., for any *X* *n*-1} such that 4 *X*||=*k**n*-3 and any *x* *X*, (lower bound) Pr[min {π(*X*)}=π(*x*)] *k*-2)}- 1/{6(*k*-2)^{2}}; (upper bound) Pr[min {π(*X*)}=π(*x*)]*k* - 2/*k* + 1/(3*k**k*).

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.5 pp.957-966

- Publication Date
- 2002/05/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

- Category

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Toshiya ITOH, "Min-Wise Independence vs. 3-Wise Independence" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 5, pp. 957-966, May 2002, doi: .

Abstract: A family *F* of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. We say that a family *F* of permutations on {0,1,. . . ,*n*-1} is **min-wise independent** if for any *X* *n*-1} and any *x* *X*, Pr[min {π(*X*)} = π(*x*)]= ||*X*||^{-1} when π is chosen uniformly at random from *F*, where ||*A*|| is the cardinality of a finite set *A*. We also say that a family *F* of permutations on {0,1,. . . ,*n*-1} is *d*-**wise independent** if for any distinct *x*_{1},*x*_{2},. . . ,*x*_{d} *n*-1} and any distinct *y*_{1},*y*_{2},. . . ,*y*_{d} *n*-1}, Pr[_{i=1}^{d} π(*x*_{i}) = π(*y*_{i})]= 1/{*n*(*n*-1)・・・ (*n*-*d*+1)} when π is chosen uniformly at random from *F* (note that nontrivial constructions of *d*-wise independent family *F* of permutations on {0,1,. . . ,*n*-1} are known only for *d*=2,3). Recently, Broder, et al. showed that any family *F* of pairwise (2-wise) independent permutations behaves close to a family of min-wise independent permutations, i.e., for any *X* *n*-1} such that 3 *X*||=*k**n*-2 and any *x* *X*, (lower bound) Pr[min {π(*X*)}=π(*x*)]*k*-1)}; (upper bound) Pr[min {π(*X*)}=π(*x*)]*O*(1/*k*). In this paper, we extend these bounds to 3-wise independent permutation family and show that any family of 3-wise independent permutations behaves closer to a family of min-wise independent permutations, i.e., for any *X* *n*-1} such that 4 *X*||=*k**n*-3 and any *x* *X*, (lower bound) Pr[min {π(*X*)}=π(*x*)] *k*-2)}- 1/{6(*k*-2)^{2}}; (upper bound) Pr[min {π(*X*)}=π(*x*)]*k* - 2/*k* + 1/(3*k**k*).

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_5_957/_p

Copy

@ARTICLE{e85-a_5_957,

author={Toshiya ITOH, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={Min-Wise Independence vs. 3-Wise Independence},

year={2002},

volume={E85-A},

number={5},

pages={957-966},

abstract={A family *F* of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. We say that a family *F* of permutations on {0,1,. . . ,*n*-1} is **min-wise independent** if for any *X* *n*-1} and any *x* *X*, Pr[min {π(*X*)} = π(*x*)]= ||*X*||^{-1} when π is chosen uniformly at random from *F*, where ||*A*|| is the cardinality of a finite set *A*. We also say that a family *F* of permutations on {0,1,. . . ,*n*-1} is *d*-**wise independent** if for any distinct *x*_{1},*x*_{2},. . . ,*x*_{d} *n*-1} and any distinct *y*_{1},*y*_{2},. . . ,*y*_{d} *n*-1}, Pr[_{i=1}^{d} π(*x*_{i}) = π(*y*_{i})]= 1/{*n*(*n*-1)・・・ (*n*-*d*+1)} when π is chosen uniformly at random from *F* (note that nontrivial constructions of *d*-wise independent family *F* of permutations on {0,1,. . . ,*n*-1} are known only for *d*=2,3). Recently, Broder, et al. showed that any family *F* of pairwise (2-wise) independent permutations behaves close to a family of min-wise independent permutations, i.e., for any *X* *n*-1} such that 3 *X*||=*k**n*-2 and any *x* *X*, (lower bound) Pr[min {π(*X*)}=π(*x*)]*k*-1)}; (upper bound) Pr[min {π(*X*)}=π(*x*)]*O*(1/*k*). In this paper, we extend these bounds to 3-wise independent permutation family and show that any family of 3-wise independent permutations behaves closer to a family of min-wise independent permutations, i.e., for any *X* *n*-1} such that 4 *X*||=*k**n*-3 and any *x* *X*, (lower bound) Pr[min {π(*X*)}=π(*x*)] *k*-2)}- 1/{6(*k*-2)^{2}}; (upper bound) Pr[min {π(*X*)}=π(*x*)]*k* - 2/*k* + 1/(3*k**k*).

keywords={},

doi={},

ISSN={},

month={May},}

Copy

TY - JOUR

TI - Min-Wise Independence vs. 3-Wise Independence

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 957

EP - 966

AU - Toshiya ITOH

PY - 2002

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E85-A

IS - 5

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - May 2002

AB - A family *F* of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. We say that a family *F* of permutations on {0,1,. . . ,*n*-1} is **min-wise independent** if for any *X* *n*-1} and any *x* *X*, Pr[min {π(*X*)} = π(*x*)]= ||*X*||^{-1} when π is chosen uniformly at random from *F*, where ||*A*|| is the cardinality of a finite set *A*. We also say that a family *F* of permutations on {0,1,. . . ,*n*-1} is *d*-**wise independent** if for any distinct *x*_{1},*x*_{2},. . . ,*x*_{d} *n*-1} and any distinct *y*_{1},*y*_{2},. . . ,*y*_{d} *n*-1}, Pr[_{i=1}^{d} π(*x*_{i}) = π(*y*_{i})]= 1/{*n*(*n*-1)・・・ (*n*-*d*+1)} when π is chosen uniformly at random from *F* (note that nontrivial constructions of *d*-wise independent family *F* of permutations on {0,1,. . . ,*n*-1} are known only for *d*=2,3). Recently, Broder, et al. showed that any family *F* of pairwise (2-wise) independent permutations behaves close to a family of min-wise independent permutations, i.e., for any *X* *n*-1} such that 3 *X*||=*k**n*-2 and any *x* *X*, (lower bound) Pr[min {π(*X*)}=π(*x*)]*k*-1)}; (upper bound) Pr[min {π(*X*)}=π(*x*)]*O*(1/*k*). In this paper, we extend these bounds to 3-wise independent permutation family and show that any family of 3-wise independent permutations behaves closer to a family of min-wise independent permutations, i.e., for any *X* *n*-1} such that 4 *X*||=*k**n*-3 and any *x* *X*, (lower bound) Pr[min {π(*X*)}=π(*x*)] *k*-2)}- 1/{6(*k*-2)^{2}}; (upper bound) Pr[min {π(*X*)}=π(*x*)]*k* - 2/*k* + 1/(3*k**k*).

ER -