DETECTING COMMUTING PATTERNS BY CLUSTERING SUBTRAJECTORIES

被引：66

作者：

Buchin, Kevin ^{[1
]}

Buchin, Maike ^{[1
]}

Gudmundsson, Joachim ^{[2
]}

Loeffler, Maarten ^{[3
]}

Luo, Jun ^{[4
]}

机构：

[1] Tech Univ Eindhoven, Dept Math & Comp Sci, Eindhoven, Netherlands

[2] NICTA, Sydney, NSW, Australia

[3] Univ Calif Irvine, Dept Comp Sci, Irvine, CA USA

[4] Chinese Acad Sci, Shenzhen Inst Adv Technol, Beijing 100864, Peoples R China

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 2011年 / 21卷 / 03期

基金：

澳大利亚研究理事会;

关键词：

Trajectories; Frechet distance; algorithms; TRAJECTORIES; ARRANGEMENTS; DISTANCE;

D O I：

10.1142/S0218195911003652

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper we consider the problem of detecting commuting patterns in a trajectory. For this we search for similar subtrajectories. To measure spatial similarity we choose the Frechet distance and the discrete Frechet distance between subtrajectories, which are invariant under differences in speed. We give several approximation algorithms, and also show that the problem of finding the 'longest' subtrajectory cluster is as hard as MaxClique to compute and approximate.

引用

页码：253 / 282

页数：30

共 46 条

[1]

Agarwal P. K., 1994, Proceedings of the Tenth Annual Symposium on Computational Geometry, P67, DOI 10.1145/177424.177521

[2]

Agrawal R., 1995, VLDB '95. Proceedings of the 21st International Conference on Very Large Data Bases, P490

[3]

Al-Naymat G, 2007, APPLIED COMPUTING 2007, VOL 1 AND 2, P393, DOI 10.1145/1244002.1244095

[4] Comparison of distance measures for planar curves [J].

Alt, H ;

Knauer, C ;

Wenk, C .

ALGORITHMICA, 2004, 38 (01) :45-58

[5] COMPUTING THE FRECHET DISTANCE BETWEEN 2 POLYGONAL CURVES [J].

ALT, H ;

GODAU, M .

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1995, 5 (1-2) :75-91

[6]

Alt Helmut., 1999, HDB COMPUTATIONAL GE, P121

[7] Reporting leaders and followers among trajectories of moving point objects [J].

Andersson, Mattias ;

Gudmundsson, Joachim ;

Laube, Patrick ;

Wolle, Thomas .

GEOINFORMATICA, 2008, 12 (04) :497-528

[8]

[Anonymous], 2005, Moving Objects Databases

[9]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[10]

BENKERT M, 2007, P 18 INT S ALG COMP

← 1 2 3 4 5 →