講演抄録/キーワード |
講演名 |
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 |