学習
ベクターデータベース入門：知っておくべきことすべて

ベクター・インデックスの基本について知っておくべきすべてのこと

May 31, 20231 分で読めます

このチュートリアルでは、最新のインデクサーのコンポーネントを分析した後、2つの最も単純なインデックス作成戦略であるフラットインデックスと転置ファイル（IVF）インデックスについて説明します。

シリーズ全体を読む

前回のチュートリアルでは、ベクトル埋め込みのパワーをより理解するために、簡単な単語の埋め込みの例と、それらがベクトルデータベースにどのように格納されインデックス化されるかを説明しました。これは、選択された距離メトリックに基づいてクエリベクトルに最も近いベクトルを見つけることを含む計算問題である、最近傍探索アルゴリズムの簡単な概要につながりました。

次に、ベクトル探索のためのいくつかのよく知られた方法について簡単に説明した：ベクトル検索はベクトルデータベースの重要な構成要素であるが、それは計算に関するものである。ベクトルデータベースは、多数の可動コンポーネントと抽象化レイヤーを含む複雑な獣である。

このチュートリアルでは、最新のインデクサーの構成要素を分析した後、最もシンプルで基本的な2つのインデクシング戦略であるフラットインデクシングとインバーテッドファイルインデックス（IVF）について説明します。この2つの様々なインデックス作成テクニックとタイプに関する知識は、次のチュートリアルに進む上で非常に重要です。

<br

ベクターインデックスとMilvus

