大規模軌跡データからの群パターン発見のための実用的アルゴリズム  [in Japanese] Practical Algorithms for Mining Flock Patterns from Trajectories  [in Japanese]

Access this Article

Search this Article

Author(s)

Abstract

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

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.

Journal

  • IPSJ Journal

    IPSJ Journal 56(4), 1292-1304, 2015-04-15

    Information Processing Society of Japan (IPSJ)

Codes

  • NII Article ID (NAID)
    110009890369
  • NII NACSIS-CAT ID (NCID)
    AN00116647
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7764
  • Data Source
    NII-ELS  IPSJ 
Page Top