[5C]索引

14:45 〜 15:10

[5C-04] ベクトル検索インデックスにおけるクラスタ代表点の並列更新手法

*内田 克¹、川島 英之¹ (1. 慶應義塾大学)

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

キーワード：

ベクトル検索、並列・分散処理、グラフ、データ構造・索引

リアルタイムに追加される莫大なデータに対して効率の良い類似検索を行う必要がある今日において，検索効率を維持したまま増分更新が可能なベクトル検索インデックスが求められている．検索効率の維持が可能なインデックスの増分更新は少数ながらも研究されているが，インデックスの品質を担保するために排他制御に依存しており，更新性能のボトルネックとなっている．本研究では，インデックス品質の低下を引き起こすことなくベクトル検索インデックスの更新を並列化するアルゴリズムを提案する．ベクトルをクラスタに分割した上でクラスタの代表点をグラフで表現するインデックスを基とし，グラフ内の代表点をバージョンを用いて管理する．代表点を楽観的に更新した後にバージョンを用いた検証を行うことで，並列更新の際に発生しうるインデックス品質の低下を防ぐことが可能となっている．