Min-Wise Independence vs. 3-Wise Independence(Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
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_1,x_2,...,x_d ∈ {0,1,...,n - 1} and any distinct y_1,y_2,...,y_d ∈ {0, 1,...,n - 1}, Pr[Λ^d_<i=1> π(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)^2 }; (upper bound) Pr[min{π(X)} = π(x)] 2/√<K> - 2/k + 1/(3k√<K> ).
- 社団法人電子情報通信学会の論文
- 2002-05-01
著者
関連論文
- A General Construction of Min-Wise Independent Permutations(Special Section on Discrete Mathematics and Its Applications)
- Constructing an Optimal Family of Min-Wise Independent Permutations
- Min-Wise Independence vs. 3-Wise Independence(Special Section on Discrete Mathematics and Its Applications)
- Approximating the Maximum Weight of Linear Codes is APX-Complete(Special Section on Discrete Mathematics and Its Applications)
- On Lower Bounds for the Communication Complexity of Private Information Retrieval : Special Section on Cryptography and Information Security