数理解析研究所講究録1093 巻 1999 年 68-73

68

A Characterization of${\rm Min}$-Wise Independent Permutations Families
TOSHIYA ITOH\dagger

YOSHINORI TAKEI*-Wise Independent Permutation Family is an efficient tool to estimate similarity of documents. We present a characterization of Exact MWIPFs by size uniformity, which represents certain symmetryof the string representation of a family. Also, we present a general construction strategy which produce any
Exact MWIPF using this characterization.

Abstract. A${\rm Min}$

Introduction

1

Background-Wise Independency is recently defined, motivated by the need for efficient calcuThe notion oflation of “Resemblance” [1], which is an effective criterion of similarlity of two documents. Min-Wise
property defined for a family of permutations on $[n]=\{1,2, \ldots, n\}$ . In the paper
Independency-Wise Independency with some construction of[2], they presented definitions of various level of-Wise Independency is:
tight
and
class offundamental
permutation families. The mostset of all permutations on $[n]$ ) isDefinition 1.1 (Exact MWIPF [2]). We say that $F\subset S_{n}=$ (-Wise Independent Permutation Family if the following holds:
an Exact(1.1)$\forall X\subset[n](X\neq\phi),$,

1.1${\rm Min}$$\mathrm{i}\mathrm{s},\mathrm{a}$${\rm Min}$${\rm Min}$$\mathrm{t}\mathrm{h}\mathrm{e}$${\rm Min}$$\forall x\in X$$[ \pi\in \mathcal{U}\mathrm{P}\mathrm{r}_{F}[\min\pi(X)-arrow\pi(x)]=1/||X||]$

where $\pi\in uF$ means that is chosen uniformly at random from .
-Wise Permutation Families and we shall omit the rd
The rest of the paper focus on Exact
6,
theyobtained more explicit condition:
Theorem
[2]
proof
of
“Exact”. In the-wise independent if and only if theis
Theorem 1.2 (equivalent condition [2]). A subset $F$ of
following holds:$\forall 0\leq k<n\forall X\subset[n](||X||=n-k)\forall x\in X$(1.2)
and $\pi(x)=k+1]=1/((n-k))$ ].
[
$F$

$\pi$

${\rm Min}$$\mathrm{w}o$$S_{n}$$\pi\in \mathcal{U}\mathrm{p}\mathrm{r}_{F}[\pi([n]\backslash X)=\{1,2,$$\ldots,$$m\dot{i}n$$k\}$Lower and upper bounds of their size are:
Theorem 1.3 (lower bound of size [2], Theorem 1). For any integer $n>0$ , letis a-wise independent permutations. Thenofof$||C||$$m\dot{i}n$$||C||\geq e^{n-O}(n)$$mult_{\dot{i}}ple$$C\subseteq S_{n}$$1\mathrm{c}\mathrm{m}(n, n-1, \ldots, 2,1)$

be a family
and hence.

Theorem 1.4 (an optimal construction in the sense of size [6], Theorem 3.3). For any integer $n>$such that$n-$, there exists a family of $\min$ -wise independent permutations$\mathcal{F}\subseteq S_{n}$

$0$

$1,$

$\ldots,$$2,1)$$||\mathcal{F}||=1\mathrm{c}\mathrm{m}(n,$.

1.2 Main Results-Wise Independency (Theorem 1.2) as size
In Section 2, we reformulate the equivalent condition of
uniformity, using a certain string representation of permutations. In Section 3, we use the characterization to generalize the construction of Theorem 1.4 to a strategy which produce various Min-Wise${\rm Min}$

Independent Permutation Families (Theorem 3.5), and show that the strategy is enough general toany-Wise Independent Permutation Family (Theorem 3.6).
${\rm Min}$$\underline{\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{d}\mathrm{u}\mathrm{c}\mathrm{e}}$*Department of Information Processing, Tokyo Institute of Technology, 4259 Nagatsuta, Midori-ku, Yokohama 2268502, Japan. ytakeiQkis. . titech. . jp.
\dagger Department of Information Processing, Tokyo Institute of Technology, 4259 Nagatsuta, Midori-ku, Yokohama 226. titech. . jp.
8502, Japan.
$\mathrm{a}\mathrm{c}$$\mathrm{i}\mathrm{p}$$\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{o}\mathrm{h}\Phi \mathrm{i}\mathrm{p}$$\mathrm{a}\mathrm{c}$

69

1.3

Notations and Definitions
In this paper, MWIPF means Exact-Wise Permutation Family.
We interpretas the set of strings:${\rm Min}$$S_{n}$(1.3)$S_{n}=\{\pi=\langle x_{1}, \ldots, x_{i}, \ldots, x_{n}\rangle|x_{i}\in[n], x_{i}\neq x_{j}(\dot{i}\neq j)\}$where,$\pi=\langle x_{1}, \ldots, x_{i}, \ldots, x_{n}\rangle$

represents the permutation

subsets $L_{k}(H)$ and $M_{k}(x)$ of$S_{n}$:. For each$\pi$$\{H\subset[n]|||H||=k\}$ , the collection of all size-k subsets of $[n]$as:$[n]\ni x_{i}\vdasharrow\dot{i}\in[n]$. We put

Then a subset $F$ of$S_{n}$$:=$

and $x\in[n]$ , define$H\in \mathcal{H}_{n,k}$

(1.4)
(1.5)

$L_{k}(H):=\{\langle x_{1}, \ldots, x_{k}, \ldots, x_{n}\rangle\in S_{n}|\{_{X_{1}}, \ldots, x_{k}\}=H\}$$M_{k}(x):=\{\langle x_{1}, \ldots, x_{k}, \ldots, x_{n}\rangle\in S_{n}|x_{k}=x\}$$f\ell_{n,k}$.

decomposes into sum of disjoint subsets:$F= \prod_{k}H\in?t_{n},(F\cap Lk(H))=\prod_{H\in \mathcal{H}_{n},k\xi\in[}\prod_{n]\backslash H}(F\cap L_{k}(H)\cap M_{k+1}(\xi))$

We define the set of first-k substrings of

.

(1.6)

$S_{n}$$S_{n,k}:=\{\pi=\langle x_{1}, \ldots, x_{i}, \ldots, x_{k}\rangle|x_{i}\in[n], x_{i}\neq x_{j}(\dot{i}\neq j)\}$$(0\leq k\leq n)$

(1.7)

.

(1.8)

and define the first-k substring oprators for $0\leq k\leq\ell\leq n$ :$\varphi_{k}^{l}$2:$S_{n},\ell\ni\langle x_{1},$$\ldots$,$x_{k},$$\ldots,$$x_{l}$)$-langle x_{1}, \ldots, x_{k}\rangle\in S_{n,k}$Characterization of MWIPF by Size Uniformity

Using the above definitions, we obtain a reformulation of Theorem 1.2, which characterizes MWIPF
by certain symmetry of size of subsets in the string representation:
Theorem 2.1. A subset $F$ of$S_{n}$

is a MWIPF if and only if{ $|F\cap L_{k}(H)\cap M_{k+1}(\xi)||=||F||/((n-k))$for all $0\leq k<n,$$H\in H_{n,k},$ $\xi\in[n]\backslash H$(2.9)

Though it is merely a direct translation of Theorem 1.2, it gives an explicit goal when we try toconstruct a MWIPF. So we shall emphasize this characteristic of MWIPFs, calling it size uniformity.

3

A General Construction of MWIPF

3.1

Informal Description of the Strategy

We sketch basic strategy of the general(see Figure 1). First, we start with the replicated, wherenull strings
is the cardinality of the set to produce. Then we iterate stages consistof classifying and appending, as in the former construction [6], but allowing more general appending
rather than the cyclic appending. Heredenotes a map which appends each element of
to each string of. In Subsection 3.4 we will discuss what is admissible as
to output a
MWIPF. Then we regard that for given constant and $C$ (under the condition is possible value
as cardinality of a MWIPF), when we fix a sequence of admissible subroutines’ we
get a construction of MWIPF. In Theorem 3.5, we shall show the strategy produces a MWIPF for
all combination of admissible appending maps.
Set theoretical notations $F,$ are too informal since they contain multiple elements. In what
follows, we reformulate each procedure to avoid confusion.
$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{S}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$C$$C\cdot\langle\rangle$$[n]\backslash H$$\mathrm{A}\mathrm{p}_{n,k[C]}^{H}$$F_{n,k}^{H}$$\mathrm{A}\mathrm{p}_{n,k[C]}^{H}$

$n$

$C$

$(\mathrm{A}\mathrm{P}_{n,k}^{H}[C])^{0\leq}H\in k\mathcal{H}<n_{k}n,$$\mathcal{G}$70
Figure 1: General strategy

Formulation of Replicating, let
For an arbitrary subset of
3.2

$S$

$\mathfrak{M}(S)$$S_{n,k}$denote the free$\mathbb{Z}$-module generated by$S$:(3.10)$\mathfrak{M}(S):=\{\mathrm{x}=\sum_{\sigma\in s^{a}}(\sigma)\sigma|a(\sigma)\in \mathbb{Z}\}$

are nonnegative, it is identified with a so-called
When all of coefficents of an element
represent multiplicity of in . If all of its coefficients are either“multiset” and each coefficent
or 1, they represent the characteristic function of a “genuine” subset of . To represent these,situations, we define subsets offor$\mathrm{x}\in \mathfrak{M}(S)$$a(\sigma)$$\sigma$$\mathrm{x}$

$S$

$0$

$\mathfrak{M}(S_{n,k})$$p,$ $q\in \mathbb{Z}$$\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}[p, q]_{k}:=\{\mathrm{x}=\sum_{\sigma\in s_{n,k}}a(\sigma)\sigma|a(\sigma)\in \mathbb{Z},p\leq a(\sigma)\leq q\}$then$\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}[\mathrm{o}, \infty]_{k^{1}}(\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}[0,1]k)$represents the collection of all multisets over,

