数理解析研究所講究録1093 巻 1999 年 74-80

74

A Polynomial Time Sampling Algorithm for an Optimal-Wise Independent Permutations
Family of${\rm Min}$TOSHIYA ITOH
titoh@ip.titech.ac.jp
Department of Information Processing .
Interdisciplinary Graduate School of Science and Engineering
Tokyo Institute of Technology
4259 Nagatsuta, Midori-ku, Yokohama 226-8502, Japan
TAKAHIRO SHINOZAKI
staka@ip.titech.ac.jp

1

Introduction

The Web [4] has grown exponentially for recent years and we have a huge amount of identical (oralmost identical) documents on the Web at present. When users wish to detect or filter those(almost) identical documents by the currently used indexing software [7], e.g., AltaVista, thismight cause them several undesirable problems –(1) indexing of those replicated documents
wastes expensive resources such as time and bandwidth; (2) most of users are not interested ingetting (almost) identical documents to their queries, etc.
To evaluate the performance of the indexing software, we need to formally define the notion
of “almost identical” between documents, however, any of the standard distances defined overstrings (e.g., Hamming distance [6] or Levenstien distance [1]) does not capture well our intuition
for this notion. In addition, these distances require the pairwise comparison of whole documents.
Thus in practice, this is infeasible for a large collection of documents and some sort of samplingfor each document is necessary. Now our problem can be reduced to a set intersection problem
with each documentby shingling process $[5, 2]$ . In the shingling process, we associate a set$D$ . In general, we can regard
as a set of natural numbers, i.e., there exists a natural number
for each document $D$ , where $[n]=\{1,2, \ldots, n\}$ .
in practical use) such that(
Then we can define a good measure (called resemblance [2]) to capture the notion of “almost
identical” between documents. The resemblance $r(A, B)$ of two documents and $B$ is defined as$r(A, B)=||s_{A}\cap s_{B}||/||s_{A}\cup s_{B}||$ , whereis the cardinality of a finite set . By experiments,
the resemblance is known to capture well the notion of “almost identical.” To compute $r(A, B)$ ,associated with $A,$ , respectively, and to evaluate
it suffices to consider the sets$\mathrm{P}\mathrm{r}(\min\{\pi(s_{A})\}=\min\{\pi(S_{B})\})$ when
, whereisis chosen uniformly at random fromthe set of all permutations on $[n]$ . Indeed, it is easy to show that
$S_{D}$$S_{D}$$n$$n\simeq 2^{64}$$S_{D}\subseteq[n]$

$A$

$A$

$||A||$$S_{A},$ $S_{B}\subseteq[n]$$B$$S_{n}$$S_{n}$$\pi$$\mathrm{P}\mathrm{r}(\min\{\pi(s_{A})\}=\min\{\pi(S_{B})\})=\frac{||S_{A}\cap S_{B}||}{||s_{A^{\cup S}B}||}=r(A, B)$.

(1)

Thus the resemblance of two documents can be easily estimated by keeping a sketch $[2, 3]$
of $D$ can be efficiently computed and is given by the fixedof each document $D$ . The sketch$( \min\{\pi_{1}(sD)\}, \min\{\pi_{2}(S_{D})\}, \ldots , \min\{\pi\ell(sD)\})$ for) independently(saysize list. To estimate $r(A, B)$ , we only count how many
chosen random permutations
however, it is unrealistic to choose uniformlyIn
practice,incommon.
andareelements
contains a huge number of permutations. Thus in the practicalat random from , because
and theoretical point of view, the goal of the paper is to construct a polynomial time samplable(smaller) family of permutations that has the property of equation (1).
$\mathrm{S}_{D}$$\ell$$\mathrm{S}_{D}=$$\pi_{1},$ $\pi_{2},$$\mathrm{S}_{A}$$\pi_{\ell}\in S_{n}$$\pi$$\mathrm{S}_{B}$$S_{n}$$\ldots,$$\ell\simeq 100$

$S_{n}$

75

Definition 1.1 (-wise independency [3]): We say th at
is a family of-wise independent permutations if for any (nonempty)
and any $x\in X,$ $\mathrm{P}\mathrm{r}(\min\{\pi(X)\}=\pi(x))=$when is chosen uniformly at random from C.
Broder, Charikar, Frieze, and Mitzenmacher [3] showed thathas the property of equation(1) if and only if it is $\min$ -wise independent.
Theorem 1.2 (lower bound [3]): For any in teger $n>0$ , letbe a family of min-wise
indepen dent permu ta tions. Thenand hence $||C||\geq e^{n-o(n}$ ).
$C\subseteq S_{n}$$\mathrm{m}\mathrm{I}\mathrm{n}$$\mathrm{m}\dot{\mathrm{l}}\mathrm{n}$$X\subseteq[n]$$||X||^{-1}$$\pi$$C\subseteq S_{n}$$C\subseteq S_{n}$$||C||\geq 1\mathrm{c}\mathrm{m}(n, n-1, \ldots, 2,1)$

Theorem 1.3 (upper bound [3]): For any integer $n>0$ , there exists a polynomial time sampla $ble$ family of $\min$ -wise independent permuta tionsuch th at.
$sC\subseteq S_{n}$$||C||\leq 4^{n}$

Theorem 1.4 (size-optimal family [8]): For any in teger $n>0$ , there exists a family ofm in-wise
independent permu tations
such th at $||F_{n}||=1\mathrm{c}\mathrm{m}(n, n-1, \ldots, 2,1)$ .
$F_{n}$$S_{n}$In this paper, we shall construct a polynomial time samplable family of permutations
and then show thatis $\min$-wise independent and.
$||F_{n}||=1\mathrm{c}\mathrm{m}(n, n-1, .

$F_{n}$

2${\rm Min}$.

$F_{n}\subseteq$., 2, 1)$

-Wise Independent Permutations

be a string. For each $k\in[n]$ , let $\mathcal{H}_{n_{)}k}=\{H\subseteq[n] : ||H||=k\}$ and, let. For each$x_{i}\in
H$$y\in[n]-\{x_{1,2}x,\ldots, X_{k}\}$ , we use:
and any}. For any
to denote the concatenation of and , i.e.,. For each$k\in[n]$ , let, whereand. Fromthe definition, it is obvious thatis an integer, becauseLet$\langle a_{1}, a_{2}, \ldots, a_{k}\rangle$$\mathcal{P}_{n,k}=$$\{\langle x_{1},x_{2}, \ldots,X_{k}\rangle\in[n]^{k} :x_{i}\neq x_{j}(i\neq j)\}$$H\in \mathcal{H}_{n,k}$$P_{n,k}^{H}=\{\langle_{X_{1},x}2, \ldots,x_{k}\rangle\in$$\pi=\langle_{X_{1},x}2, \ldots, x_{k}\rangle\in’\rho_{n,k}$$\mathcal{P}_{n,k}$$\pi\# y$$\pi$$\pi\# y=\langle_{X_{1}}, x_{2,\ldots,k}x, y\rangle\in P_{n,k+1}$$y$$\alpha_{n,k}=\mathrm{l}\mathrm{c}\mathrm{m}(n, n-1, .

.., n-k+1)$$\beta_{n,k}=\alpha_{n,k}/\alpha_{n,k-1}$$\alpha_{n,0}=1$$\beta_{n,k}$$\beta_{n,k}=\frac{\alpha_{n,k}}{\alpha_{n,k-1}}=\frac{1\mathrm{c}\mathrm{m}(\alpha_{n,k1}-,n-k+1)}{\alpha_{n,k-1}}=\frac{(n-k+1)}{\mathrm{g}\mathrm{c}\mathrm{d}(\alpha n,k-1,n-k+1)}$

For any
to be

.

(2)

, let
and
.
$x_{j}=x_{j}’$if there exists an $i\in[k]$ such thatandfor each $i<j\leq k$
or $x_{j}=x_{j}’$ for each $j\in[k]$ . It is obvious thatthe total order. As for the intuition of ourconstruction for the $\min$-wise independent permutations, see [8].
$H\in \mathcal{H}_{n,k}$$F_{n,k}^{H}$$\pi=\langle x_{1,2}X, \ldots,x_{k}\rangle\in F_{n,k}^{H}$$\pi’=\langle_{X_{1}’,x_{2}’}, \ldots,X_{k}\rangle’\in \mathcal{F}_{n,k}^{H}$$\pi\preceq\pi’$$\mathrm{D}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{e}\preceq \mathrm{o}\mathrm{n}$$x_{i}<x_{i}’$$\preceq \mathrm{i}\mathrm{s}$$\underline{\mathrm{l}\mathrm{n}\mathrm{p}\mathrm{u}\mathrm{t}.}$$\underline{\mathrm{O}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}.}$$\underline{\mathrm{I}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{a}\mathrm{l}.}$Stage :$k$

An Integer $n>0$ .
A Family of Permutations.
, where denotes the null string.
, iterate the following:
For $k=0,1,$$\mathcal{F}_{n}(=F_{n,n})$$F_{n,0}=F_{n,0}^{\phi}=\{\langle\rangle\}$$\lambda$$..\mathrm{e}’ n-1$$\underline{\mathrm{C}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{I}\mathrm{f}\mathrm{y}\mathrm{I}\mathrm{n}\mathrm{g}\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{c}\mathrm{e}\mathrm{d}\mathrm{u}\mathrm{r}\mathrm{e}.}$, let
For eachaccording to the order$H\in \mathcal{H}_{n,k}$

