Presentation	1998/11/20 An Optimal Construction of Exactly Min-Wise Independent Permutations YOSHINORI TAKEI, TOSHIYA ITOH, TAKAHIRO SHINOZAKI,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	A family of min-wise independent permutations C is known to be a useful tool of indexing replicated documents on the Web. For any integer n>0, a family of permutations C on{1, 2, ..., n}is said to be min-wise independent if for any(nonempty)X⊆{1, 2, ..., 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‖c‖>1cm(n, n-1, ..., 2, 1)=e^for any family of min-wise independent permutations C on{1, 2, ..., n}and that there exists a family of min-wise independent permutations C on{1, 2, ..., n}such that‖C‖<4^n. However, it has been unclear whether there exists a family of 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 of min-wise independent permutations C for each integer n>0 if it exists. In this paper, we shall construct a family of permutations F_n for each integer n>0 and show that F_n is min-wise independent and ‖F_n‖=1cm(n, n-1, ..., 2, 1). Thus our construction of F_n is optimal in the sense of family size.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	Min-Wise Independent Permutation Family / 1cm / p-adic Valuations / Resemblance
Paper #	COMP98-62
Date of Issue

Conference Information
Committee	COMP
Conference Date	1998/11/20(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	An Optimal Construction of Exactly Min-Wise Independent Permutations
Sub Title (in English)
Keyword(1)	Min-Wise Independent Permutation Family
Keyword(2)	1cm
Keyword(3)	p-adic Valuations
Keyword(4)	Resemblance
1st Author's Name	YOSHINORI TAKEI
1st Author's Affiliation	Department of Information Processing Tokyo Institute of Technology()
2nd Author's Name	TOSHIYA ITOH
2nd Author's Affiliation	Department of Information Processing Tokyo Institute of Technology
3rd Author's Name	TAKAHIRO SHINOZAKI
3rd Author's Affiliation	Department of Information Processing Tokyo Institute of Technology
Date	1998/11/20
Paper #	COMP98-62
Volume (vol)	vol.98
Number (no)	432
Page	pp.pp.-
#Pages	10
Date of Issue