近似最近傍探索インデックスは大規模なベクトル集合から高速にクエリに類似したベクトルを探索するためのデータ構造であり、画像やテキストの検索に応用されている。特に、ベクトルをノードとするグラフ上を探索するグラフベースの手法は精度と速度が優れている。その性能は探索の開始点の選択に依存する。本研究では、k-meansを用いた新たな開始点選択手法を提案し、複数のデータセットでの実験により提案手法が精度・速度のトレードオフを改善することを示した。特にマルチスレッドによるバッチ処理において有効であることが示された。提案手法はインデックス本体と独立に構築でき、メモリ使用量も非常に小さいため、適用範囲が広い。