| 講演抄録／キーワード |
| 講演名 |
2006-03-23 11:05
ε-近似k-制限最小値独立置換族のサイズの下界
○伊東利哉・永谷達也（東工大） |
| 抄録 |
（和） |
最小値独立置換族(およびその拡張概念である$\varepsilon$-近似$k$-制限最小値独立置換族)は，インターネット上に存在する多数の類似した文書の特定に有用であることが知られており，これまでにそれらの構成法，置換族のサイズに関する(非)構成的上界・下界が数多く示されている．ここで，任意の整数$n>0$に対し，集合$[1,n]=\{1,2,\ldots,n\}$上の置換全体の集合を$S_{n}$とするとき，置換族${\cal F} \subseteq S_{n}$が$\varepsilon$-近似$k$-制限最小値独立であるとは，任意の(空でない)部分集合$X \subseteq [1,n]$ (ただし$\|X\|\leq k$)と任意の$x \in X$に対し，置換$\pi \in {\cal F}$を一様且つ無作為に選んだ場合，$|\Pr_{\pi \in {\cal F}} [\min\{\pi(X)\}=\pi(x)] - 1/\|X\|| \leq \varepsilon/\|X\|$が成り立つことを言う(ただし，$\|A\|$は有限集合$A$の要素数を表すものとする)．これまでに$\varepsilon$-近似$k$-制限最小値独立置換族${\cal F} \subseteq S_{n}$のサイズに関して，以下のことが知られている:
(構成的上界) $\|{\cal F}\|= 2^{4k+o(k)}k^{2 \log \log (n/\varepsilon)}$;
(非構成的上界) $\|{\cal F}\|= O(\frac{k^{2}}{\varepsilon^{2}} \log (n/k))$;
(下界) $\|{\cal F}\|=\Omega(k^{2}(1-\sqrt{8 \varepsilon}))$．
本論文では，まず始めに完全グラフの多色枝塗りに関する(一般化された)ラムゼー数の上界を評価し，さらに代数的手法を用いることで，より厳密な
$\varepsilon$-近似$k$-制限最小値独立置換族${\cal F} \subseteq S_{n}$の
サイズの下界$\|{\cal F}\|=\Omega (k \sqrt{\frac{1}{\varepsilon}\log (n/k)})$を導出する． |
| （英） |
A family ${\cal F}$ of min-wise independent permutations is known to be a useful tool~of~indexing replicated documents on the Web. For any integer $n>0$, let
$S_{n}$ be the family of all~permutations on $[1,n]=\{1,2,\ldots, n\}$. For any integer $k \in [1,n]$ and any real $\varepsilon >0$, we say that a family ${\cal F} \subseteq S_{n}$ of permutations is $\varepsilon$-approximate k$-restricted
min-wise independent if for any (nonempty) $X \subseteq [1,n]$ such that
$\|X\| \leq k$ and any $x \in X$, $|\Pr [\min \{\pi(X)\} = \pi(x)]- 1/\|X\| |\leq
\varepsilon/\|X\|$, when $\pi$ is chosen from ${\cal F}$ uniformly at random (where $\|A\|$ is the cardinality of a finite set $A$). For the size of families ${\cal F} \subseteq S_{n}$ of $\varepsilon$-approximate $k$-restricted min-wise independent permutations, the following results are known: For any integer $k\in [1,n]$ and any real $\varepsilon > 0$, (constructive upper bound)
$\|{\cal F}\|=2^{4k+o(k)}k^{2 \log \log (n/\varepsilon)}$; (nonconstructive upper bound) $\|{\cal F}\|=O(\frac{k^{2}}{\varepsilon^{2}} \log (n/k))$; (lower bound) $\|{\cal F}\|=\Omega(k^{2}(1-\sqrt{8 \varepsilon}))$. In this paper, we first derive an upper bound for the Ramsey number of the edge coloring with $m \geq 2$ colors of a complete graph $K_{\ell}$ of $\ell$ vertices, and by the linear algebra method, we then derive a slightly improved lower bound, i.e., we show that
for any family ${\cal F} \subseteq S_{n}$ of $\varepsilon$-approximate $k$-restricted min-wise independent permutations, $\|{\cal F}\| =
\Omega(k \sqrt{\frac{1}{\varepsilon}\log (n/k)})$. |
| キーワード |
（和） |
最小値独立 / 正定値 / ラムゼー数 / 最数的手法 / / / / |
| （英） |
Min-Wise Independence / Positive Definite / Ramsey Number / Linear Algebra Method / / / / |
| 文献情報 |
信学技報, vol. 105, no. 680, COMP2005-66, pp. 23-30, 2006年3月. |
| 資料番号 |
COMP2005-66 |
| 発行日 |
2006-03-16 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
COMP |
| 開催期間 |
2006-03-22 - 2006-03-23 |
| 開催地（和） |
電気通信大学 |
| 開催地（英） |
The University of Electro-Communications |
| テーマ（和） |
|
| テーマ（英） |
|
| 講演論文情報の詳細 |
| 申込み研究会 |
COMP |
| 会議コード |
2006-03-COMP |
| 本文の言語 |
英語（日本語タイトルあり） |
| タイトル（和） |
ε-近似k-制限最小値独立置換族のサイズの下界 |
| サブタイトル（和） |
|
| タイトル（英） |
Improved Lower Bounds for Families of ε -Approximate k-Restricted Min-Wise Independent Permutations |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
最小値独立 / Min-Wise Independence |
| キーワード(2)（和/英） |
正定値 / Positive Definite |
| キーワード(3)（和/英） |
ラムゼー数 / Ramsey Number |
| キーワード(4)（和/英） |
最数的手法 / Linear Algebra Method |
| キーワード(5)（和/英） |
/ |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
伊東 利哉 / Toshiya Itoh / イトウ トシヤ |
| 第1著者 所属（和/英） |
東京工業大学 (略称： 東工大)
Tokyo Institute of Technology (略称： Tokyo Inst. of Tech.) |
| 第2著者 氏名（和/英/ヨミ） |
永谷 達也 / Tatsuya Nagatani / ナガタニ タツヤ |
| 第2著者 所属（和/英） |
東京工業大学 (略称： 東工大)
Tokyo Institute of Technology (略称： Tokyo Inst. of Tech.) |
| 第3著者 氏名（和/英/ヨミ） |
/ / |
| 第3著者 所属（和/英） |
(略称： )
(略称： ) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2006-03-23 11:05:00 |
| 発表時間 |
35分 |
| 申込先研究会 |
COMP |
| 資料番号 |
COMP2005-66 |
| 巻番号（vol） |
vol.105 |
| 号番号（no） |
no.680 |
| ページ範囲 |
pp.23-30 |
| ページ数 |
8 |
| 発行日 |
2006-03-16 (COMP) |
|