長さ極大な群れパターンを軌跡集合から効率良く発見するアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2013-05-10
• タイトル: 長さ極大な群れパターンを軌跡集合から効率良く発見するアルゴリズム
• タイトル / 言語: en
• タイトル: Efficient Algorithms for Finding All Length-Maximal Flock Patterns from a Set of Trajectories
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 北海道大学大学院情報科学研究科
• 著者所属: 国立情報学研究所
• 著者所属(英): en
• 著者所属(英): Hokkaido University, Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): Hokkaido University, Graduate School of Information Science and Technology
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者名: 有村, 博紀; 耿, 暁亮; 宇野, 毅明
• 著者名(英): Hiroki, Arimura; Xiaoliang, Geng; Takeaki, Uno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，（Gudmundsson and van Kreveld, ACM GIS 2006; Benkert, Gudmundsson et al., Computational Geometry, 41(111), 2008）によって導入された群れパターン（flock pattern）の軌跡集合データからの発見問題について考察する．L2ノルムをもつ2次元平面上の軌跡集合に対して，最大幅と最小長さが固定の時に，最大数の軌跡を含む群れパターンを見つける問題は，直径の2-σを許してもNP困難である．その一方で，最小軌跡数と最大幅が固定で，長さ最大の群れパターン一つは多項式時間で求まることが示されている．これに対して，本論文では，L∞ノルムをもつ2次元平面上のn本の長さTの軌跡の集合に対して，最大幅rかつ最小長さk以上で，長さ（方向の区間）極大の群れパターンをO(mnT2)遅延とO(m2)領域ですべて列挙する多項式時間遅延かつ多項式領域の列挙アルゴリズムを与える．ここに，m = |X|は列挙されるパターンのサイズ（それが含む軌跡数）である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we study the problem of finding a class of spatio-temporal patterns called (m, k)-flock patterns (Gudmundsson and van Kreveld, Proc. ACM GIS'06; Benkert, Gudmundsson, Hubner, Wolle, Computational Geometry, 41:11, 2008), which represent a groups of moving objects close each other within width at most r under L∞-norm in a given time segment of length at least k, in a collection of 2-dimensional trajectories. For max-width r > 0, min-length k, and a collection S of n trajectories of legnth T, the proposed algorithm finds all length-maximal (m, k) flock patterns in an input collection of trajectory data in O(pnT2) delay and O(p2) space, p = |X| is the size of ID set being enumerated. We also present a practical improvement using geometric indexes.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2013-AL-144, 号 3, p. 1-8, 発行日 2013-05-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会