オープンソース類似度検索ツール群
プロジェクトの紹介
理研-AIP圧縮情報処理ユニットでは、私たちは常にデータの可能性を追求し、より効率的で正確な情報処理のための技術開発に尽力しています。これまでの研究において、さまざまなデータ形式や検索ニーズに対応するため、数多くの類似度検索ソフトウェアを開発してきました。
本ホームページでは、これらの研究成果を広く公開し、共有することを目的としています。私たちが開発してきた類似度検索ツールは、様々な分野の研究者や開発者がデータをより深く、効果的に解析する助けとなることでしょう。ツールの詳細な説明と共に、ソースコードへのアクセスも提供しており、皆様が自由に利用し、更なる開発を進めていただけるようになっています。
私たちの技術が、皆様の研究やプロジェクトに役立ち、データの世界を一緒に探求していけることを願っています。どうぞ、ご自由にご覧いただき、私たちの成果をご活用ください。
類似度検索ツール群の紹介
私たちの研究室で開発されてきた類似度検索ツール群は、大規模なデータセット内で類似したデータを効率的に探し出すことを目的としており、主な特徴は以下の通りです。
検索タイプの多様性: このツール群は、「One-vs-All」と「All-vs-All」の二つの類似度検索タイプを提供します。「One-vs-All」検索では、単一のクエリデータをデータベース内の全データと比較し、設定された閾値以上の類似度を持つデータを全て特定します。一方で、「All-vs-All」検索では、データベース内の全データ同士の類似度を計算し、閾値以上の類似度を持つデータペアを全て抽出します。
データ形式の対応力: このツールは、グラフ、移動軌跡、ベクトルといった様々なデータ形式に対応しており、多岐にわたる用途で利用可能です。
多種多様な類似度計算方法: コサイン類似度、Min-Max法、Jaccard類似度など、様々な類似度計算方法に対応しています。これにより、データの特性や検索の目的に応じて、最も適切な類似度計算方法を選択することが可能です。
高速かつ省メモリ: このツールは、大規模データセットを扱う際でも、高速な検索性能と低いメモリ使用量を実現しています。これにより、リソースが限られた環境でも効率的に類似データを検索することが可能です。
これらの特徴により、私たちの類似度検索ツール群は、大量のデータから重要な情報を迅速かつ効率的に引き出すための強力なツールとして、多岐にわたる分野で活用されています。
次の2つのテーブルは現在公開されているツール郡をまとめています。
「One-vs-All」類似度検索ツール郡
「One-vs-All」類似度検索ツール群は、異なるデータ形式と類似度尺度に対応した、幅広いアプリケーションで利用可能なツールのコレクションです。
gWT: gWTはグラフデータに特化した類似度検索ツールです。例えば、化合物の構造を表すグラフデータに対して優れた性能を発揮し、5000万以上の化合物を含むPubChemのような大規模データベースにおいても迅速かつ正確な類似度検索を行うことが可能です。類似度の測定にはコサイン類似度が用いられます。
SMBT: SMBTは0と1で構成されるベクトルデータに対して最適化された類似度検索ツールです。化合物フィンガープリントのようなスパースなデータに対して高い効率を持ち、Jaccard類似度を用いて類似度を計算します。
bSTおよび DyFT: これらのツールはベクトルデータに対して適応可能な類似度検索を提供し、Min-Max類似度を使用して類似度を計算します。大規模なデータセットに対しても効率的な検索を可能にします。
frechet_simsearch: このツールは、移動軌跡データの類似度検索に特化しており、スポーツデータ解析など、動きのパターンを解析するのに適しています。Frechet距離を用いて類似度を計測し、例えばバスケットボールのプレイヤーの動きを分析する際に利用することができます。
これらのツール群は、それぞれ異なるデータ形式と類似度尺度に特化しており、多様なシナリオでの利用を可能にしています。高速でメモリ効率の良い実装により、大規模データセットに対しても優れた性能を発揮し、研究や産業界での応用範囲を広げています。
関連文献
Kanda, S., Tabei, Y.: Dynamic similarity search on integer sketches, In Proceedings of the 2020 IEEE International Conference on Data Mining (ICDM), 2020.
Kanda, S., Takeuchi, K., Fujii, K., Tabei, Y.: Succinct trit-array trie for scalable trajectory similarity search, In Proceedings of the 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, 2020.
Kanda, S., Tabei, Y.: b-bit sketch trie: scalable similarity search on integer sketches, In Proceedings of the 2019 IEEE International Conference on BigData (IEEE BigData), 2019.
Tabei, Y., Simon, J. P.: Scalable similarity search for molecular descriptors, In Proceedings of the 10th International Conference on Similarity Search and Applications, 2017.
Tabei, Y., Kishimoto, A., Kotera, M., Yamanishi, Y.: Succinct interval splitting tree for scalable similarity search of compound-protein pairs with property constrains, In Proceedings of the 19th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2013.
Tabei, Y.: Succinct Multibit Tree: Compact representation of multibit trees by using succinct data structures in chemical fingerprint searches, In Proceedings of the 12th Workshop on Algorithms in Bioinformatics (WABI), 2012.
Tabei, Y., Tsuda, K.: Kernel-based similarity search in massive graph databases with wavelet trees, In Proceedings of the 11th SIAM International Conference on Data Mining (SDM), 2011.
「All-vs-All」類似度検索ツール郡
「All-vs-All」類似度検索は、データベース内の全てのデータ同士の類似度を計算し、類似しているデータペアを見つけ出す作業を指します。私たちの研究室が開発したこのカテゴリーのツール群は、主に高速な類似度検索アルゴリズム「SketchSort」に基づいています。
「All-vs-All」類似度検索ツールの使用例としては、画像や文章の重複除去、化合物データベースにおける類似ペアの発見、タンパク質シーケンスの中から特定のモチーフを抽出することなどがあります。これらのタスクは、大量のデータの中から重要な関係性を見つけ出すことを目的としており、高速で正確な類似度検索が求められます。
私たちが提供する「All-vs-All」類似度検索ツール群は、様々なデータ形式と類似度尺度に対応しており、利用者のニーズに合わせて最適なツールを選択することができます。各ツールは独自の特性を持っており、高速かつ省メモリで動作することを目標としています。
特定の応用領域や目的に最も適したツールを選択することで、効率的かつ正確な類似度検索が可能となります。私たちのツール群は、データ分析のスピードと精度を向上させ、大規模なデータセットから価値ある情報を抽出する助けとなります。
関連文献
Ito, J., Tabei, Y., Shimizu, K., Tsuda, K., Tomii, K.: PoSSuM: A database of similar protein–ligand binding and putative pockets, Nucleic Acids Research, DB issue 40:D541-8, 2012.
Ito, J., Tabei, Y., Shimizu, K., Tomii, K., Tsuda, K.: PDB-scale analysis of known and putative ligand binding sites with structural sketches, Proteins, 80, 747-763, 2012
Tabei, Y., Tsuda, K.: SketchSort: Fast all pairs similarity search for large databases of molecular fingerprints, Molecular Informatics, 30, 801-807, 2011.
Tabei, Y., Uno, T., Sugiyama, M., Tsuda, K.: Single versus multiple sorting in all Pairs similarity search, In Proceedings of the 2nd Asian Conference on Matching Learning (ACML), 2010.