オープンソースへのMicrosoftの最新の貢献であるSpace Partition Tree And Graph (SPTAG)は、Microsoft Bing検索エンジンで使用される近似最近傍検索（NNS）アルゴリズムの実装である。
純粋な数学的用語では、SPTAGは、クエリベクトルからの距離を最小にする、与えられた集合内のベクトルを効率的に見つけることができるものである。実際には、SPTAGは近似NNSを実行する。つまり、どのベクトルが最近傍であるかを推測し、実際の最近傍を返すことを保証するものではない。これと引き換えに、メモリ消費と時間消費の点で、アルゴリズムの要件が改善される。
これは、SPTAGを使用して同様のデータを検索できることを意味する。ベクトルは、データポイントを数値で表したもので、相対的な距離に従って整理できる。データポイントからベクトル空間へのマッピングを適切に選択した場合、その距離は対応するデータポイント間の類似性を表すものと見なすことができる。
データのベクトル化は、テキスト、ページスニペット、画像、その他のメディアなどの異種データポイントを比較できるという点で、従来のキーワード検索と比較して興味深い特性がある。それらはすべて、アルゴリズムが元の形式を気にせずに扱うベクトルにマッピングされる。Microsoftが説明しているように、これはやや驚くべき効果がある。
たとえば、ユーザが「How tall is the tower in Paris（パリの塔の高さは）？」と入力したとします。 Bingは、「Eiffel」という単語が検索クエリになくても、 「tall」という単語が結果に表示せずに、ユーザにEiffel Tower（エッフェル塔）が1,063フィートであることを伝える自然言語の結果を返すことがあります。
SPTAGは単なる実験ではなく、その強さはBingで強調されてきた。そこでは、ベクトル化されてSPTAGに供給される150億を超えるデータポイントが扱われる。BingプログラムマネージャのJeffrey Zhuによると、SPTAGは5ミリ秒以内に1000億のベクトルを検索して最も関連性の高い結果を提供することができる。
もちろん、データポイントをベクトルにマッピングすることがベクトル検索を効果的に使用するための重要なステップであることに気づかなければならない。Microsoftのアルゴリズムはそれに関して何の助けにもならない。さらに、MicrosoftはWebデータをベクトルにマッピングする方法についての見解を提供していない。これが検索の背後にある魔法の一部である。この点について、Microsoftは、Bingがディープニューラルネットワークを使用してマッピングをトレーニングしていると述べている。そして、検索結果に対するユーザクリックを考慮して、その意味と元のユーザクエリとの関連性をより深く理解していると述べている。テキストコーパスをベクトル空間にマッピングするために使用される既知のアルゴリズムはWord2vecであり、その実装はいくつかの言語で利用可能である。
SPTAGが唯一の近似NNSアルゴリズム実装ではない。特に、Faissと呼ばれる類似のアルゴリズムの実装を、Facebook Researchは発表した。それはまた、10億のベクトルデータセットに対して素晴らしいパフォーマンスを出すと謳われている。