enumerate every$i\in[m_{k}]$ , where $m_{k}=$ , arrange

and. For eachas follows:$F_{n_{)}k}^{H}=\{\langle_{X_{1},x}2, \ldots, x_{k}\rangle\in F_{n,k} :$\pi_{k}^{H}\in F_{n,k}^{H}$$\pi_{k,1,\pi_{k^{i}}}^{HH},2’\ldots$,$\preceq$, where: in the the array$f_{k}(H)=||F_{n,k}^{H}||$$\pi_{k,fk(H)}^{H_{*}}$The Array$C_{k}$$\ovalbox{\tt\small REJECT}_{(}^{2}\pi_{k,f_{k}}^{H_{1}}(H_{1})\pi’)k,fkH_{2},J\pi^{H_{1}}k,1\pi_{2\pi_{k}^{H_{m_{k}}}}\pi HkH1k,1^{k}k(mH_{m})$$C_{k}$

x_{i}\in H\}$.

Procedure: For each$i\in[f_{k}(H)]$ , and enumerat those$\tilde{\pi}_{k,1,||}^{H}$$\pi_{k,1}^{H}$, generatecopies of each$\beta_{n,k+1}$$H\in \mathcal{H}_{n,k}$$\mathrm{R}\mathrm{e}\mathrm{p}^{||\mathrm{C}\mathrm{a}}\mathrm{t}\dot{\mathrm{l}}\mathrm{n}\mathrm{g}$$e$$\beta_{n,k+1}$$\tilde{\pi}_{k,2\beta n,k+}^{H}1$$\cdot$.
...

$\tilde{\pi}_{k,\beta_{n},||}^{H},k+1$$\tilde{\pi}_{k,\beta_{n,k+1||}1}^{H}+$. .
$\cdot.\cdot$$\cdot.\cdot$. ..

$\dot{i}\in[m_{k}]$, arrange) $-1$ )$\pi_{k,f_{k}(}^{H}H$$\overline{\beta_{n,k+1}\mathrm{c}\mathrm{o}\mathrm{p}\mathrm{i}\mathrm{e}\mathrm{S}}\beta_{n},k+1^{\cdot}\mathrm{c}.0^{\cdot}\overline{\mathrm{p}\mathrm{i}\mathrm{e}\mathrm{s}}$For each$\pi_{k,i}^{H}\in \mathcal{F}_{n,k}^{H}$$\beta n,k+1+1||$$\pi_{k,2}^{H}$$\pi_{k,2}^{H}$$\pi_{k,1}^{H}$).

for each$\tilde{\pi}_{k,fk(H,||^{)}}^{H}\beta n,k+1$$\cdot.\cdot$$\pi_{k,j_{k}(}^{H}H$)$\beta_{n,k+1}\mathrm{C}\mathrm{O}^{\cdot}\mathrm{p}.\overline{\mathrm{i}}.\mathrm{e}\mathrm{s}$in the array$\tilde{\pi}^{H_{i}}k,1’\tilde{\pi}k,\dot{2},.,\tilde{\pi}_{k}H..H,:fk(H.\cdot)\beta n,k+1$

The Array.

