Publications
CONFERENCE (DOMESTIC) 高次元空間における効率的な近似k Nearest Neighbor 検索アルゴリズム
新井悠介 (阪大), 天方大地(阪大), 藤田澄男, 原隆浩(阪大)
第13回データ工学と情報マネジメントに関するフォーラム (DEIM2021)
March 01, 2021
近似k-Nearest Neighbor（AkNN） 検索は，コンピュータビジョンおよび機械学習をはじめとする様々な 分野で利用されている．AkNN 検索のアプリケーションでは，高次元データに対して高速かつ高精度に動作するアル ゴリズムが必要とされている．そのアプローチとして，グラフインデックスを用いたアルゴリズムが，ハッシュや量 子化を用いたアルゴリズムよりも高性能であることが知られている．しかし，既存のグラフインデックスを用いた アルゴリズムは極めてヒューリスティックであるため，その性能の理論的根拠はない．本稿では，Locality Sensitive Hashing と近接グラフを用いた新しいAkNN 検索アルゴリズムを提案する．提案アルゴリズムの性能は理論的に裏付 けされている．実世界のデータを用いた実験により，提案アルゴリズムは既存のstate-of-the-art と比較して高速かつ 高精度に動作することを示した．
Paper : 高次元空間における効率的な近似k Nearest Neighbor 検索アルゴリズム (external link)