Constructing an Optimal Family of Min-Wise Independent Permutations

概要

論文の詳細を見る
A family C of min-wise independent permutations is known to be a useful tool of indexing replicated documents on the Web. For any integer n > 0, a family C of permutations on [n] = {1, 2, ..., n} is said to be min-wise independent if for any (nonempty) X⊊ [n] and any x ⋳ X, Pr(min{π(X)}=π(x))=‖X‖^<-1> when π is chosen uniformly at random from C, where ‖A‖ is the cardinality of a finite set A. for any integer n > 0, it has been known that (1) ‖C‖≥1cm(n, n-1, ..., 2, 1)=e^<n-o(n)> for any family C of min-wise independent permutations on [n]; (2) there exists a polynomial time samplable C family of min-wise independent permutations on [n] such that ‖C‖ ≥ 4^n. However, it has been unclear whether there exists a min-wise independent family C such that ‖C‖=1cm(n, n-1, ..., 2, 1) for each integer n > 0 and how to construct such a family C of min-wise independent permutations for each integer n > 0 if it exists. In this paper, we shall construct a family Fn of permutations for each integer n>0 and show that Fn is min-wise independent and ‖Fn‖ =1cm(n, n-1, ..., 2, 1). Moreover, we present a polynomial time sampling algorithm for the family. Thus the family Fn of min-wise independent permutations is optimal in the sense of family size and is easy to implement because of its polynomial time samplability.
社団法人電子情報通信学会の論文
2000-04-25