Milvusは、HnswlibやAnnoyと共に、Facebook AI Similarity Search (FAISS)を主要なインデックス構築ライブラリの一つとして使用しています。前のチュートリアルで述べたように、Milvusはこれらのライブラリの上に構築され、通常のデータベース機能と一貫したユーザーレベルAPIを備えた本格的なデータベースを提供します。FAISS](https://zilliz.com/learn/faiss)はPythonのインターフェイスを持つc++で書かれたライブラリなので、Rのベクトルインデックスとは対照的に、c++のvector indexを使う練習をするには良い場所です。

FAISSをすでに知っているのであれば、こことこれから紹介するチュートリアルのコンセプトの多くはすでに知っているかもしれません。

ベクトル指示子の種類

前のチュートリアルを読んでお気づきかもしれませんが、大まかに言って4種類のベクトル探索アルゴリズムがあります：

ハッシュベースのインデックス作成（局所性を考慮したハッシュなど）、
ツリーベースのインデックス作成（ANNOYなど）、
クラスタベースまたはクラスタ索引法（積の量子化など）、および
グラフベースインデキシング(Hierarchical navigable small worldまたはHNSW、CAGRAなど)。

様々なタイプのアルゴリズムが、大規模なデータセットや様々なタイプのベクトルデータに対してより効果的に働きますが、これらはすべて、精度やリコールが多少犠牲になるものの、ベクトル検索プロセスのスピードアップに役立ちます。

ベクトル検索](https://zilliz.com/learn/vector-similarity-search)で見落とされがちな重要な点は、このようなベクトルインデックスと検索アルゴリズムを多数組み合わせることができる点である。ベクトル・データベース内では、完全なベクトル・インデックスは一般に3つの異なるコンポーネントから構成される：

インデックスを作成する前にベクトルを縮小したり最適化したりするオプションの前処理ステップ、
インデックス作成に使用されるコアアルゴリズムである必須の primary ステップ。
オプションの secondary ステップでは、検索速度をさらに向上させるためにベクトルを量子化したりハッシュ化したりすることができる。

これを少しずつ分解していこう。

最初のステップでは、実際にデータ構造を構築することなく、インデックス作成と検索に使用する生のベクトルを準備します。ここで使われるアルゴリズムはアプリケーションや上流のベクトル生成方法に依存することが多いが、よく使われるものにL2 正規化、次元削減、ゼロパディングなどがある。ほとんどのベクトルデータベースはこのステップをスキップし、前処理は完全にアプリケーション層のユーザーに任されている。

一次アルゴリズムは唯一の必須要素であり、ベクトルインデックスの核心を形成する。このステップの出力は、効率的なベクトル検索に必要なすべての情報を保持するデータ構造でなければなりません。ここではツリーベースやグラフベースのデータ構造がよく使われるが、量子化アルゴリズムや、積量子化や局所性を考慮したハッシュなどのハッシュベースのインデックスも同様に機能する。

第二のステップでは、データセット内のすべての浮動小数点値をより精度の低い整数値、すなわち float64 -> int8 または float32 -> int8 にマッピングすることで、インデックスの総サイズを削減する。この変更により、インデックスサイズを小さくし、検索速度を向上させることができるが、一般的には精度を犠牲にすることになる。量子化とハッシュ化については今後のチュートリアルで詳しく説明します。

フラットインデックスとは？

より複雑なベクトル探索アルゴリズムに深入りする前に、「フラット」インデックスとしても知られる線形探索について簡単に見ておきましょう。

フラットインデックスは最も基本的なインデックス作成方法ですが、最も見過ごされている方法です。フラット・インデックスでは、クエリーベクトルをデータベース内の他のすべてのベクトルと比較します。コードではこのようになります：

python

クエリー = np.random.normal(size=(128,)) dataset = np.random.normal(size=(1000, 128)) nearest = np.argmin(np.linalg.norm(dataset - query, axis=1)) 最も近い 333


インデックスが単にデータセットのサイズと同じフラットなデータ構造であることに注意してください。

最初の2行のコードでは、1000要素のベクトルデータセットに加えて、ランダムなクエリーベクトルを作成している。3行目は、データセットの全要素とクエリベクトルの最近傍要素との距離（**np.linalg.norm** 経由）を計算し、最小距離のインデックス（**np.argmin** 経由）を抽出します。これにより、クエリベクトルの最近傍の配列インデックスが得られ、これを **dataset[nearest,:\]** を使用して抽出することができます。

これは明らかに最も素朴なベクトル探索の方法ですが、特にGPUやFPGAなどのアクセラレータを使って探索処理を並列化すれば、小さなデータセットでも驚くほどうまくいきます。例えば、上のループはIntel i7-9750HのCPUで0.5ミリ秒未満で実行される。つまり、6コアのラップトップCPUでフラット・インデックスを使えば、2000以上のQPSを達成できる！

QPSは10kベクターで160、100kベクターで16に低下するが、1000ベクターから10kベクターへの10倍以上の低下はCPUキャッシュ・サイズの制限によるものと思われる。それでもこの数字はかなり良い。ランタイムの複雑さや水平方向のスケーリングが話題になっていますが、小規模なアプリケーションやプロトタイピングでは、[KISSの原則](https://en.wikipedia.org/wiki/KISS_principle)を思い出してください：シンプルに、バカに。

## 転置ファイルインデックスとは？


フラット・インデックスは素晴らしいが、明らかにスケールしない。そこで、ベクトル検索用のデータ構造が登場する。精度と再呼び出しを少し犠牲にして実行時間を改善することで、クエリー速度とスループットの両方を大幅に改善することができます。今日、たくさんの***インデックス作成戦略がありますが、最も一般的に使われているものに***転置ファイルインデックス***（IVF）があります。

派手な名前はさておき、IVFは実際にはかなり単純です。転置ファイルインデックスは、データセット全体のベクトル空間をパーティションに配置することで、全体的な検索範囲を縮小します。すべてのパーティションは***セントロイド***に関連付けられており、データセット内のすべてのベクトルは、その最も近いセントロイドに対応するパーティションに割り当てられる。

二次元のボロノイ図。 Image by Balu Ertl, CC BY-SA 4.0.](https://assets.zilliz.com/voronoi_diagram_7c821bdc9e.png)

FAISS](https://github.com/facebookresearch/faiss)をご存知の方なら、上の図に見覚えがあるかもしれません。これは_ボロノイ図_と呼ばれ、わずか2次元ではありますが、このクラスターインデックスの割り当てを視覚的に示しています。全部で20のセル（クラスター）があり、各クラスターの重心は黒い点で表示されている。データセット中のすべての点は、この20の領域のいずれかに入る。

クラスタのセントロイドは通常、_k-means_と呼ばれるクラスタリング・アルゴリズムで決定される。K-meansは、まず `K` 個の点の集合をクラスタとしてランダムに選択することで動作する、相互作用的アルゴリズムである。反復ごとに、ベクトル・データセット中のすべての点は最も近い重心に割り当てられ、すべての重心は各クラスタの平均に更新される。このプロセスは収束するまで続けられる。統計学に詳しい人なら期待値最大化法（expectation-maximazation）として知られるプロセスである。

この知識をもとに、k-meansを使ってIVFのセントロイドを「自動的」に決定してみましょう。このために、scipyの `kmeans2` 実装を使用します：


python
>> import numpy as np
>> from scipy.cluster.vq import kmeans2
>>> num_part = 16 # IVFパーティション数
>> dataset = np.random.normal(size=(1000, 128))
>>> (centroids, assignments) = kmeans2(dataset, num_part, iter=32) >> (centroids, assignments) = kmeans2(dataset, num_part, iter=32)
>> centroids.shape
(16, 128)
>> indexes.shape
(1000,)

これで centroids にはデータセットのすべての num_part (FAISS ではこのパラメータを nlist と呼ぶ) のセントロイドが格納され、assignments には各ベクトルに最も近いセントロイド/クラスタの ID が格納される。これは以下のようにして確認できる：

python

test = [np.argmin(np.linalg.norm(vec - centroids, axis=1)) for vec in dataset]. np.all(test == assignments) 真


各セントロイドをクラスタ内のベクトルのリストと関連付けることで、転置ファイルインデックスを作成する必要があります：

>> index = [[] for _ in range(num_part)
>>> index = [[] for _ in range(num_part)] >> for n, k in enumum(num_part)
>>> index = [[] for _ in range(num_part)] >> for n, k in enumerate(assignments)：
... index[k].append(n) # n番目のベクトルがk番目のクラスタに追加されます。
...

上記のコードでは、まずリストのリストを作成し、一番外側のレイヤーがファイルのインデックスを反転させたパーティションの数に対応しています。そして、forループですべての割り当て（つまり、各ベクトルがどのパーティションに属するか）をループし、インデックスに値を入れます。

インデックスを配置することで、最も近いクラスタのみを検索することで、全体の検索空間を制限することができます：

python

query = np.random.normal(size=(128,)) c = np.argmin(np.linalg.norm(centroids - query, axis=1)) # 最も近いパーティションを見つける nearest = np.argmin(np.linalg.norm(dataset[index[c]] - query, axis=1)) # 最近傍を見つける

最も近い 333


num_part`の値を16、データセットのサイズを100kとした場合、以前と同じハードウェア（CPUはIntel i7-9750H）を使って約150QPSを得た。num_part`を64に上げると、なんと650QPSになる。

特に高次元データの場合、最も近いクラスタだけでなく、それ以外のクラスタまで検索を拡張することが現実的である場合が多いことに注意してください（FAISSに詳しい方には、これは転置ファイルインデックスを作成する際の**nprobe**パラメータに相当します）。これは主に[***curse of dimensionality***](https://zilliz.com/glossary/curse-of-dimensionality-in-machine-learning) によるもので、2次元や3次元の類似データと比較した場合、各パーティションはかなり多くのエッジを持ちます。nprobe**の良い値の経験則はありません - むしろ、検索速度と精度/想起のトレードオフを見るために、まずデータで実験することが役に立ちます。

反転ファイルインデックスについては以上です！悪くないでしょう？

## まとめ


このチュートリアルでは、ベクターインデックスの3つの構成要素と、最も一般的に使用される2つの方法、フラットインデックスと反転ファイルインデックスについて見てきました。この2つは最も基本的な戦略であり、この2つを出発点として、より複雑なベクターインデックスをさらに深く掘り下げていきます。

次回のチュートリアルでは、スカラー量子化(SQ)と積量子化(PQ)-[Milvus](https://zilliz.com/what-is-milvus)ユーザーが利用できる2つの一般的な量子化ストラテジー-を用いたインデックスストラテジーへのディープダイブを続けます。次回のチュートリアルでお会いしましょう！

このチュートリアルのコードはすべてGithub: https://github.com/fzliu/vector-search。


## ベクターデータベース101コースをもう一度見てみよう

1.[非構造化データ入門](https://zilliz.com/learn/introduction-to-unstructured-data)
2.[ベクターデータベースとは](https://zilliz.com/learn/what-is-vector-database)
3.[ベクトルデータベース、ベクトル検索ライブラリ、ベクトル検索プラグインの比較](https://zilliz.com/learn/comparing-vector-database-vector-search-library-and-vector-search-plugin)
4.[Milvusの紹介](https://zilliz.com/learn/introduction-to-milvus-vector-database)
5.[Milvusクイックスタート](https://zilliz.com/learn/milvus-vector-database-quickstart)
6.[ベクトル類似検索入門](https://zilliz.com/learn/vector-similarity-search)
7.[ベクトルインデックスの基本と反転ファイルインデックス](https://zilliz.com/learn/vector-index)
8.[スカラー量子化と積量子化](https://zilliz.com/learn/scalar-quantization-and-product-quantization)
9.[階層的航行可能小世界(HNSW)](https://zilliz.com/learn/hierarchical-navigable-small-worlds-HNSW)
10.[近似最近傍オーイェー(ANNOY)](https://zilliz.com/learn/approximate-nearest-neighbor-oh-yeah-ANNOY)
11.[プロジェクトに適したベクトルインデックスの選択](https://zilliz.com/learn/choosing-right-vector-index-for-your-project)
12.[DiskANNとVamanaアルゴリズム](https://zilliz.com/learn/DiskANN-and-the-Vamana-Algorithm)