A family of permutations ${\cal F$ of $[n]=\{1,2,\ldots ,n\}$ is $(\varepsilon,k)$-min-wise independent if for every nonempty subset $X$ of at most $k$ elements of $[n]$, and for any $x \in X$, the probability that in a random element $\pi$ of ${\cal F}$, $\pi(x)$ is the minimum element of $\pi(X)$, deviates from $1/|X|$ by at most $\varepsilon/|X|$. This notion can be defined for the uniform case, when the elements of ${\cal F}$ are picked according to a uniform distribution, or for the more general, biased case, in which the elements of ${\cal FF}$ are chosen according to a given distribution $D$.
It is known that this notion is a useful tool for indexing replicated documents on the web. We show that even in the more general, biased case, for all admissible $k$ and $\varepsilon$ and all large $n$, the size of ${\cal F}$ must satisfy $|{\cal F}| \geq \Omega\left(\frac{k}{\varepsilon^2\log(1/\varepsilon)}
\log n\right)$, as well as $|{\cal F}| \geq \Omega \left(\frac{k^2}{\varepsilon\log(1/\varepsilon)}
\log n\right)$. This improves the best known previous estimates even for the uniform case.
各種検索
サポート
ヘルプ