Min-Wise Independence vs. 3-Wise Independence

Toshiya ITOH

Min-Wise Independence vs. 3-Wise Independence

Toshiya ITOH

Full Text Views

0

Cite this

Summary :

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 {0,1,. . . ,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₁,x₂,. . . ,x_d {0,1,. . . , n-1} and any distinct y₁,y₂,. . . ,y_d {0,1,. . . , 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 {0,1,. . . ,n-1} such that 3 ||X||=k n-2 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(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 {0,1,. . . ,n-1} such that 4 ||X||=k n-3 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(k-2)}- 1/{6(k-2)²}; (upper bound) Pr[min {π(X)}=π(x)] 2/k - 2/k + 1/(3kk).

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

Cite this

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 {0,1,. . . ,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₁,x₂,. . . ,x_d {0,1,. . . , n-1} and any distinct y₁,y₂,. . . ,y_d {0,1,. . . , 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 {0,1,. . . ,n-1} such that 3 ||X||=k n-2 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(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 {0,1,. . . ,n-1} such that 4 ||X||=k n-3 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(k-2)}- 1/{6(k-2)²}; (upper bound) Pr[min {π(X)}=π(x)] 2/k - 2/k + 1/(3kk).
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 {0,1,. . . ,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₁,x₂,. . . ,x_d {0,1,. . . , n-1} and any distinct y₁,y₂,. . . ,y_d {0,1,. . . , 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 {0,1,. . . ,n-1} such that 3 ||X||=k n-2 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(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 {0,1,. . . ,n-1} such that 4 ||X||=k n-3 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(k-2)}- 1/{6(k-2)²}; (upper bound) Pr[min {π(X)}=π(x)] 2/k - 2/k + 1/(3kk).},
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 {0,1,. . . ,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₁,x₂,. . . ,x_d {0,1,. . . , n-1} and any distinct y₁,y₂,. . . ,y_d {0,1,. . . , 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 {0,1,. . . ,n-1} such that 3 ||X||=k n-2 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(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 {0,1,. . . ,n-1} such that 4 ||X||=k n-3 and any x X, (lower bound) Pr[min {π(X)}=π(x)] 1/{2(k-2)}- 1/{6(k-2)²}; (upper bound) Pr[min {π(X)}=π(x)] 2/k - 2/k + 1/(3kk).
ER -