| 講演名 | 2003/10/20 [チュートリアル講演]最小値独立置換族に関する最近の成果 伊東 利哉, 武井 由智, 垂井 淳, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | Broderらによって提案された"最小値独立置換族"は,電子文書の類似度を効率的に判定する際の基本的な概念であり,WEB上の類似文書の検出・確率的アルゴリズムの効率化などの応用を持つことが知られている.本稿では,最小値独立置換族(及びその拡張概念であるε-近似的最小中国財務局長独立置換族・k-制限最小値独立置換族など)に関する最近の成果-(1)最小値独立置換族を用いた電子文書の類似性判定法 : (2)最小値独立置換族のサイズに関する上界と下界 ; (3)ε-近似的最初値独立置換族のサイズに関する上界と下界 ; (4)k-制限最小値独立置換族のサイズに関する上界と下界-について述べ,最小値独立置換族(及びその拡張概念)の構成方法の現状を概観する. |
| 抄録(英) | The notion of "a family of min-wise independent permutations" was introduced by Broder, et al. It is a basic tool to estimate resemblance between documents and has applications of detecting almost identical documents on the Web and of reducing the amount of randomness used by algorithms. In this paper, we focus on min-wise independent permutations and the related notions, e. g., ε-approximate min-wise independent permutations, k-restricted min-wise independent permutatios, etc., and overview the recen tresults on (1) how to estimate resemblance between documents by min-wise independent permutations ; (2) upper and lower bounds for the size of min-wise independent permutations ; (3) upper and lower bounds for the size of ε-approximate min-wise independent permutations ; (4) upper and loer obunds for the size of k-restricted min-wise independent permutations. |
| キーワード(和) | 類似度 / 最小値独立 / k-制限最小値独立 / ε-近似最小値独立 / k-順位独立 / アフィン平面 / 射影平面 |
| キーワード(英) | resemblance / min-wise independence / k-restricted min-wise independence / ε-approximate min-wise independence / k-rankwise indepencence / affine planes / projective planes |
| 資料番号 | COMP2003-49 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2003/10/20(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | [チュートリアル講演]最小値独立置換族に関する最近の成果 |
| サブタイトル（和） | |
| タイトル（英） | Recent Progress on Min-Wise Independent Permutations |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 類似度 / resemblance |
| キーワード(2)（和/英） | 最小値独立 / min-wise independence |
| キーワード(3)（和/英） | k-制限最小値独立 / k-restricted min-wise independence |
| キーワード(4)（和/英） | ε-近似最小値独立 / ε-approximate min-wise independence |
| キーワード(5)（和/英） | k-順位独立 / k-rankwise indepencence |
| キーワード(6)（和/英） | アフィン平面 / affine planes |
| キーワード(7)（和/英） | 射影平面 / projective planes |
| 第 1 著者 氏名（和/英） | 伊東 利哉 / Toshiya ITOH |
| 第 1 著者 所属（和/英） | 東京工業大学学術国際情報センター Global Scientific Information and Computing Center, Tokyo Institute of Technology |
| 第 2 著者 氏名（和/英） | 武井 由智 / Yoshinori TAKEI |
| 第 2 著者 所属（和/英） | 長岡技術科学大学電気系 Department of Electrical Engineering, Nagaoka University of Technology |
| 第 3 著者 氏名（和/英） | 垂井 淳 / Jun TARUI |
| 第 3 著者 所属（和/英） | 電気通信大学情報通信工学科 Department of Communications and Systems, University of Electro-Communications |
| 発表年月日 | 2003/10/20 |
| 資料番号 | COMP2003-49 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 394 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |