DiskANNとヴァマナアルゴリズム

#ディスカンとヴァマナアルゴリズム入門

Milvusチュートリアル](https://codelabs.milvus.io/)へようこそ。前回のチュートリアルでは、Approximate Nearest Neighbors Oh Yeah、略してAnnoyについて深く掘り下げてみました。Annoyはツリーベースのインデックス作成アルゴリズムで、ランダム投影を使用してベクトルの超空間を繰り返し分割し、最終的な分割はバイナリツリーになります。Annoyは精度と再現性を向上させるために2つのトリックを使用する。1）クエリポイントが分割超平面の近くにある場合、分割の両半分をトラバースする。Annoyは現在、実運用環境でのインデックス作成アルゴリズムとしてはあまり使われていないが（HNSWやIVF_PQの方がはるかに人気がある）、それでもAnnoyはツリーベースのベクトルインデックスの強力なベースラインを設定している。

Annoyの核心は依然として_インメモリインデックスである。我々は、インメモリインデックス、つまり、完全にRAMに存在するベクトルインデックスしか見ていない。コモディティマシンでは、インメモリインデックスは小規模なデータセット（1024次元ベクトルが1000万個程度まで）には最適である。しかし、100Mベクトルを超えると、インメモリインデックスは法外に高価になります。例えば、100Mベクトルだけで、約400GBのRAMが必要になります。

ここで、on-disk index（RAMとハードディスクの両方を利用するベクターインデックス）が役に立ちます。このチュートリアルでは、NVMeハードディスク上にインデックスの大部分を永続化することで、大規模なベクターの保存、インデックス作成、検索を可能にするグラフベースのベクターインデックスであるDiskANNについて説明します。まず、DiskANNのコアとなるデータ構造であるVamanaについて説明した後、DiskANNのオンディスク部分がどのようにVamanaグラフを利用して効率的にクエリを実行するかについて説明します。以前のチュートリアルと同様に、PythonでVamanaアルゴリズムの実装を開発します。

Vamana アルゴリズム

Vamanaのキーコンセプトは相対近傍グラフ（RNG）です。形式的には、1つの点に対するRNGの辺は、新しい辺が既存のどの近傍にも近くない限り、繰り返し構築される。RNGの重要なコンセプトは、グラフのどの点に対しても、最も関連性の高い近傍エッジのサブセットだけが追加されるようにRNGが構築されるということである。HNSWと同様に、近傍ベクトルはベクトルデータベースで使用されている距離メトリック、例えば余弦やL2によって決定される。

RNGには主に2つの問題があり、ベクトル探索にはまだ非効率的です。1つ目は、RNGを構築するのに$$O(n^2)$$という法外なコストがかかることです。もう一つは、RNGの直径を決めるのが難しいことです。直径の大きいRNGは密度が高すぎるし、直径の小さいRNGはグラフの走査（インデックスの問い合わせ）に時間がかかり非効率的である。にもかかわらず、RNGは依然として良い出発点であり、Vamanaアルゴリズムの基礎を形成している。

単位正方形内の100個のランダム点の相対近傍グラフ](https://assets.zilliz.com/The_relative_neighborhood_graph_of_100_random_points_in_a_unit_square_ae8ba87127.png)

画像ソースWikepedia-相対近傍グラフ。どの点も最も近い隣人の部分集合としかつながっていないことに注意。

大まかに言えば、Vamanaアルゴリズムは、2つの巧妙なヒューリスティック、すなわち貪欲探索手順とロバスト・プルーン手順を利用することで、これらの問題を解決する。では、この2つのヒューリスティックがどのように作用して、ベクトル探索用に最適化されたグラフを作るのか、実装とともに見ていこう。

その名の通り、貪欲探索アルゴリズムはグラフ p 内で指定された点（ベクトル）に最も近い近傍を繰り返し探索する。大雑把に言えば、近傍ノード集合 nns と訪問ノード集合 visit の2つの集合を保持する。

python def _greedy_search(graph, start, query, nq: int, L: int)：

best = (np.linalg.norm(graph[start][0] - query), entry).

nns = [start].
visit = set() # 訪問ノードの集合
nns = ヒープ化(nns)

# 上位k個の最近接ノードを見つける
while nns - visit：
    nn = nns[0］
    for idx in nn[1]：
        d = np.linalg.norm(graph[idx][0] - query)
        heappush(nns, (d, nn))
        visit.add((d, nn))

    # 検索リストサイズの要素まで保持
    while len(nns) > L：
        heappop(nns)

return (nns[:nq], visit)

nns` は開始ノードで初期化され、各反復でクエリ点に最も近い方向に最大 `L` ステップする。これは `nns` 内の全てのノードを訪問するまで続けられる。

一方、Robust pruneはもう少し複雑である。このヒューリスティックは、貪欲な探索手順において、連続する探索ノード間の距離が指数関数的に減少するように設計されている。形式的には、ロバストプルーンは1つのノードに対して呼び出されると、最大で`R`個の辺が存在し、新しい辺が既存の隣接ノードから少なくとも`a`回離れたノードを指すように、アウトバウンドの辺が修正されることを保証する。

python
def _robust_prune(graph, node: Tuple[np.ndarray, Set[int]], candid: Set[int], R: int)：
    
    candid.update(node[1])
    node[1].clear()

    while candid：
        (min_d, nn) = (float("inf"), None)

        # 入力ノードに最も近い要素/ベクトルを見つける
        for k in candid：
            p = graph[k］
            d = np.linalg.norm(node[0] - p[0])
            if d < min_d：
                (min_d, nn) = (d, p)
        node[1].add(nn)

        # 選択されたノードに対して最大R個の外隣接ノードを設定する
        if len(node[1]) == R：
            ブレーク

        # 今後の反復は距離閾値に従わなければならない
        for p in candid：
            if a * min_d <= np.linalg.norm(node[0] - p[0])：
                candid.remove(p)

これら2つのヒューリスティックを用いて、Vamanaアルゴリズムの全容に焦点を当てることができる。Vamana グラフはまず初期化され、各ノードは R 個のランダムな外向きの辺を持つ。その後、アルゴリズムはグラフ内の全てのノードに対して _greedy_search と _robust_prune を繰り返し呼び出す。

ベクトル・インデックスに関するこれまでのチュートリアルのように、全てを1つのスクリプトにまとめましょう：

python class VamanaIndex(_BaseIndex)： """Vamanaグラフアルゴリズムの実装。各グラフの各要素は ベクトルとグラフ内の一方向接続のリストを含む2タプル を含む2タプルである。 """

def __init__(self, L: int = 10, a: float = 1.5, R: int = 10)：
    super().__init__()
    self._L = L
    self._a = a
    self._R = R
    self._start = None # ベクトル開始のインデックス
    self._index = [] # 開始ベクトルのインデックス


def create(self, dataset)：

    self._R = min(self._R, len(dataset))

    # データセットでグラフを初期化する
    # 開始位置をメドイドベクトルとして設定
    dist = float("inf")
    medoid = np.median(dataset, axis=0)
    for (n, vec) in enumerate(dataset)：
        d = np.linalg.norm(medoid - vec)
        if d < dist：
            dist = d
            self._start = n
        self._index.append((vec, set()))

    # 各ノードのアウト・コネクションをランダムにする
    for (n, node) in enumerate(self._index)：
        idxs = np.random.choice(len(self._index) - 1, replace=False, size=(self._R,))
        idxs[idxs >= n] += 1 # どのノードも自分自身を指していないことを確認する
        ノード[1].update(idxs)

    # ランダム並べ替え＋逐次グラフ更新
    for (n, node) in enumerate(self._index)：
        (_, V) = self.search(node, nq=1)
        self._robust_prune(node, V)
        for inb in node[1]：
            nbr = self._index[inb]。
            if len(nbrs[1]) > self._R：
                self._robust_prune(nbr, nbr[1].union(n))
            else：
                nbr[1].add(n)


def insert(self, vector)：
    raise NotImplementedError("Vamana indexes are static")


def search(query, nq: int = 10)：
    """貪欲な検索。
    """

    best = (np.linalg.norm(self._index[self._start][0] - query), entry).

    nns = [start].
    visit = set() # 訪問ノードのセット
    nns = ヒープ化(nns)

    # 上位k個の最近接ノードを見つける
    while nns - visit：
        nn = nns[0］
        for idx in nn[1]：
            d = np.linalg.norm(self._index[idx][0] - query)
            heappush(nns, (d, nn))
            visit.add((d, nn))

        # 検索リストサイズの要素まで保持する
        while len(nns) > self._L：
            heappop(nns)

    return (nns[:nq], visit)


def _robust_prune(node: Tuple[np.ndarray, Set[int]], candid: Set[int])：
    
    candid.update(node[1])
    node[1].clear()

    while candid：
        (min_d, nn) = (float("inf"), None)

        # 入力ノードに最も近い要素/ベクトルを見つける
        for k in candid：
            p = self._index[k].
            d = np.linalg.norm(node[0] - p[0])
            if d < min_d：
                (min_d, nn) = (d, p)
        node[1].add(nn)

        # 選択されたノードに対して最大R個の外隣接ノードを設定する
        if len(node[1]) == R：
            ブレーク

        # 今後の反復は距離閾値に従わなければならない
        for p in candid：
            if a * min_d <= np.linalg.norm(node[0] - p[0])：
                candid.remove(p)

Vamanaは以上である！

## まとめ
このチュートリアルでは、グラフベースのインデックス作成戦略であるDiskANNを深く掘り下げてみました。HNSW のように、DiskANN は高次元の入力空間をどこでどのように分割するかという問題を回避し、代わりに近傍のベクトル間の関係を有向グラフで構築することに依存します。今後10年間、非構造化データの量が増え続けるにつれ、オンディスクインデックスの必要性は高まり、この分野の研究も進むだろう。

このチュートリアルのコードはすべて[https://github.com/fzliu/vector-search](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)