MLAB2012で大規模化合物フィンガープリントの類似度検索のための簡潔データ構造に関する研究発表を行いました
8月6日,7日に北海道大学で開催された、機械学習とバイオインフォマティクスのワークショップMLAB2012にて研究発表を行いました。
http://www.cris.hokudai.ac.jp/takigawa/mlab2012/
発表内容は大規模化合物フィンガープリントデータベースのための新しい簡潔データ構造を提案するというものです。フィンガープリントとは、化合物の部分構造や性質をバイナリーのベクトルとして表現したのもで、自然言語処理におけるbag-of-words (BOF)と同じデータ表現です。化合物類似度検索分野ではフィンガープリントの類似度として、Jaccard (Tanimoto)類似度が標準として使われています。
2009年にKristensenらが高速な類似度検索を可能にするマルチビット木(Multibit Tree)というデータ構造を提案しました。マルチビット木とは、近年提案されたJaccard類似度のバウンドに基づく決定木です。決定木の各ノードではエントロピー最大化によりノードを分割するフィンガープリントの要素が選ばれます。決定木の各葉は各フィンガープリントに対応します。クエリーフィンガープリントと類似度のしきい値が与えられたら、クエリーフィンガープリントのJaccard類似度のバウンドに基づき探索空間を枝刈りしながら検索することに類似度検索を行います。このバウンドと決定木の組み合わせが高速な類似度検索を可能とします。
しかし、ポインターによる決定木の表現はメモリー効率が悪いために大規模フィンガープリントに対しては大量のメモリーを消費してしまいます。さらに、バウンドに基づく検索ではfalse positiveを出力してしまうので、これらを取り除くためにフィンガープリントデータベース自体もメモリーに持たなければなりませんでした。
そこで、今回はマルチビット木に基づきメモリー効率の良い大規模フィンガープリントデータベースのための新しい簡潔データ構造を提案しました。マルチビット木は決定木からなるので簡潔木LOUDSで表現すことができます。さらにフィンガープリントデーターベースをメモリー効率良く表現するために、可変長配列や簡潔トライによる表現も提案しました。
300万からならフィンガープリントをつかった実験では、ポインターによるマルチビット木の実装では22GBのメモリーを消費してしまうところを、提案手法では検索速度を保ったまま2GBまでメモリーを減少させることに成功しています。
下は発表資料です。
発表者は豪華でしたので、他の発表も楽しんで聞くことができました。