copies ofas follows:$\pi_{k,i}^{H}\in F_{n,k}^{H}$$\tilde{\pi}_{k,(fk(}^{H}H$76$R_{k}$

as follows:$R_{k}$$\ovalbox{\tt\small REJECT}_{\tilde{\pi}_{k,f_{k}}^{H_{1}}\tilde{\pi}}^{\tilde{\pi}\tilde{\pi}}(H_{1}\tilde{\pi}^{H}k,1)\beta_{nk1}k,fk1H_{2}(H_{2}kH,)12\beta nk1\tilde{\pi}^{H}k,fk(mkHk,1mm_{k})\beta_{nk}1$

AppendIng Procedure: For each $H\in H_{n,k}$ , let $H^{\mathrm{c}}=[n]-H=\{y1, y_{2}, \ldots, yn-k\}$ and assume
for each:that $y_{1}<y_{2}<\cdots<y_{n-k}$ . Let$[fk(H)\beta n,k+1]\}$ , whereis the function that returns the residue when divides .
as follows:in the array,
For each $i\in[m_{k}]$ , arrange$\mathcal{G}_{n,k+1}^{H}=\{\pi_{k1,i}^{H}+$$b$$\mathrm{r}\mathrm{e}\mathrm{s}(a, b)$$\pi_{k}^{H}\dotplus_{1,1’ k+1,2}\pi H*,$

Finally, define$\dot{i}\in$$\pi_{k+1,i}^{H}=\tilde{\pi}_{k,i}^{H}\# y_{\gamma}\mathrm{e}\mathrm{s}(i-1,n-k)+1$$F_{n,k+1}= \bigcup_{H\in \mathcal{H}_{n}},g_{n,k+1}kH$$\ldots$$a$$A_{k+1}$$\pi_{k+1}^{H_{*}},fk(Hi)\beta_{n},k+1$, i.e., a collection of all entries in the array$A_{k+1}$.

as a permutation on $[n]$ in the natural manner,, we regard
For each$[n]$for each $i\in[n]$ .
in such a way thati.e., defines a permutation on, the following lemma and proposition are essential to
For our construction of.
andguarantee the $\min$ -wise independency of$\pi=\langle x_{12,\ldots,n}, Xx\rangle$$\pi\in \mathcal{F}_{n}$$\pi(x_{i})=\dot{i}$$\pi$$F_{n}\subseteq S_{n}$$\mathcal{F}_{n}$$||F_{n}||=1_{\mathrm{C}}\mathrm{m}(n, n-1, \ldots, 2,1)$

Lemma 2.1 [8]: For each $0\leq k\leq n-1$ , the following holds:(a)$\alpha_{n_{)}k}$is divisible by

Proposition 2.2 [8]: For each $0\leq k\leq n-1$ and each(a)$||r_{n)k}^{H}||=\alpha n,k/$;(b)$H\in \mathcal{H}_{n,k}$$||\mathcal{G}_{n,k1}^{H}+||=\alpha_{\mathrm{n}},k+1/$, the following olds:$\mathrm{h}$.

By the use of Lemma 2.1 and Proposition 2.2, we can show the following:

Theorem 2.3 [8]: For any in teger $n>0$ , the family of ermu tations.
dent an$.p$$d||F_{n}||=\alpha_{n,n}=\mathrm{l}\mathrm{c}\mathrm{m}(n, n-1, \ldots , 2, 1)$$F_{n}$

is $\min$ -wise indepen-

77

3

Polynomial Time Samplability

3.1

Overview of Our Polynomial Time Sampling Algorithm

