階層グリッドを用いた四分木探索による移動軌跡データからの並列分散型頻出パターン検出

DOI Web Site BIBCODE 参考文献11件
  • 神野 良太
    神戸大学大学院システム情報学研究科計算科学専攻（現在は，西日本旅客鉄道株式会社に勤務．）
  • 熊南 昂司
    神戸大学大学院システム情報学研究科計算科学専攻
  • 福井 聡
    神戸大学工学部情報知能工学科
  • 関 和広
    神戸大学大学院システム情報学研究科計算科学専攻
  • 上原 邦昭
    神戸大学大学院システム情報学研究科計算科学専攻

書誌事項

タイトル別名
  • Parallel Distributed Trajectory Pattern Mining Based on Quadtree Search with Hierarchical Grid

抄録

In trajectory data mining which discovers frequent movement patterns from the trajectories of moving objects, both mining complex patterns and processing massive trajectory data are challenging problems. In this paper, we propose a new approach to trajectory data mining focusing on these problems. In order to make trajectories easier to process, traditional approaches quantize trajectories by a grid with a constant resolution. However, the optimal resolution often varies across different areas. This makes it difficult to mine complex patterns. Furthermore, the necessary amount of computational resources increases as the resolution becomes higher. This causes another problem that processing a massive dataset is difficult. To solve these problems, we propose a parallelized approach based on quadtree search with hierarchical grids. We employ a hierarchical grid structure with multiple resolutions to quantize trajectories. This approach initially searches for frequent patterns in a coarse grid level and drills down into a finer grid level to find more fine-grained patterns when needed. In this approach, we extract frequent movements as a pattern in terms of time duration of movements within a margin of error. Since an optimal time error varies across grid's resolutions, we propose a method for estimating optimal time errors. We also show a parallelization method based on MapReduce. In drilling down patterns, we mine child patterns in each region the parent pattern passes through and integrate child patterns along their parent pattern. In evaluation, experiments on real-word data show the effectiveness of our approach in mining complex patterns in low computational resources.

収録刊行物

参考文献 (11)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