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

• Item type: Journal(1)
• 公開日: 2015-04-15
• タイトル: 大規模軌跡データからの群パターン発見のための実用的アルゴリズム
• タイトル / 言語: en
• タイトル: Practical Algorithms for Mining Flock Patterns from Trajectories
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文（推薦論文）] 軌跡データマイニング，時空間パターン，移動物体，群パターン，閉パターンマイニング（論文賞受賞）
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 国立情報学研究所
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): Hokkaido University
• 著者名: 耿, 暁亮; 宇野, 毅明; 有村, 博紀
• 著者名(英): Xiaoliang, Geng; Takeaki, Uno; Hiroki, Arimura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 群パターンは，Gudmundssonらによって2006年に提案された時空間パターンであり，一群の物体が指定した時間以上の間，指定された距離以内で，一緒に移動する様子を表す．本稿では，群パターン発見のための深さ優先探索型アルゴリズムFPMおよび，そのための2つの高速化手法を提案する．さらに，その有用性を評価するために，提案手法と既存の幅優先探索型アルゴリズムBFEを実装し，人工データと実データ上で比較実験を行う．結果として，2つの高速化手法を組み合わせることによって，著しい高速化を達成できることが示された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Flock patterns are a class of spatio-temporal patterns that represent groups of objects moving close each other in a given time segment, proposed by Gudmundsson et al. in 2006. In this paper, we propose depth-first algorithms for mining flock patterns based on depth-first frequent itemset mining approach. Especially, propose two speed-up techniques for flock pattern mining, where one uses a class of closed patterns, called rightward length-maximal flock patterns, and the other uses geometric indexes such as quad trees. To evalute these extensions, we make empirical comparison of our algorithms to BFE algorithm (Vieira et al., 2009) on synthesis datasets and real datasets. The experiments demonstrated that the modified algorithms with the above speed-up techniques are order of magnitude faster than the basic algorithm and BFE algorithm in most parameter settings.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 56, 号 4, p. 1292-1304, 発行日 2015-04-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764