(3.11)$S_{n,k}$(resp. genuine).
subsets ofIn these cas es the sum of all coefficients coincides with the cardiality of its (multi)set interpretation.
as:
So we define the weight of an element of$S_{n,k}$$\mathfrak{M}(S_{n,k})$$w_{k}( \sum_{k\sigma\in S_{n}},a(\sigma)\sigma):=\sum_{\sigma\in s_{nk}},a(\sigma)$

The substring operator$\Phi_{k}^{l}$:$\varphi_{k}^{\ell}$(3.12)

induces the linear map:$arrow$$\mathfrak{M}(Sn,k)(v$$\mathfrak{M}(sn,l)\mathrm{u}$(3.13)$\mapsto*$$\sum_{\mathcal{T}\in s_{n,t}}b(\mathcal{T})\varphi_{k(\tau)=}\ell\sigma\in s_{n}\sum,k(_{\tau:\varphi_{k}^{t}()}\sum_{\mathcal{T}=\sigma}b(_{\mathcal{T}}))\sigma$$\sum_{\tau\in S_{n}\ell},b(\tau)_{\mathcal{T}}$for $0\leq k\leq\ell\leq n$ . Obviously$\Phi_{k}^{t}$preserves weight:$w\ell(\mathrm{x})=w_{k}(\Phi_{k}^{\ell}(\mathrm{X}))$

1In this case, the inequality on$a(\sigma)$$(_{\mathrm{X}}\in \mathfrak{M}(S_{n},\ell))$

is should be read as $0\leq a(\sigma)<\infty$ .

(3.14)

71

3.3

Formulation of Classifying

The direct decompsition formula (1.6) is extended to$\mathfrak{M}(S_{n,k})$:.

(3.15)$\mathfrak{M}(S_{n,k})=H\in\bigoplus_{n,k}\mathfrak{M}(\varphi_{k}^{n}(L_{k}(H)))=\oplus\oplus \mathfrak{M}(\varphi_{k}^{n}+1(L_{k}\mathcal{H}H\in \mathcal{H}n,k\xi\in[n\mathrm{J}\backslash H(H)\cap M_{k+1(\xi})))$We define the projections:$\Psi_{k}^{H}$:$arrow$$\mathfrak{M}(Sn,k)(v$$\mathfrak{M}(\varphi_{k}^{n}(L_{k(H)))}(v$(3.16)$-+$$\sum_{\sigma\in s_{\mathcal{R},k}}a(\sigma)\sigma$$\sigma\in\varphi_{k}^{n}(Lk(H\sum_{))}a(\sigma)\sigma$

and$\psi_{k+1}^{H,\xi}$:$\mathfrak{M}(S_{n,k+1})$$arrow$$\mathfrak{M}(\varphi_{k+1}^{n}(Lk(H)\cap Mk+1(\xi)))$

$(v$

$(v$

$rightarrow$$\sigma\in S_{n,k}\sum_{+1}a(\sigma)\sigma$$\sigma\in(L_{k}(\sum_{\varphi_{k+1}^{n}H)\mathrm{n}M_{k}1(+\xi))}a(\sigma)\sigma$(3.17),

respectively. Taking the projection
is exactly “classifying” in this setting. To represent the notionof size uniformity, we add some more definitions. For $C\in \mathbb{Z}>0$ and ach $0\leq k<n,$ $H\in H_{n,k}$ ,, define subs ofas:$\Psi_{k}^{H}$$e$$\xi\in[n]\backslash H$$\mathfrak{M}(S_{n,k+1})$$e\mathrm{t}\mathrm{s}$

UNIF

.

(3.18)$[C]_{k+1}^{H}’\xi:=\{\mathrm{x}\in \mathfrak{M}(S_{n,k+1})|w_{k+1}(\psi^{H\xi}k\dotplus_{1(}\mathrm{x}))=C/((n-k))\}$

Then put$\mathrm{U}\mathrm{N}|\mathrm{F}[c]_{k+1}$$\cup \mathrm{N}\mathrm{l}\mathrm{F}[C]\leq k$$:=$$\bigcap_{H\in H_{n,k}}\bigcap_{\xi\in[n}]\backslash H\cup \mathrm{N}\mathrm{l}\mathrm{F}[c]^{H}k+’ 1\xi$$:=$$\bigcap_{0\leq}i\leq k(\Phi_{i}^{k})^{-1}(\cup \mathrm{N}\mathrm{l}\mathrm{F}[c]_{i})$,(3.19),(3.20)

respectively. Here we put.
Using these settings, we obtain a reformulation of Theorem 2.1.
Proposition 3.1. An
represent a MWIPF without multiple elements of size $C$ if and only$\mathrm{U}\mathrm{N}\mathrm{I}\mathrm{F}[\mathit{0}]_{0}:=\{C. \langle\rangle\}$$\mathrm{x}\in \mathfrak{M}(S_{n})$if$\mathrm{x}\in$

MULT$[0,1]_{n}\cap \mathrm{U}\mathrm{N}\mathrm{I}\mathrm{F}[C]\leq n$.

3.4

Formulation of Appending
An “Appending” is a corresponding rule from inputs)

to
outputssuch that. But we are interested))
in rules only those which are admissible as processes to produce MWIPF. They need not care about
inputs violating uniformit, of ealier stages, while they should guarantee that their outputs satisfy size
uniformity with respect to this stage. This leads us to the following definition of classes of maps:$b(\tau)\tau\in \mathfrak{M}(\varphi_{k}^{n}(L_{k}(H)))$$\mathrm{y}=\sum_{\mathcal{T}\in(L(}\varphi_{k+1}^{n}kH$$\mathrm{x}=\sum_{\sigma\in\varphi_{k}^{n}(L_{k}(H}$)$)^{a(}\sigma$$\sigma\in \mathfrak{M}(\varphi_{k}^{n}(L_{k}(H)))$$\Phi_{k}^{k+1}(\mathrm{y})=\mathrm{x}$$\mathrm{y}$Definition 3.2 $(AP[C]^{H}k)$ .
$AP[C]^{H}k:=\{$$\mathrm{A}\mathrm{P}_{k}^{H}$:$\Psi_{k}^{H}(\cup \mathrm{N}|\mathrm{F}[C]_{\leq k}\cap \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}[\mathrm{o}, \infty]_{k})arrow \mathfrak{M}(\varphi_{k+1}^{n}(Lk(H)))$$|$$\mathrm{A}\mathrm{P}_{k}^{H}(\sum\sigma\in\varphi^{n}k(L_{k}(H))a(\sigma)\sigma)=\sum\xi\in[n_{L}]\backslash Hb(a, \sigma\sigma\in\varphi_{k((H))}^{n}k’\xi)\langle\sigma\xi\rangle$,(3.21)(i),(ii) $\forall\xi\in[n]\backslash H[\sum_{\sigma\in\varphi_{k}^{n}}(Lk(H))a,\xi)b(\sigma,=C/((n-k))]$ ,$\forall\xi\in[n]\backslash H,\forall\sigma\in\varphi_{k}^{n}(L_{k}(H))[b(a, \sigma, \xi)\in \mathbb{Z}\geq 0]$(iii)$\forall\sigma\in\varphi_{k}^{n}(L_{k}(H))[\sum_{\xi\in[n]\backslash }Hb(a, \sigma, \xi)=a(\sigma)]$

$\}$

72

Figure 2:$\mathrm{C}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{A}\mathrm{p}[c]_{k}H$

.

:

:

..

$\cdot$$\cdot$$C/$$\xi_{n-k-1}$:$\mathrm{f}_{\cap}$$a(\sigma_{n!/(k}n-)!)\{$

By definitions $(3.11),(3.18)$ and (3.13) the above conditions
(i)
(ii)
(iii)

$\Leftrightarrow$$\Leftrightarrow$$\Leftrightarrow$

(a):
(b):
(c):

$(\mathrm{i}),(\mathrm{i}\mathrm{i})$and (iii) are equivalent to:$\mathrm{A}\mathrm{P}_{k}^{H}(\mathrm{x})\in \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}[0, \infty]k+1$’

for all$\psi_{k+1}^{H,\xi}(\mathrm{A}\mathrm{P}_{k(\mathrm{x})}^{H})\in \mathrm{U}\mathrm{N}\mathrm{l}\mathrm{F}[\mathit{0}]^{H}k+’ 1\xi$$\xi\in[n]\backslash H$(3.22),.

$\Phi_{k}^{k+1}(\mathrm{A}\mathrm{p}_{k}H(\mathrm{x}))=\mathrm{x}$In addition, we define the following subclass to exclude rules those which produce “MWIPF withmultiple elements”:

Definition 3.3$(\mathcal{R}AP[C]^{H}k)$.

$\mathcal{R}AP[C]_{k}H:=\{A\in AP[C]^{H}k|A$(iv)

Example 3.4
an element of$(\mathrm{C}\mathrm{y}\mathrm{C}\mathrm{l}\mathrm{e}\mathrm{A}\mathrm{P}[c]_{k}H)$$\mathcal{R}AP[C]^{H}k$whensatisfiesand$(\mathrm{i}),(\mathrm{i}\mathrm{i}),(\mathrm{i}\mathrm{i}\mathrm{i})$$[\mathrm{x}\in \mathrm{M}\cup \mathrm{L}\mathrm{T}[0, (n-k)!]_{k}\Rightarrow A(\mathrm{x})\in \mathrm{M}\cup \mathrm{L}\mathrm{T}[0, (n-k-1)!]_{k}+1]\}$. For all $0\leq k<n$ and$C\in \mathbb{Z}_{\geq 0}$, theis divisible by $(n-k)$ .
$H\in \mathcal{H}_{n,k}$$\mathrm{f}\mathrm{o}\mathrm{U}\mathrm{o}\mathrm{w}\mathrm{i}\mathrm{n}\mathrm{g}$map(3.23)$\mathrm{C}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{A}\mathrm{p}[c]^{H}k$isrespectively;
and a numbering oflater set for$[n]\backslash
H=\{\xi_{0},\ldots\xi
n-k-1\}$
the
of
from
(numberingand(possiblylist each of with multiplicity
convenience). For the input, the numberzero) in a column. By the assumption that input is in$Descript\dot{i}on$of$\mathrm{C}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{A}\mathrm{p}[c]_{k}H$. Fix a numbering of$[n]\backslash H$$\varphi_{k}^{n}(L_{k}(H))$$0$$\varphi_{k}^{n}(L_{k}(H))=\{\sigma_{1}, \ldots, \sigma_{n!/(}k)!\}n-$$a(\sigma_{i})$$\sigma_{i}$$\mathrm{x}=\sum_{\sigma\in\varphi_{k}^{n}}(Lk(H))^{a(}\sigma)\sigma$$\Psi_{k}^{H}(\cup \mathrm{N}\mathrm{l}\mathrm{F}[c]\leq k)\subset\Psi_{k}^{H}(\mathrm{U}\mathrm{N}\mathrm{I}\mathrm{F}[c]_{k})$$\mathrm{x}$of rows is $\sum_{i}a(\sigma_{i})=wk(\mathrm{x})=\sum_{x}\in Hw_{k(\psi^{H}(\mathrm{X}}k\backslash \{x\},x))=k\cdot C/((\gamma\iota-(k-1)))=c/$$\xi_{n-k-1},$, i.e., fill theThen create the second column by the cyclic sequence
repeats
cycle
the
2).
Note
(Figureby
row of the second column
th.at, since the number of row $C/$ is divisible byexactly $C/((n-k))$ times and ends with, and setto,theoccurence of pair
set
and
of
each
.
For
$n-k$
the period. Then it is easy to see thatto the output$\xi_{0},$$\xi_{1},$$\xi_{0},$$\xi 1,$$\ldots,$$\xi_{0},$$\xi_{(r}\mathrm{m}\mathrm{o}\mathrm{d} (n-k))$$r\mathrm{t}\mathrm{h}$$\ldots$$\ldots,$$\xi_{n-k-1}$$\xi_{n-k-1}$$\sigma_{i}$$\sigma_{i},$$\xi_{j}$$\xi_{j}$$b(a, \sigma_{i}, \xi_{j})$$\mathrm{C}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{A}\mathrm{p}[c]_{k}H$$\mathrm{A}\mathrm{P}_{k}^{H}(\mathrm{x})$$\mathrm{y}=\sum_{\xi\in[n}]\backslash H,\sigma\in\varphi_{k}(Lk(H))bn(a, \sigma, \xi)\langle\sigma\xi\rangle$$\in \mathcal{R}AP[C]_{k}^{H}$.

$\square$

The General Construction
Now we are ready to describe the general strategy to produce multiplicty-free MWIPFs of specificsize:aTheorem 3.5. Let $n>0$ be an integer and let $0<C\leq n!$ be ana sequence of $append\dot{i}ng$ maps.
Define theofas follows:
sequence

3.5$\dot{i}ntegerwh_{\dot{i}C}h\dot{i}S$$\mathrm{l}\mathrm{c}\mathrm{m}(n, n-1, \ldots , 1)$$mult_{\dot{i}}ple$$(\mathrm{A}\mathrm{P}_{k}^{H}\in \mathcal{R}AP[C]_{k}H)_{H}0\leq k\in \mathcal{H}<n_{k}n,\cdot$$F_{\dot{i}X}$$(\mathrm{x}_{k}\in \mathfrak{M}(S_{n,k}))^{n}k=0$

(1):
(2):

$\mathrm{x}_{0}:=c\cdot\langle\rangle$$\mathrm{x}_{k+1}:=\sum_{n}H\in \mathcal{H},k\mathrm{A}\mathrm{p}_{k}^{H}(\Psi_{k}H(\mathrm{X}k))$$(0\leq k<n)$(3.24)

73

then,$\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}[0,1]_{n}\cap\cup \mathrm{N}\mathrm{l}\mathrm{F}[\overline{C}]\leq n’\dot{i}.e.,$

Proof. Note thatthe definition of$\mathrm{x}_{n}$$\mathrm{x}_{n}$$C$

for all (cf. [6] Lemma 31or [2] Theorem 6). If, then it is easily checked that$c_{/}’((n-k))\in \mathbb{Z}$$\mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}[0, (n-k)!]_{k}$3.6

is an element offor all $(0\leq k\leq n)$ . Especially,
represent an Exact MWIPF of size without multiple elements.

$\mathrm{x}_{k}\in \mathrm{U}\mathrm{N}\mathrm{I}\mathrm{F}[c]_{<k}\cap \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}[0, (n-k)!]_{k}$$k$$\mathrm{x}_{k}\in \mathrm{U}\mathrm{N}\mathrm{l}\mathrm{F}[C]\leq k^{\cap}$$\mathrm{x}_{k+1}\in \mathrm{U}\mathrm{N}\mathrm{I}\mathrm{F}[C]_{\leq}k+1\cap \mathrm{M}\mathrm{U}\mathrm{L}\mathrm{T}[0, (n-(k+1))!]_{k+1}$$\prime \mathcal{R}AP[C]^{H}k$.

by$\square$Completeness of the Construction

Indeed, the strategy produce any MWIPF under suitable conmbination of appending maps.

Theorem 3.6. Let be a positive integer and let $C>0$ be a multiple of. If
represents a MWIPF without multiple elements of size , then there exist a sequence ofappending map
such that:as in Theorem 3.5, then.
if we define$n$$\mathrm{l}\mathrm{c}\mathrm{m}(n, n-1, \ldots , 1)$$C$$\mathrm{y}\in \mathfrak{M}(S_{n})$$(\mathrm{A}\mathrm{P}_{k}^{H}\in \mathcal{R}AP[C]_{k}H)_{H}^{0}\leq\in\mu_{n,k}k<n$$\mathrm{x}_{k}\in \mathfrak{M}(S_{n,k})(0\leq k\leq n)$

Proof. For each$k$$\mathrm{x}_{n}=\mathrm{y}$and $H$ , define
if$\psi_{k}^{H}\dotplus^{\xi}1(\mathrm{y}k+1)$$\sum$$\mathrm{z}=\Psi_{kk()}Hn\mathrm{o}\Phi \mathrm{y}$(3.25)$\mathrm{A}\mathrm{P}_{k}^{H}(\mathrm{z}):=\{$ $\xi\in[n]\backslash H$$\mathrm{C}\mathrm{y}\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{A}_{\mathrm{P}}[C]_{k}^{H}(\mathrm{z})$and check that4$\mathrm{A}\mathrm{P}_{k}^{H}\in \mathcal{R}AP[C]^{H}k$. Then checkotherwise.

$\mathrm{x}_{k}=\Phi_{k}^{n}(\mathrm{y})$inductively.

口Concluding Remarks

In this paper, we reformulated a characterization of MWIPF as
uniformity, then presented astrategy to produce subsets of , which conform the output set to size uniformity. The strategy gives
a construction of MWIPF when one fix a choise of appending maps. On the other hand, by suitablechoise of appending maps, it produce any MWIPF. Thus the strategy is a surjection from the set of all
combination of appending maps to the set of all MWIPFs. This means that we may understand thatcharacteristic of a MWIPF is consist of local one (characteristic of each appending map) and global
one (combination of appending maps).
For practical apprications such as estimating document similarity, smaller family size and effecient
sampling are more desiable than exactness of-Wise Independency. In [2], they presented a numberof possible relaxized versions of MWIPF ( -restrict , approximat , biased distribution, etc.) for
this purpose. Indyk [4] presented a construction strategy of approximately-Wise Independent
Permutation Families based on families of hash-functions, which is useful for the derandomization of
the RNC algorithm [3]. Then it would be a problem: “For these relaxied versions of MWIPFs, arethere analogs of the generic construction strategy?”$S\dot{i}ze$$S_{n}$${\rm Min}$$k$$e\mathrm{d}$$e\mathrm{d}$${\rm Min}$

References[1] Broder, A.Z., On the Resemblance and Containment of Documents,” Proc. of Compression andComplexity of Sequences, pp.21-29 (1998).
[2] Broder, A.Z., Charikar, M., Frieze, A.M., and Mitzenmacher, M., “-Wise Independent Permutations,” Proc. of the Thirtieth Annual ACM Symposium on Theory of Computing, pp.327-336(1998).
[3] Broder, A.Z., Charikar, M., and Mitzenmacher, M., “A Derandomization Using-Wise Independent Permutations” RANDOM’98, pp. 15-24 (1998).
${\rm Min}$${\rm Min}$[4] Indyk, P. “A Small Approximately-Wise Independent Family of Hash Functions”, SODA’99,
pp. 454-456 (1999).
[5] Shinozaki, T., Itoh, T. “A Polynomial Time Sampling Algorithm for an Optimal Family of MinWise Indep.endent Permutations”, These proceedings.
Optimal Construction of Exactly[6] Takei, Y., Itoh, T., Shinozaki, T. “-Wise Independent
Permutations”, Technical Report of IEICE, COMP98-62, pp.89-98 (1998).
${\rm Min}$$\mathrm{A}\mathrm{n}\backslash$${\rm Min}$