We first describe the intuition behind our polynomial time sampling algorithm Samp.
For eachand each $x\in[n]$ , let
The following lemma plays an essential role to design the sampling algorithm Samp.
$H\in \mathcal{H}_{n,k}$$\mathcal{E}_{k+^{\mathrm{i}^{)}=}}^{(x}H\{\langle x_{12}, x, \ldots, Xk, x_{k1}+\rangle\in \mathcal{G}_{n,k+1}^{H} :Lemma 3.1 [8, Eq.(ll)]:$||\mathcal{E}_{k\mathrm{i}|}^{(H)}+x|=\alpha_{n,k+1}/\{(k+1)\}$for each$H\in \mathcal{H}_{n,k}$x_{k+1}=x\}$.

and each $x\in[n]$ .

Remark 3.2: For each $H=\{X_{1}, X_{2}, \ldots, X_{k}+1\}\in \mathcal{H}_{n,k+1}$ and each $x\in H$ , we define, i.e.,
is the set ofthat has $x\in H$ at
the $(k+1)$ -th (rightmost) position. Note that. So it follows from Lemma
3.1 thatcan be partitioned into $k+1$ setsof equal size.
$\mathcal{T}_{k+1}^{H}(x)=$$\{\langle\xi_{1}, \xi_{2}, \ldots, \xi k+1\rangle\in F_{n,k+1}^{H} :\xi_{k+1}=x\}$$\mathcal{T}_{k+1}^{H}(X)$$\pi\in \mathcal{F}_{n,k+1}^{H}$$\mathcal{E}_{k+1}^{(H-}\{x\},x)=\mathcal{T}_{k+1}^{H}(X)$$F_{n,k+1}^{H}$$\tau_{k+1}^{H}(X_{i})$For each $0\leq k\leq n-1$ , let
be the location ofwith respect to the total order, where $0\leq L_{k}(\pi)\leq\alpha_{n,k}/-1$ and. In Step , the algorithm
Samp randomly chooses $x\in[n]$ and sets
and $H_{1}=\{x\}$ . Assume that in Step , thealgorithm Samp keeps, and.
Let $\Gamma_{n,k+1}=(n-k)/\beta_{n,k+1}$ . Then from equation (2), we have that
$L_{k}(\pi)$$\pi\in \mathcal{F}_{n,k}^{H}$$L_{0}(\pi_{0})=L_{0}(\langle\rangle)=0$$\preceq \mathrm{o}\mathrm{n}\mathcal{F}_{n,k}^{H}$$0$$\pi_{1}=\langle x\rangle$$\pi_{k}=\langle X_{1}, X_{2}, \ldots , x_{k}\rangle\in \mathcal{F}_{n,k}^{H},$$k$$H_{k}=\{x_{1}, x_{2}, \ldots, x_{k}\}\in \mathcal{H}_{n,k}$$\Gamma_{n,k+1}=\frac{n-k}{\beta_{n,k+1}}=(n-k)\cdot\frac{\mathrm{g}\mathrm{c}\mathrm{d}(\alpha_{n,k},n-k)}{n-k}=\mathrm{g}\mathrm{c}\mathrm{d}(\alpha n,k, n-k)$$L_{k}(\pi_{k})$.

Let $H_{k}^{c}=[n]-H_{k}=\{y_{1}, y_{2}, \ldots , y_{n-k}\}$ and $y_{1}<y_{2}<\cdots<y_{n-k}$ . Partition
intoblocks, i.e.,of sizefor each $0\leq i\leq\Gamma_{n,k+1^{-}}1$ .
Recall our construction of the family . In Stage , we generatecopies of each entry$H_{k}^{c}$$\beta_{n,k+1}$$\Gamma_{n,k+1}$$H_{k,i}^{c}=\{yi\cdot\beta_{n,k+1}+1, y_{i}.\beta n,k+1+2, \ldots, y(i+1)\cdot\beta_{\hslash,k+}1\}$$k$$F_{n}$$\beta_{n,k+1}$

call
at theProcedure in Stage .
),) an allowable block forThus the sampling algorithm Samp randomly chooses
and sets $H_{k+1}=$
and, where $x_{k+1}=y$ .
As a next task, Samp needs to evaluate(see Figure 1). Let $\Delta_{k+1}(xk+1)$ be the location ofin the set $H_{k+1}=\{x_{1}, x_{2}, \ldots,Xk+1\}$ , where $0\leq\Delta_{k+1}(x_{k}+1)\leq k$ , when $x_{i}\in H_{k+1}$
are arranged in the increasing order, and let
be the location ofwith respect to the total orderon, where $0\leq\delta_{k+1}(\pi k+1)\leq\alpha_{n,k+1}/\{(k+$1)
total
the Classifying Procedure in Stage $k+1$ . Then it follows from Remark 3.2 that$\pi\in F_{n,k}^{H_{k}}$$H_{k,(L(}^{c}r\mathrm{e}\mathrm{S}k\pi_{k}$$k$$\mathrm{A}_{\mathrm{P}\mathrm{P}^{\mathrm{e}}}\mathrm{n}\mathrm{d}\mathrm{l}\mathrm{n}\mathrm{g}$$\Gamma_{n},k+1$$y\in H_{k,\gamma}^{c}\epsilon \mathrm{s}(Lk\mathrm{t}\pi k),\Gamma_{n},k+1)$$H_{k}\cup\{X_{k+1}\}\in \mathcal{H}_{n,k+1}$$\pi_{k+1}=\pi_{k}\# x_{k+1}\in \mathcal{F}_{n,k+1}^{H_{k+}}1$$L_{k+1}(\pi_{k}+1)$$x_{k+1}$$\pi_{k+1}\in \mathcal{T}_{k+1}^{H_{k+}}1(xk+1)$$\delta_{k+1}(\pi_{k+}1)$$\preceq$$\mathcal{T}_{k+1}^{H_{k+}}1(X_{k1}+)$$\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}\preceq \mathrm{a}\mathrm{t}$$L_{k+1}( \pi_{k+}1)=\frac{\alpha_{n,k+1}}{(k+1)(\begin{array}{l}nk+1\end{array})}$Note that every
there exists
is located at the$\Delta_{k+1}(x_{k+}1)+\delta_{k+1}(\pi_{k}+1)$.

has
as the rightmost element. Thus
to which
is appended at the Appending Procedure in Stage-th position in, it suffices for the evaluation of$\pi\in \mathcal{T}_{k+1}^{H_{k+}}1(X_{k1}+)$$\pi’\in F_{n,k}^{H_{k}}$.

$L_{k}(\pi_{k})$$x_{k+1}$$x_{k+1}$$F_{n,k}^{H_{k}}$$\pi\in \mathcal{T}_{k+1}^{H_{\mathrm{k}+}}1(X_{k+1})$$k$. Since$\delta_{k+1}(\pi k+1)$iff$\pi_{k}$to count

78

the number ofSo$\pi\in F_{n,k}^{H_{k}}$and $L_{k}(\pi)<L_{k}(\pi_{k})$ .

such thatand we finally have that$\mathrm{r}\mathrm{e}\mathrm{s}(L_{k}(\pi), \mathrm{r}_{n,k+1})=\mathrm{r}\mathrm{e}\mathrm{S}(Lk(\pi_{k}), \Gamma n,k+1)$$\delta_{k+\iota}(\pi_{k}+1)=\lfloor L_{k}(\pi_{k})/\Gamma_{n,k+1}\rfloor$$L_{k+1}( \pi_{k+}1)=\frac{\alpha_{n,k+1}}{(k+1)(\begin{array}{l}nk+1\end{array})}$.

$\Delta_{k+1}(xk+1)+\lfloor\frac{L_{k}(\pi_{k}\rangle}{\Gamma_{n,k+1}}\rfloor$.

It is obvious that by the use of $L_{k+1}(\pi_{k+}1)$ , the algorithm Samp can specify the allowable blockat the Appending Procedure in Stage $k+1$ .
for$\pi_{k+1}\in F_{n,k+}^{H_{k+1}}1$$H_{k+1,;}^{\mathrm{c}}$$\frac{\alpha_{n.k+1}}{(k+1)(\begin{array}{l}nk+1\end{array})}$$\frac{a_{n.k+1}}{(k+1)(\begin{array}{l}nk+1\end{array})}$$\frac{\alpha_{n.k+1}}{(k+1)(\begin{array}{l}nk+1\end{array})}$..
$\cdot$Figure 1: Evaluation of $L_{k+1}(\pi k+1)$

3.2

Description of the Algorithm

The following is the formal description of the sampling algorithm Samp for the optimal family
of $\min$-wise independent permutations.
An integer $n>0$ .
$\underline{\mathrm{l}\mathrm{n}\mathrm{p}\mathrm{u}\iota\cdot.}$$\underline{\mathrm{O}\mathrm{u}\mathrm{t}\mathrm{p}\mathrm{u}\mathrm{t}.}$$\pi\in F_{n}$.

$H_{0}=\phi$ , and $L_{0}(\pi_{0})=L0(\langle\rangle)=0$ .
Let$n-1$ , iterate the following:
Step : For $k=0,1,$$\underline{\ln i\mathrm{t}\mathrm{I}\mathrm{a}|\cdot.}$$\pi_{0}=\langle\rangle,$$k$$\ldots,$(1) Let $H_{k}^{c}=[n]-H_{k}=\{y_{1}, y_{2}, \ldots, y_{n-}k\}$ , where $y_{1}<y_{2}<\cdots<y_{n-k}$ , and partition, i.e., for each $0\leq i\leq\Gamma_{n,k+1^{-}}1$ , letinto $\Gamma_{n,k+1}=(n-k)/\beta_{n,k+1}$ blocks of size

$H_{k}^{c}$$\beta_{n,k+1}$.

$H_{k}^{c_{i}},=\{yi\cdot\beta n,k+1+1, yi\cdot\beta n,k+1+2, \ldots, y_{(+}i1)\cdot\beta n,k+1\}$(2) Compute$\mathrm{r}\mathrm{e}\mathrm{s}(L_{k}(\pi_{k}), \Gamma n,k+1)$

and choose$y\in H_{k,(Lk(\pi_{k}}^{c_{\mathrm{f}\mathrm{e}\mathrm{S}}}$) uniformly at random.
), $\Gamma+1$$n,k$(3) Let $x_{h+1}=y$ and set $H_{k+1}=H_{k}\cup\{X_{k+1}\}\in \mathcal{H}_{n,k+1}$ andin $H_{k+1}=\{x_{1}, x_{2}, \ldots , x_{k+1}\}$ when we(4) Let $0\leq\Delta_{k+1}(xk+1)\leq k$ be the location ofarrange $x_{i}\in H_{k+1}$ in the increasing order, and evaluate$\pi_{k+1}=\pi_{k}\# Xk+1\in F_{n,k1}^{H_{k+1}}+\cdot$$x_{k+1}$$L_{k+1}( \pi_{k}+1)=\frac{\alpha_{n,k+1}}{(k+1)(\begin{array}{l}\mathrm{n}k+1\end{array})}$.

$\Delta_{k+1}(x_{k+1})+\lfloor\frac{L_{k}(\pi_{k})}{\Gamma_{n,k+1}}\rfloor$

.

79

3.3

Analysis of the Algorithm

In this subsection, we analyze the time complexity of the sampling algorithm Samp and showthat the algorithm Samp runs in polynomial time in (not in the length of ).
To analyze the time complexity of the sampling algorithm Samp, we need to estimate thetime complexity of integer multiplication and integer division. For integers $m\geq\ell>0$ , we use
MULT $(m,p)$ to denote the number of bit operations required to multiply an $m$ bit integer by an
bit integer, and QUOTandto denote the number of bit operations required
to compute the quotient and residue, respectively, when dividing an $m$ bit integer by an bit
integer. We also use
to denote the number of bit operations required to compute
the greatest common divisorof $m$ bit integer and an bit integer.
Lemma 3.3: For any integer $m\geq\ell>0,$( $mm$ lg lg $m$ ).
Lemma 3.4: For any integer $m\geq\ell>0,$andIf$0<m\leq 2\ell$ , then QUOT $(m, \ell)=O$ (lglg ) and(lglg ).
Lemma 3.5: For any integer $m\geq\ell>0,$
If $0<m\leq 2\ell$,$(m,\ell)=O(\ell^{2}\ell\ell)$then EUC.
$n$$(m, \ell)$$\ell$$n$$\mathrm{R}\mathrm{E}\mathrm{S}(m,\ell)$$\ell$$\mathrm{E}\mathrm{U}\mathrm{C}(m,\ell)$$\ell$$(\mathrm{g}\mathrm{c}\mathrm{d})$$\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}(m, \ell)=o$$\mathrm{Q}\mathrm{U}\mathrm{O}\mathrm{T}(m, \ell)=O(m\ell)$$\ell\ell$$\ell$$\mathrm{R}\mathrm{E}\mathrm{S}(m,\ell)=O$$\mathrm{R}\mathrm{E}\mathrm{S}(m, \ell)=O(m\ell).$$\ell\ell$$\ell$$\mathrm{E}\mathrm{U}\mathrm{C}(m, \ell)=O(m\ell+\ell ^{2}\ell\ell).$To

the allowable blockforand the location $L_{k+1}(\pi_{k+}1)$ ofin
in Step , the algorithm Samp evaluates: (1)(4) $A_{n,k+1}=\alpha_{n,k}+1/\{(k+1)\}$ ; and (5). By definitions, we
can immediately derive the following proposition:
Proposition 3.6: For each $0\leq k\leq n-1$ , the following holds: (1);(2) $\alpha_{n,k}+1=\{\alpha_{n,k}\cdot(n-k)\}/\Gamma_{n,k+1;}$ and (3) $A_{n,k+1}=(A_{n,k}\cdot k)/\Gamma_{n,k+1}$ .
$A_{n,1}=1$ , and $L_{1}(\pi_{1})=0$ in Step
Since
, assume that in Step , the algorithm Samp
already has, and$An,k+1$ , and $L_{k+1}(\pi k+1)$ .
and recursively evaluates
In general,, andare bit integers, and $n-k,$, and are $n$ bitinintegers Step . Then the following holds for the time complexity of Samp in Step .
(1) Time complexity of evaluating
bit operations
are required (from Lemma 3.4).
(2) Time complexity of evaluating: $\mathrm{E}\mathrm{U}\mathrm{C}(n, n)=O(nn)$ bit operations are required (from Proposition $3.6-(1)$ and Lemma 3.5).
(3) Time complexity of evaluating( $n$ lg lg lg lg lg ) and
MULT $(n, n)=O$ ( $nn$ lg lg ) bit operations are required (from Proposition $3.6-(2)$and Lemmas 3.4 and 3.3), i.e., ( $nn$ lg lg ) bit operations are required.
(4) Time complexity of evaluating $A_{n,k+1}=\alpha_{n,k+1}/\{(k+1)\}:\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}(n, n)=O(nn$lg lg ) and QUOT $(n, n)=O(nn)$ bit operations are required (from Proposition 3.6(3) and Lemmas 3.4 and 3.3), i.e., ( $nn$ lg lg ) bit operations are required.
(5) Time complexity of evaluating
bit operations are required (from Lemma 3.4).
Thus in Step of the algorithm Samp, ( $nn$ lglg ) bit operations are required. Since thealgorithm Samp iterates this process times, we finally have the following theorem:
Theorem 3.7: For any $n>0$ , the algorithm Samp
ires ( $n^{2}n$ lg lg ) bit operations touniformly sample $\pi kom$ the (smallest) family of $\min$ -wise independent permuta tions .
$\mathrm{s}_{\mathrm{P}^{\mathrm{e}\mathrm{c}\mathrm{i}}\mathfrak{g}}r$$\pi_{k}\in \mathcal{F}_{n,k}^{H_{k}}$$H_{k+1,i}^{c}$$k$$F_{n,k+1}^{H_{k}}+1$$\pi_{k+1}$$\Gamma_{n,k+1;}(2)\mathrm{r}\mathrm{e}\mathrm{s}(L_{k}(\pi_{k}), \mathrm{r}_{n,k1}+);(3)\alpha_{\mathrm{n},k+1;}$$\delta_{k+1(\pi_{k}}+1)=\lfloor L_{k(\pi_{k}})/\Gamma_{n},k+.1\rfloor$$\Gamma_{n,k+1}=\mathrm{g}\mathrm{c}\mathrm{d}(\alpha_{n,k}, n-k)$$0$$\alpha_{n,1}=n,$$\alpha_{n,k},$$A_{n,k}$$\alpha_{n,k},$$A_{n,k}$$k$$L_{k}(\pi_{k})$$\alpha_{n,k+1},$$L_{k}(\pi_{k})$

$n$

$k$

$\Gamma_{n,k+1}$

$k$

$k$

$\mathrm{r}\mathrm{e}\mathrm{s}(L_{k}(\pi_{k}), \mathrm{r}_{n,k1}+):\mathrm{R}\mathrm{E}\mathrm{S}(n, n)=O(nn)$$\Gamma_{n,k+1}$$\alpha_{n,k+1}:\mathrm{Q}\mathrm{U}\mathrm{O}\mathrm{T}(n, n)=O$

$n$

$n$

$n$

$O$

$n$

$n$

$O$

$n$

$\delta_{k+1}(\pi k+1)=\mathrm{L}^{L_{k}}(\pi_{k})/\Gamma_{n,k+1}\rfloor:\mathrm{Q}\mathrm{U}\mathrm{O}\mathrm{T}(n, n)=O(nn)$

$O$

$k$

$n$

$n$

$re\mathrm{q}u$

$O$

$n$

$F_{n}$

80

Concluding Remarks

4

In this paper, we have constructed an optimal family of $\min$-wise independent permutationsin the sense of family size, and have shown that it is polynomial time samplable.
Let $k\in[n]$ be a fixed integer ( $k\simeq 1000$ in general). In the practical point of view, Broder,et.al. [3] defined the notion of “ -restricted $\min$ -wise independent.”$F_{n}$$k$is a family of k-wise independency [3]): We say that
Definition 4.1 (restricted$1\leq||X||\leq
k\leq n$ andsuch that-wise independent permu ta tion if for any
restricted
any $x\in X,$ $\mathrm{P}\mathrm{r}(\min\{\pi(X)\}=\pi(x))=||X||^{-1}$ when is chosen uniformly at random from C.
$C\subseteq S_{n}$$\mathrm{m}|\mathrm{n}$$X\subseteq[n]$$\mathrm{m}\dot{|}\mathrm{n}$$\pi$

In a way similar to Theorem 1.2, Broder, et.al. [3] derived the lower bound below for any familyof -restricted $\min$ -wise independent permutations.
$k$

Theorem 4.2 [3]: For any integer $n>0$ , let
independent permutations. Then$C\subseteq S_{n}$be a family of -restricted min-wise.
and hence$||C||\geq 1\mathrm{c}\mathrm{m}(k, k-1, \ldots , 2, 1)$$k$$||C||\geq e^{k-\circ}(k)$At present, we do not know whether for any integers $n>0$ and $0<k<n$ , there exists a familyof -restricted $\min$-wise (but not $\min$ -wise) independent permutations, but our construction of
the family of $\min$ -wise independent permutations could be applied to this.
$k$References[1] Aho, A.V., “Algorithms for Finding Patterns in Strings,” in Handbook of Theoretical Com(1990).
puter Science, Vol.A, MIT$\mathrm{P}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}/\mathrm{E}1_{\mathrm{S}\mathrm{e}\mathrm{V}}\mathrm{i}\mathrm{e}\mathrm{r}$[2] Broder, A.Z., On the Resemblance and Containment of Documents,” Proc. of Compression
and Complexity of Sequences, pp.21-29 (1998).

