SimilaritySearch.jl

類似性search.jl

類似性search.jlは、最近隣の検索のライブラリです。特に、任意のメトリック関数を使用した高速で柔軟な検索インデックスであるSearchGraph,の実装が含まれています。ほとんどの機能と構造のマルチスレッドをサポートするように設計されています。

パッケージは次のインデックスを提供します。

• ParallelExhaustiveSearch ：各クエリが利用可能なすべてのスレッドを使用して解決されるブルートフォース検索インデックス。
• ExhaustiveSearch ：ブルートフォース検索インデックス、各クエリは単一のスレッドを使用して解決されます。
• SearchGraph ：並列構造を備えたおおよその検索インデックス。

関数のメインセットは次のとおりです。

• search ：単一のクエリを解決します。
• searchbatch ：クエリのセットを解決します。
• allknn ：計算します $ k $インデックス内のすべての要素の最寄りの隣人。
• neardup ：メトリックデータセットから近赤面を削除します。
• closestpair ：メトリックデータセットで最も近いペアを計算します。

これらの機能の正確な定義と関数と構造の完全なセットは、ドキュメントに記載されています。

ジュリアの類似性検索エコシステム

現在、最も近い隣の検索に特化したいくつかのパッケージが存在します。たとえば、CD-Tree、ball Trees、Quadtree、octree、VP-Tree、その他の多次元およびMETRIC構造などのCD-Tree、ball Trees、Quadtree、octree、bk-tree、bk-tree、multric構造など、 NearestNeighbors.jl RegionTrees.jl JuliaNeighbors検索に特化したパッケージがあります。これらの構造は、正確な類似性クエリを解決するように設計されているため、低次元データでは非常にうまく機能します。

FAISSライブラリFaiss.jlのラッパーである製品量子化スキームを使用したRayuela.jlなど、おおよその類似性検索を実行するいくつかのパッケージが存在します。 FAISSライブラリは、 HNSWインデックスの産業強度実装とともに、製品量子化スキームと地域に敏感なハッシュスキームの高性能実装を提供します。 NearestNeighborDescent.jlは、 pynndescent背後にある検索アルゴリズムを実装します。

SimilaritySearch.jlパッケージは、マルチスレッドシステムを活用するように設計された検索構造とアルゴリズムでエコシステムを豊かにしようとします。これらの機能は、ジュリアのプログラミング言語のダイナミズムとパフォーマンスにより、簡潔かつ効率的に実装されています。パフォーマンスの特性に関しては、検索パフォーマンスや結果の品質を低下させることなく、同様のアプローチと比較して、建設時間が大幅に短縮されます。

signisitysearchのインストール

次のようにパッケージをインストールできます

] add SimilaritySearch . jl

また、テストのセットを次のように実行できます

] test SimilaritySearch

ライブラリを使用します

例をご覧ください。 JupyterとPl王星のノートブックのリスト、およびその使用を例示するスクリプトがあります。

貢献する

貢献は大歓迎です。文書化と実装の貢献のためのプルリクエストを記入してください。問題については、必要な情報を問題に記入してください（以下を参照してください。）既に解決策がある場合は、プルリクエストも提供してください。

問題

最小限の再現可能な例を提供するパッケージの問題を報告します。問題がデータに依存している場合は、それを再現するために必要なデータを提供することを忘れないでください。

SearchGraphの制限

主な検索構造であるSearchGraph,いくつかの特性を持つグラフであり、その多くはインデックス化されているデータセットによって誘導されます。その既知の制限のいくつかは、これらの特性に関連しています。例えば：

• メートル距離はうまく機能します。一方、セミメトリックは機能するはずですが、ルーティング機能はまだ特徴付けられていません。
• 代替品と比較してかなりうまく機能している場合でも、Levenshtein距離などの個別のメトリックや、可能な値をほとんど取らない他のメトリックもパフォーマンスが低くなる可能性があります。
• 同様のことは、多くの重複物質（かなり近い要素）がある場合に起こります。この場合、近赤面に近いものを取り外して、その近くのオブジェクトの一部に関連付けられたバッグに入れる必要があります。
• 非常に高次元のデータセットは、頂点ごとのエッジ数の長期尾の分布を生成します。極端な場合は、大きな近隣を剪定し、シングルエッジパスを豊かにする必要があります。

構造とアルゴリズムについて

次の原稿は、 SearchGraphインデックス（パッケージバージョン0.6 ）を説明およびベンチマークします。

 @article{tellezscalable,
  title={A scalable solution to the nearest neighbor search problem through local-search methods on neighbor graphs},
  author={Tellez, Eric S and Ruiz, Guillermo and Chavez, Edgar and Graff, Mario},
  journal={Pattern Analysis and Applications},
  pages={1--15},
  publisher={Springer}
}

現在のアルゴリズム（バージョン0.8および0.9 ）は、次の原稿に記載され、ベンチマークされています。

@misc{tellez2022similarity,
      title={Similarity search on neighbor's graphs with automatic Pareto optimal performance and minimum expected quality setups based on hyperparameter optimization}, 
      author={Eric S. Tellez and Guillermo Ruiz},
      year={2022},
      eprint={2201.07917},
      archivePrefix={arXiv},
      primaryClass={cs.IR}
}

このパッケージについては、Joss Paperにも記載されています。

エリック・S・テレスとギレルモ・ルイス。 SimilaritySearch.jl ：ジュリアのオートチューン化した最近隣接インデックス。 Journal of Open Sourceソフトウェアhttps://doi.org/10.21105/joss.04442。

v0.9.xシリーズについて

このバージョンのアルゴリズムはv0.8と同じですが、APIの互換性を破壊します。

• これで、 Polyesterパッケージを使用して、スレッドの代わりにマルチスレッドを処理します。@スレッド
• プロセスがいくつかのスレッドで開始される場合、マルチスレッドメソッドはデフォルトで有効になります。 v0.8では反対でした
• allknn 、アルゴリズムを簡素化し、効率を改善するために自己参照を保持します（v0.8のallknn自動的に自己参照を削除します）

その他：

• 関数ドキュメントとベンチマークを追加します
• SearchGraphグラフ剪定方法を追加します
• timedsearchbatch関数を削除します

v0.10.xシリーズについて

SearchGraph構造をさまざまなワークロードとアプリケーションに簡単に調整できます。例えば、

• 建設パラメーターのより多くの制御
• 読み込みと保存
• Refactors検索APIは、構造体全体で一貫しています

https://github.com/sadit/similaritysearchdemosおよびhttps://github.com/sadit/similaritysearch.jl/blob/main/test/testsearchgraph.jlを参照してください。

v0.11シリーズについて

主要なリファクタリングを導入します。特に、ほとんどの関数に対してコンテキストオブジェクトを明示的に使用します。また、簡単なロギング手順も導入します。ただし、デフォルトのコンテキストオブジェクトの暗黙的な使用を使用して、多くのパブリック関数の互換性を保持します。