| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2010-06-14 10:25 ［招待講演］複合ソート法による高速な全ペア類似度検索 ○津田宏治（産総研）  IBISML2010-2 |
|
| 抄録 | （和） | 近年、画像や信号などを、数十ビット程度のスケッチとよばれるビット列で表す手法が、多く提案されて いる。ここから、半教師つき学習などに必要な類似度ネットワークを作成するには、ハミング距離の意味で近いペア を網羅的に発見する必要がある。しかし、全てのペアに関して距離を計算する方法は遅すぎ、三角不等式を用いて枝 刈りをする方法を用いても十分な速度が得られない。本発表では、アイテムセットマイニングに用いられるPattern Growth 法と、基数ソートを組合わせた複合ソート法という手法を紹介し、160 万サンプルの画像データに適用して、 cover tree, Lanczos bisection などの他手法よりも、大幅に高速であることを示す。特に、Locality sensitive hashing を用いてスケッチを作成した際の平均的な偽陰性確率（見逃しの確率）や、重複した発見を避けるための工夫につい ても述べる。また、同じアイデアを編集距離に基づくペア発見に適用することによって、生物配列への適用も可能に なる。この方法で、数千万本の短いDNA 配列に対して全ペア類似度検索を行った結果、Suffix Array を用いる方法に 比べて、20-1000 倍の高速化を達成した。 |
| （英） | Recently it is increasingly common that images and signals are mapped to bit strings called sketches. To build a similarity network necessary for, e.g., semi-supervised learning, it is necessary to find all close pairs in terms of Hamming distance. However, it is too slow to compute all distances and pruning by metricity does not help much. In this presentation, we present the multiple sorting method which combines pattern growth and radix sort. It is shown that it is much faster than cover tree and Lanczos bisection in a large scale image dataset. In this method, the average false negative rate is computable and duplicated discoveries are deliberately avoided. It is possible to generalize the method to edit distance. In an experiment with tens of millions of biological sequences, our method was 20 to 1000 fold faster than suffix-array based methods. |
|
| キーワード | （和） | 複合ソート法 / 全ペア類似度検索 / / / / / / |
| （英） | Multiple Sorting Method / All Pairs Similarity Search / / / / / / | |
| 文献情報 | 信学技報, vol. 110, no. 76, IBISML2010-2, pp. 3-3, 2010年6月. | |
| 資料番号 | IBISML2010-2 | |
| 発行日 | 2010-06-07 (IBISML) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | IBISML2010-2 |
|
| 研究会情報 | |
| 研究会 | IBISML |
| 開催期間 | 2010-06-14 - 2010-06-15 |
| 開催地（和） | 東大武田ホール |
| 開催地（英） | Takeda Hall, Univ. Tokyo |
| テーマ（和） | 機械学習とその応用 |
| テーマ（英） | Machine learning, etc. |
| 講演論文情報の詳細 | |
| 申込み研究会 | IBISML |
| 会議コード | 2010-06-IBISML |
| 本文の言語 | 日本語 |
| タイトル（和） | 複合ソート法による高速な全ペア類似度検索 |
| サブタイトル（和） | |
| タイトル（英） | All Pairs Similarity Search by Multiple Sorting |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 複合ソート法 / Multiple Sorting Method |
| キーワード(2)（和/英） | 全ペア類似度検索 / All Pairs Similarity Search |
| キーワード(3)（和/英） | / |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 津田 宏治 / Koji Tsuda / ツダ コウジ |
| 第1著者 所属（和/英） | 産業技術総合研究所 (略称： 産総研) National Institute of Advanced Industrial Science and Technology (略称： AIST) |
| 講演者 | 第1著者 |
| 発表日時 | 2010-06-14 10:25:00 |
| 発表時間 | 50分 |
| 申込先研究会 | IBISML |
| 資料番号 | IBISML2010-2 |
| 巻番号（vol） | vol.110 |
| 号番号（no） | no.76 |
| ページ範囲 | p.3 |
| ページ数 | 1 |
| 発行日 | 2010-06-07 (IBISML) |
[研究会発表申込システムのトップページに戻る]