[7D]多次元

11:15 〜 11:40

[7D-04] 高次元ベクトル検索の索引に対する逐次差分更新の高速化の研究

*堀内 美聡¹、渡 佑也¹、林 友佳¹、高松 宏樹¹、山室 健¹、新井 淳也² (1. NTTソフトウェアイノベーションセンタ、2. NTTコンピュータ&データサイエンス研究所)

発表者区分：一般
論文種別：ロングペーパー
インタラクティブ発表：あり

キーワード：

ベクトル検索、データベース、索引更新、ベクトルデータベース、ベクトル索引

高次元ベクトルに対する近似最近傍探索 (ANNS) は，より大量のデータや最新データに対する検索のために，検索性能（速度・精度）と索引更新速度の両立が求められてきている．既存研究では，検索性能に優れるグラフ索引と，索引更新速度に優れるハッシュ索引を組み合わせた，ハイブリッド手法が提案されている．しかし，データ挿入ごとに索引全体を更新するため，低速なグラフ更新が終わるまで挿入データを検索できず，グラフ更新がボトルネックである．本稿では，索引構造を独立に更新するハイブリッド索引更新技術を提案する．提案手法は，ハッシュ索引のみを利用する検索も可能にすることで，遅いグラフ更新を待たず高速に挿入データの検索を可能にする．さらに，複数の挿入データをまとめて最小限の操作でグラフ構造を変更することで，グラフ更新自体も効率化する．2種のデータセットを用いた評価実験により，提案手法は既存のハッシュ索引相当の速度で検索可能にし，既存のハイブリッド手法を上回るグラフ更新速度かつ同等の検索性能であることを示す．