부
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 x1,x2,. . . ,xd {0,1,. . . , n-1} and any distinct y1,y2,. . . ,yd {0,1,. . . , n-1}, Pr[i=1d π(xi) = π(yi)]= 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)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
부
@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 x1,x2,. . . ,xd {0,1,. . . , n-1} and any distinct y1,y2,. . . ,yd {0,1,. . . , n-1}, Pr[i=1d π(xi) = π(yi)]= 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)2}; (upper bound) Pr[min {π(X)}=π(x)] 2/k - 2/k + 1/(3kk).},
keywords={},
doi={},
ISSN={},
month={May},}
부
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 x1,x2,. . . ,xd {0,1,. . . , n-1} and any distinct y1,y2,. . . ,yd {0,1,. . . , n-1}, Pr[i=1d π(xi) = π(yi)]= 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)2}; (upper bound) Pr[min {π(X)}=π(x)] 2/k - 2/k + 1/(3kk).
ER -