-Wise Independent[3] Broder, A.Z., Charikar, M., Frieze, A.M., and Mitzenmacher, M., “
Permutations,” Proc. of the Thirtieth Annual ACM Symposium on Theory of Computing,pp.327-336 (1998).
${\rm Min}$[4] Berners-Lee, T., Cailliau, R., Loutonen, A., Nielsen, H.F.., and Secret, A., “The World-Wide
Web,” Communications of the ACM, Vo1.37, No.1, pp.76-82 (1994).

[5] Broder, A.Z., Glassman, S.C., Manasse, M.S., and Zweig, G., “Syntactic Clustering of theWeb,” Proc. of the Sixth International World Wide Web Conference, pp.391-404 (1997).
[6] MacWilliams, F.J. and Sloane, N.J.A., “The Theory of Error-Correcting Codes,” 9th edition, North-Holland (1996).
[7] Souza, R.J., Krishnakumar, P., Ozveren, C.M., Simcoe, R.J., Spinney, B.A., Thomas, R.E.,
and Walsh, R.J., “GIGAswitch: A High-Performance Packet-Switching Platform,” DIGITAL Technical Journal, Vol.6, No.1, pp.9-22 (1994).

[8] Takei, Y., Itoh, T., and Shinozaki, T., “An Optimal Construction of Exactly Min-Wise
Independent Permutations,” Technical Report of IEICE, COMP98-62, pp.89-98 (1998).