Loading article…
類似性検索は、オブジェクトの (通常は非常に大きな) 空間を検索するという原理を共有する一連のメカニズムに使用される最も一般的な用語です。このとき、比較できるのは、任意の 2 つのオブジェクト間の類似性だけです。これは、画像、音声、その他の高度なデジタル オブジェクトの大規模なコレクションなど、含まれるオブジェクトが自然な順序を持たない大規模な情報リポジトリの時代に、ますます重要になっています。
最近傍検索と範囲クエリは類似検索の重要なサブクラスであり、多数のソリューションが存在します。類似検索の研究は、複雑なオブジェクトを検索する際の固有の問題に大きく依存しています。このようなオブジェクトは、いわゆる次元の呪いの現れにより、既知のほとんどの手法が大規模なコレクションで通用しなくなり 、未解決の問題がまだ多く残っています。残念ながら、類似検索が必要な多くの場合、オブジェクトは本質的に複雑です。
類似性検索に対する最も一般的なアプローチは、距離空間という数学的概念に依存しており、これにより、検索ドメインのスケーラビリティを実現するための効率的なインデックス構造の構築が可能になります。
類似性検索は、さまざまなニーズに応じて、さまざまな科学およびコンピューティングのコンテキストで独自に進化してきました。2008 年に、この分野の数人の一流研究者は、この主題はそれ自体が研究テーマであるべきであり、その使用のさまざまな領域に当てはまる一般的な問題に焦点を当てる必要があると強く感じました。その結果、SISAP 財団が設立され、その主な活動は、この一般的なトピックに関する一連の年次国際会議です。
メトリック検索
メトリック検索は、メトリック空間内で行われる類似性検索です。半メトリック特性は、あらゆる種類の検索を意味のあるものにするために多かれ少なかれ必要ですが、三角不等式のさらなる特性は、概念的な目的ではなく、エンジニアリングの目的に役立ちます。
三角不等式の単純な帰結は、空間内の任意の 2 つのオブジェクトが離れている場合、3 番目のオブジェクトは両方に近づくことができないということです。この観察により、データ コレクション内で測定された距離に基づいてデータ構造を構築し、クエリの実行時にデータのサブセットを除外することができます。簡単な例として、参照オブジェクトをデータ セットから選択し、セットの残りをこのオブジェクトまでの距離に基づいて 2 つの部分に分割することができます。つまり、参照オブジェクトに近いオブジェクトをセットAに、オブジェクトから遠いオブジェクトをセットBに分割します。セットが後でクエリされたときに、クエリから参照オブジェクトまでの距離が大きい場合、セットA内のオブジェクトはいずれもクエリに非常に近づくことはできません。距離が非常に小さい場合、セットB内のオブジェクトはいずれもクエリに近づくことはできません。
このような状況が定量化され研究されると、さまざまなタイプのコレクションに適したさまざまなメトリック インデックス構造を設計できます。したがって、メトリック検索の研究領域は、メトリック空間の特性を使用して効率的な類似性検索を実行できる、大規模で比較的静的なデータ コレクションの前処理アルゴリズムの研究として特徴付けられます。
種類
局所性を考慮したハッシュ
類似性検索の一般的なアプローチは、局所性感知ハッシュ(LSH) です。[1]これは、入力項目をハッシュして、類似項目がメモリ内の同じ「バケット」に高い確率でマップされるようにします (バケットの数は、入力項目の可能な範囲よりもはるかに小さくなります)。これは、画像データベース、ドキュメント コレクション、時系列データベース、ゲノム データベースなどの大規模な高次元データに対する最近傍検索によく適用されます。[2]
参照
SISAP 財団および会議シリーズ: www.sisap.org
文献
- Pei Lee、Laks VS Lakshmanan、Jeffrey Xu Yu: Top-k 構造類似性検索について。ICDE 2012:774-785
- Zezula, P.、Amato, G.、Dohnal, V.、Batko, M. 類似性検索 - メトリック空間アプローチ。Springer、2006年。ISBN 0-387-29146-6
- サメット、H.. 多次元およびメトリックデータ構造の基礎。Morgan Kaufmann、2006年。ISBN 0-12-369446-9
- E. Chavez、G. Navarro、RA Baeza-Yates、JL Marroquin、「距離空間での検索」、ACM Computing Surveys、2001
- ML ヘットランド、「メトリック インデックスの基本原理、データ マイニングにおける多目的問題のための群知能」、計算知能研究第 242 巻、2009 年、pp 199–232
リソース
- マルチフィーチャーインデックスネットワーク（MUFIN）プロジェクト
- MI ファイル (メトリック反転ファイル)
- コンテンツベースの写真画像検索テストコレクション (CoPhIR)
ベンチマーク
- ANN ベンチマーク、近似最近傍アルゴリズム検索用、Spotify提供
参考文献
- ^ ジオニス、アリスティデス、ピョートル・インディク、ラジーブ・モトワニ。 「ハッシュ化による高次元の類似性検索」 VLDB。 Vol. 99. No.6. 1999.
- ^ Rajaraman, A.; Ullman, J. (2010). 「大規模データセットのマイニング、第3章」