When Does a Partitioned ANN Index Need Active Re-Partitioning Under Drift?  A Characterization and Benchmark 

技術要約：ドリフト下において、パーティション化されたANNインデックスはいつ能動的な再パーティショニングを必要とするのか？

問題提起
近似最近傍探索（ANN）インデックスは、連続的な挿入、削除、およびモデルの更新によってデータ分布が変化する非定常なコーパスにおいて、ますます重要な役割を果たしている。既存のシステム研究（例：Quake, Ada-IVF, GTI, CrackIVF, SPFresh, DeDrift）における支配的な前提は、「静的なパーティションはデータのドリフトによって陳腐化し、能動的な再パーティショニング（分割、マージ、再クラスタリング、またはクラッキングによる）を行わない限り、リコール（再現率）の崩壊を引き起こす」というものである。本論文はこの前提の普遍性に疑問を投げかけ、「どのような特定のドリフト条件下で能動的な再パーティショニングが実際に必要となるのか」、あるいは「ドリストを、わずかに調整されたプローブ予算（probe budget）を持つ静的なインデックスで吸収できるのはいつなのか」を問うものである。

手法
著者らは既存システムの直接的なベンチマーク比較を行うのではなく、メンテナンスコストと再構築コストのトレードオフを特性化するために、制御されたマッチド・リコール（matched-recall）ハーネスを構築している。主な手法構成要素は以下の通りである：

• マッチド・リコール・プロトコル: コストのノブ（例：プローブ予算 $b$）を固定してリコールを測定する従来のベンチマークとは異なり、このプロトコルではリコールの下限（0.90）を固定し、それを達成するために必要な最小のプローブ予算（$b_{needed}$）とレイテンシを測定する。これにより、メンテナンスのコストを、変化するカバレッジ（例：パーティションの分割が固定された $b$ でカバーされる質量を減少させること）による混同効果から分離する。
• ワークロード生成器: 著者らは、パラメータ化されたドリフト軸を使用している：
  • ターンオーバー ($\tau$): 生存セットが置き換わる割合。
  • 更新レート ($u$): クエリに対する更新の比率。
  • 相関 ($\rho$): データドリフトとクエリドリフトのデカップリング。
  • 有界ウィンドウ (Bounded Window): カーディナリティ（集合の大きさ）は一定に保ちつつ分布を回転させるモードであり、規模の変化からドリフトを分離する。
• 共有グラウンドトゥルース: コンテンツキーに基づいた厳密なグラウンドトゥルースを各チェックポイントごとに一度計算し、すべての実験アーム（静的、分割/マージ、再クラスタリング、再構築）で共有することで、公平な比較を保証する。
• 事前登録されたキルゲート (Pre-Registered Kill-Gates): 本研究では、失敗した仮説を「救済」することを防ぐために、一連の反証可能な基準を採用している。もしある仮説（例：「リーフ内のグラフ（graph-in-leaf）は静的な勝利である」）がゲートで失敗した場合、研究はパラメータを調整して無理に肯定的な結果を出すのではなく、方向転換を行う。
• テストされたアーム:
  • 静的 (C0): メンテナンスなし、墓石（tombstone）削除。
  • メンテナンス・バリアント: ドリフトによってトリガーされる分割/マージ、カーディナリティによってトリガーされる分割、および増分的な再中心化（incremental re-centering）。
  • リファレンス (R): インデックス・アーキテクチャ内でのフル・リクラスター（ゼロからの再構築）であり、品質のベースラインとして機能する。
  • 外部検証: 外部検証のために、実際のQuakeアーティファクトを同一のトレース上で実行した。

主要な結果

1. 中程度のドリフトにおける静的充足性:
   中程度の成長/ターンオーバー（SIFT1M, GIST1M）を持つデータセットにおいて、墓石削除を用いた静的パーティションは、メンテナンスが行われたバリアントと同じプローブ予算で0.90のリコール下限を維持する。この領域では、能動的なメンテナンスは不要である。すなわち、「スラック（余裕）」がドリフトを吸収するのである。

