[4C]近傍問合せ

11:15 〜 11:40

[4C-04] 高次元空間における高速な近似EMSTアルゴリズム

*木戸 渓人¹、天方 大地¹、原 隆浩¹ (1. 大阪大学)

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

キーワード：

最小全域木、高次元データ、近似アルゴリズム

本論文では，大規模高次元データセットにおけるユークリッド最小全域木（Euclidean Minimum Spanning Tree, EMST）を構築する問題を扱う．この問題は，データの可視化，宇宙論，およびバイオインフォマティクス等の様々な応用がある．最近では，機械学習ベースの埋め込み技術により，多くのオブジェクトが高次元ベクトルとして表現されているため，上記の応用先では高次元空間における効率的なEMSTアルゴリズムが必要である．EMSTの代表的な手法にBoruvkaアルゴリズムがあるが，このアルゴリズムはn個のデータに対して時間計算量がO(n^2\log n)となる．また，最先端のEMSTアルゴリズムでは実用的な処理時間を達成しているが，それらは低次元データへの適用を想定している．それらのアルゴリズムは高次元空間での適用において全探索に帰着するため，正確なEMSTの解を得るには高い計算コストが必要となる．ここで，応用においては近似解を許容することで高速な応答が求められる場合が多い．したがって，本論文では高次元データ空間における高速な近似EMSTアルゴリズムを提案する．提案アルゴリズムの有効性を示すため，実世界のデータセットを用いた実験を行い，提案アルゴリズムが既存アルゴリズムよりもはるかに早い時間でより正確な近似解を得ることを示す．