Publications
CONFERENCE (DOMESTIC) 動的なワークロードにおける近似最近傍探索
木戸 渓人 (大阪大学), 天方 大地 (大阪大学), 藤田 澄男
第25回情報科学技術フォーラム (FIT2026)
September 02, 2026
高次元ベクトル検索は，推薦システムや EC，LLM 向け RAG 等の幅広い応用を支える基盤技術であり，その高速化のために近似 𝑘 最近傍探索（Approximate 𝑘-Nearest Neighbor Search, A𝑘NNS）が用いられている．応用では，データの追加や削除が伴う，既存のグラフベース A𝑘NNS 手法の多くは，探索の開始点の発見と近傍探索の両方を単一のグラフに依存しているため，更新時にグラフ品質を維持するコストが大きく，検索性能との両立が難しい．本論文ではこの問題に対し，検索開始点の選択を担うクラスタリング木と，局所探索を担う近接グラフという二つのインデックスに役割を分離した A𝑘NNS 手法を提案する．クラスタリング木により各クエリに対して低コストに有望な開始候補集合を得ることで，近接グラフ側は局所的な近傍構造の維持に専念でき，データの挿入・削除時の更新を局所的な操作に限定できる．実世界データセットを用いた静的および動的ワークロードでの評価により，提案手法は静的設定では既存の最先端手法と同程度の検索性能を維持しつつ，動的環境では従来手法より短い時間でワークロードを処理可能であることを示す．
Paper :
動的なワークロードにおける近似最近傍探索
(external link)