2. グラフ・イン・リーフは静的な勝利ではない:
   （元の研究の動機となった）グラフ・イン・リーフ型のハイブリッド・インデックスは、リコール・QPSのパレート図において、フラットなHNSWによって支配されている。これは静的な探索上の利点を提供せず、ビルド時間の高速化のみをもたらす。

3. 境界領域（回転ドリフト）:
   実世界のスケール制御された回転ウィンドウ（MS-Turing-10M）において、静的パーティションは著しく劣化する。分布が回転するにつれ、必要なプローブ予算（$b_{needed}$）は64から112以上へと上昇する。この領域では、再中心化が真に必要となる。

4. 増分的な再中心化 vs. フル再構築:
   回転ドリフトの領域において、安価な増分再中心化は、フル・リクラスター（ゼロからの再構築）と同等のリコール品質（同一の $b_{needed}$）を、約1/6の再生コストで達成する。

   • 総所有コスト (TCO): 現実的なクエリ主体のワークロードでは、増分再中心化とフル再構築のTCOは同等である。増分再中心化が厳密に勝利するのは、更新主体のワークロードのみである。
   • 再構築が優位となるクロスオーバーの否定: 本論文は、フル再構築が優位になるクロスオーバーポイント（$u^* \approx 4.7$）が存在するという以前の主張を否定し、それが新鮮なビルドのレイテンシを古いインデックスに帰属させたことや、シーケンシャルなタイミングのドリフトによるアーティファクトであることを特定した。

5. 外部検証 (Quake):
   同一のトレース上で実際のQuakeシステムを実行した結果、レジーム境界が確認された。Quakeは、限定されたスキャン分率においてリコール下限を維持している。しかし、そのデフォルトのサイズ駆動型ポリシーはインデックスを断片化させ（$nlist$ を13倍に増加させ）、高いメンテナンスコストを発生させた。一方で、制御された再中心化は、小さな予算で安価に維持することができた。

貢献

1. 制御されたベンチマーク: パラメータ化されたドリフト・ワークロードと、データ/クエリのドリフトをデカップリングし、領域ごとのグラウンドトゥルースを提供するマッチド・リコール・ハーネス。
2. レジームマップ: 「静的に十分な」領域（中程度の成長/ターンオーバー）と「再中心化が役立つ」領域（回転ドリフト）を区別する特性化。
3. 決定ルール: 実務家向けの具体的なガイドライン：
   • 中程度の成長: 静的なまま維持し、墓石削除を使用し、プローブ予算をわずかに大きく取る。
   • 回転ドリフト: 再中心化を行うが、フル再構築ではなく増分的な再中心化を使用する。
   • トリガーの選択: ドリフトに基づくトリガーとカーディナリティに基づくトリガーの間でリコールの差はない。エンジニアリング上の利便性に基づいて選択すること。
4. 説明的フレームワーク: ドリフトが吸収可能か、それとも再パーティショニングを強制するかを説明する「プローブ・バジェット・スラック」モデル（$\sigma < b$）。
5. 誠実なネガティブな結果: グラフ・イン・リーフは静的な勝利ではないこと、および再中心化を伴わない分割/マージは単にインデックスを断片化させるだけであり、ドリフトを軽減するわけではないという、分野における過剰な主張の修正。

意義と主張
本論文の主要な貢献は、新しいメンテナンス・アルゴリズムではなく、レジームマップと決定ルールであると主張している。これは、「ドリフトは能動的な再パーティショニングを必要とする」という前提が条件的であることを示唆している。

• スラック・レジーム（中程度のドリフト）では、メンテナンスは正当性の必要条件ではなく、多くの場合、不要なコストのトレードオフである。
• 強制レジーム（回転ドリフト）では、メンテナンスは必要であるが、フル・リビルドは回避可能である。増分的な再中心化は、フル再構築のわずかな部分のコストで、同等のリコール品質を達成する。
• 本論文は、マッチド・リコールおよびコンテンション制御されたプロトコルが、メンテナンスの必要性とコストに関する誤った結論（例：固定予算による比較）を招いた混乱要因を防ぐ上で、極めて重要であることを強調している。