Constructing an Optimal Family of Min-Wise Independent Permutations

Yoshinori TAKEI; Toshiya ITOH; Takahiro SHINOZAKI

Constructing an Optimal Family of Min-Wise Independent Permutations

Yoshinori TAKEI, Toshiya ITOH, Takahiro SHINOZAKI

Full Text Views

0

Cite this

Summary :

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|| lcm(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ⁿ. However, it has been unclear whether there exists a min-wise independent family C such that ||C|| = lcm(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 F_n of permutations for each integer n>0 and show that F_n is min-wise independent and ||F_n|| = lcm(n,n-1,. . . ,2,1). Moreover, we present a polynomial time sampling algorithm for the family. Thus the family F_n of min-wise independent permutations is optimal in the sense of family size and is easy to implement because of its polynomial time samplability.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.4 pp.747-755

Publication Date: 2000/04/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithms and Data Structures

Cite this

Copy

Yoshinori TAKEI, Toshiya ITOH, Takahiro SHINOZAKI, "Constructing an Optimal Family of Min-Wise Independent Permutations" in IEICE TRANSACTIONS on Fundamentals, vol. E83-A, no. 4, pp. 747-755, April 2000, doi: .
Abstract: 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|| lcm(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ⁿ. However, it has been unclear whether there exists a min-wise independent family C such that ||C|| = lcm(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 F_n of permutations for each integer n>0 and show that F_n is min-wise independent and ||F_n|| = lcm(n,n-1,. . . ,2,1). Moreover, we present a polynomial time sampling algorithm for the family. Thus the family F_n of min-wise independent permutations is optimal in the sense of family size and is easy to implement because of its polynomial time samplability.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_4_747/_p

Copy

@ARTICLE{e83-a_4_747,
author={Yoshinori TAKEI, Toshiya ITOH, Takahiro SHINOZAKI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Constructing an Optimal Family of Min-Wise Independent Permutations},
year={2000},
volume={E83-A},
number={4},
pages={747-755},
abstract={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|| lcm(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ⁿ. However, it has been unclear whether there exists a min-wise independent family C such that ||C|| = lcm(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 F_n of permutations for each integer n>0 and show that F_n is min-wise independent and ||F_n|| = lcm(n,n-1,. . . ,2,1). Moreover, we present a polynomial time sampling algorithm for the family. Thus the family F_n of min-wise independent permutations is optimal in the sense of family size and is easy to implement because of its polynomial time samplability.},
keywords={},
doi={},
ISSN={},
month={April},}

Copy

TY - JOUR
TI - Constructing an Optimal Family of Min-Wise Independent Permutations
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 747
EP - 755
AU - Yoshinori TAKEI
AU - Toshiya ITOH
AU - Takahiro SHINOZAKI
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2000
AB - 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|| lcm(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ⁿ. However, it has been unclear whether there exists a min-wise independent family C such that ||C|| = lcm(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 F_n of permutations for each integer n>0 and show that F_n is min-wise independent and ||F_n|| = lcm(n,n-1,. . . ,2,1). Moreover, we present a polynomial time sampling algorithm for the family. Thus the family F_n of min-wise independent permutations is optimal in the sense of family size and is easy to implement because of its polynomial time samplability.
ER -