「大規模軌跡データからの群パターン発見のための実用的アルゴリズム」

2015年度論文賞受賞者の紹介

大規模軌跡データからの群パターン発見のための実用的アルゴリズム

[情報処理学会論文誌 Vol.56, No.4, pp.1292-1304]
[論文概要]

 群パターンは,Gudmundssonらによって2006年に提案された時空間パターンであり,一群の物体が指定した時間以上の間,指定された距離以内で,一緒に移動する様子を表す.本稿では,群パターン発見のための深さ優先探索型アルゴリズムFPMおよび,そのための二つの高速化手法を提案する.さらに,その有用性を評価するために,提案手法と既存の幅優先探索型アルゴリズムBFEを実装し,人工データと実データ上で比較実験を行う.結果として,二つの高速化手法を組み合わせることによって,著しい高速化を達成できることが示された.

[推薦理由]

 本論文は、指定した時間以上・距離以内で一緒に移動する一群の物体を発見する群パターン問題に対して、多項式遅延・領域計算量を持つ完全な解集合を発見するアルゴリズムを提案している。形式的証明とともに、人工データ、実データを利用した実験を通じて、既存アルゴリズムに対して著しい高速化、性能の安定性が報告されている。新規性、有用性がともに高く、このアルゴリズムを利用したビッグデータからの群パターンの発見は、さまざまな応用処理において有益となると考えられるため、論文賞としてふさわしいと判断し、ここに推薦する。

耿暁亮 君

 1986年生.2009年中国東北大学ソフトウェア学院ソフトウェア工学科卒業.同年,北海道大学大学院情報科学研究科研究生を経て,2012年北海道大学大学院修士課程修了.同年,北海道大学大学院情報科学研究科博士後期課程入学.2010年から地理情報マイニングの研究に従事.2015年博士後期課程終了,博士(工学)を取得.2016年1月日立(中国)R&D研究員着任.ビッグデータと軌跡データを研究.

宇野毅明 君

 1998年3月東京工業大学総合理工学研究科博士課程終了,博士(理学)を取得.1998年4月東京工業大学経営工学専攻助手着任,2001年2月国立情報学研究所助教授着任.2005年5月より2006年8月までスイス連邦工科大学に滞在.現在,情報学プリンシプル研究系教授.日本オペレーションズリサーチ学会,情報処理学会,電子情報通信学会に所属.専門はアルゴリズムの理論と応用,特に離散アルゴリズム,列挙アルゴリズム,計算量理論,組合せ最適化など.データマイニング・データ解析・ゲノム情報学では,クラスタリングや類似性などの基礎計算を大規模データで高速に行う手法を研究.2010年文部科学大臣表彰 科学技術部門 若手科学者賞受賞.

有村博紀 君

 1988年九州大学理学部物理学科卒業.1990年九州大学大学院修士課程修了.同年,九州工業大学助手,同助教授などを経て,1996年九州大学大学院助教授,2004年から北海道大学情報科学研究科教授,現在に至る.博士(理学).1999~2002年JSTさきがけ研究21研究員.2007~2011年文科省GCOEプログラム「知の創出を支える次世代IT基盤拠点」拠点リーダー.現在,データマイニングと,情報検索,アルゴリズムの研究に従事.ACM,情報処理学会,人工知能学会の各会員.