Detecting commuting patterns by clustering subtrajectories

K. Buchin; M. Buchin; J. Gudmundsson; M. Löffler; J. Luo

doi:10.1142/S0218195911003652

Detecting commuting patterns by clustering subtrajectories

K. Buchin
, M. Buchin
, J. Gudmundsson
, M. Löffler
, J. Luo

Algorithms

Research output: Contribution to journal › Article › Academic › peer-review

105 Citations (Scopus)

1 Downloads (Pure)

Abstract

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 Fréchet distance and the discrete Fréchet 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.

Original language	English
Pages (from-to)	253-282
Journal	International Journal of Computational Geometry and Applications
Volume	21
Issue number	3
DOIs	https://doi.org/10.1142/S0218195911003652
Publication status	Published - 2011

Access to Document

10.1142/S0218195911003652

Cite this

@article{a358174e38404df184e01ade27bbe400,

title = "Detecting commuting patterns by clustering subtrajectories",

abstract = "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 Fr{\'e}chet distance and the discrete Fr{\'e}chet 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.",

author = "K. Buchin and M. Buchin and J. Gudmundsson and M. L{\"o}ffler and J. Luo",

year = "2011",

doi = "10.1142/S0218195911003652",

language = "English",

volume = "21",

pages = "253--282",

journal = "International Journal of Computational Geometry and Applications",

issn = "0218-1959",

publisher = "World Scientific",

number = "3",

}

TY - JOUR

T1 - Detecting commuting patterns by clustering subtrajectories

AU - Buchin, K.

AU - Buchin, M.

AU - Gudmundsson, J.

AU - Löffler, M.

AU - Luo, J.

PY - 2011

Y1 - 2011

N2 - 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 Fréchet distance and the discrete Fréchet 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.

AB - 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 Fréchet distance and the discrete Fréchet 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.

U2 - 10.1142/S0218195911003652

DO - 10.1142/S0218195911003652

M3 - Article

SN - 0218-1959

VL - 21

SP - 253

EP - 282

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 3

ER -

Detecting commuting patterns by clustering subtrajectories

Abstract

Access to Document

Fingerprint

Cite this