On discovering moving clusters in spatio-temporal data

Panos Kalnis*, Nikos Mamoulis, Spiridon Bakiras

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

280 Scopus citations

Abstract

A moving cluster is defined by a set of objects that move close to each other for a long time interval. Real-life examples are a group of migrating animals, a convoy of cars moving in a city, etc. We study the discovery of moving clusters in a database of object trajectories. The difference of this problem compared to clustering trajectories and mining movement patterns is that the identity of a moving cluster remains unchanged while its location and content may change over time. For example, while a group of animals are migrating, some animals may leave the group or new animals may enter it. We provide a formal definition for moving clusters and describe three algorithms for their automatic discovery: (i) a straight-forward method based on the definition, (ii) a more efficient method which avoids redundant checks and (iii) an approximate algorithm which trades accuracy for speed by borrowing ideas from the MPEG-2 video encoding. The experimental results demonstrate the efficiency of our techniques and their applicability to large spatio-temporal datasets.

Original languageEnglish (US)
Pages (from-to)364-381
Number of pages18
JournalLecture Notes in Computer Science
Volume3633
DOIs
StatePublished - Jan 1 2005
Event9th International Symposium on Spatial and Temporal Databases, SSTD 2005 - Angra dos Reis, Brazil
Duration: Aug 22 2005Aug 24 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'On discovering moving clusters in spatio-temporal data'. Together they form a unique fingerprint.

Cite this