平成24年度は,(1)離散構造データの埋め込み,(2)本質的な高次元データの次元縮小,(3)離散構造データの高次元ベクトル表現,および,埋め込みと次元縮小という3つの研究目的について,研究目的(1)に対する「(A)離散構造間距離とアルゴリズム」,研究目的(2)に対する「(B)SimpleMap法の歪みの解析と拡張」の研究を進めた.「(A)離散構造間距離のアルゴリズム」では,離散構造間距離の一つである木編集距離に対して,その変種である木の断片距離を新たに定式化し,順序木における二乗時間アルゴリズムを開発した.この断片距離は,既存の木編集距離の変種に対して新たな階層を与えている.また,無順序木の次数2木包含問題を孤立部分木包含問題にまで拡張し,その問題を解く多項式時間アルゴリズムを開発した.離散構造間距離の応用として,塩基配列の位置の関係を比較する手法として進化系統樹に基づいた位置間の剪定距離を新たに導入した.また,バズマーケティングサイトから木編集距離を用いてコミュニティを抽出する手法を開発した.さらに木以外の離散構造としては,超グラフのベルジュ非巡回部分超グラフに対する効率よい列挙問題に取り組んでいる.「(B)SimpleMap法の歪みの解析と拡張」に対しては,主に動画像検索のためのSimpleMap法の拡張に取り組んだ.特に,ヒルベルトR木を用いた検索高速化手法,階層的空間索引構造R-treeを用いたSketch検索の高速化,階層的空間索引を用いた検索高速化のための局所次元縮小射影などを開発した.