Trajectory clustering: A partition-and-group framework

Jae Gil Lee, Jiawei Han, Kyu Young Whang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Existing trajectory clustering algorithms group similar trajectories as a whole, thus discovering common trajectories. Our key observation is that clustering trajectories as a whole could miss common sub-trajectories. Discovering common sub-trajectories is very useful in many applications, especially if we have regions of special interest for analysis. In this paper, we propose a new partition-and-group framework for clustering trajectories, which partitions a trajectory into a set of line segments, and then, groups similar line segments together into a cluster. The primary advantage of this framework is to discover common sub-trajectories from a trajectory database. Based on this partition-and-group framework, we develop a trajectory clustering algorithm TRACLUS. Our algorithm consists of two phases: partitioning and grouping. For the first phase, we present a formal trajectory partitioning algorithm using the minimum description length(MDL) principle. For the second phase, we present a density-based line-segment clustering algorithm. Experimental results demonstrate that TRACLUS correctly discovers common sub-trajectories from real trajectory data.

Original languageEnglish (US)
Title of host publicationSIGMOD 2007
Subtitle of host publicationProceedings of the ACM SIGMOD International Conference on Management of Data
Pages593-604
Number of pages12
DOIs
StatePublished - Oct 30 2007
EventSIGMOD 2007: ACM SIGMOD International Conference on Management of Data - Beijing, China
Duration: Jun 12 2007Jun 14 2007

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Other

OtherSIGMOD 2007: ACM SIGMOD International Conference on Management of Data
CountryChina
CityBeijing
Period6/12/076/14/07

Keywords

  • Density-based clustering
  • MDL principle
  • Partition-and-group framework
  • Trajectory clustering

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'Trajectory clustering: A partition-and-group framework'. Together they form a unique fingerprint.

Cite this