Tracking moving objects in anonymized trajectories

Nikolay Vyahhi*, Spiridon Bakiras, Panos Kalnis, Gabriel Ghinita

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations


Multiple target tracking (MTT) is a well-studied technique in the field of radar technology, which associates anonymized measurements with the appropriate object trajectories. This technique, however, suffers from combinatorial explosion, since each new measurement may potentially be associated with any of the existing tracks. Consequently, the complexity of existing MTT algorithms grows exponentially with the number of objects, rendering them inapplicable to large databases. In this paper, we investigate the feasibility of applying the MTT framework in the context of large trajectory databases. Given a history of object movements, where the corresponding object ids have been removed, our goal is to track the trajectory of every object in the database in successive timestamps. Our main contribution lies in the transition from an exponential solution to a polynomial one. We introduce a novel method that transforms the tracking problem into a min-cost max-flow problem. We then utilize well-known graph algorithms that work in polynomial time with respect to the number of objects. The experimental results indicate that the proposed methods produce high quality results that are comparable with the state-of-the-art MTT algorithms. In addition, our methods reduce significantly the computational cost and scale to a large number of objects.

Original languageEnglish (US)
Title of host publicationDatabase and Expert Systems Applications - 19th International Conference, DEXA 2008, Proceedings
Number of pages14
StatePublished - 2008
Externally publishedYes
Event19th International Conference on Database and Expert Systems Applications, DEXA 2008 - Turin, Italy
Duration: Sep 1 2008Sep 5 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5181 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other19th International Conference on Database and Expert Systems Applications, DEXA 2008

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Tracking moving objects in anonymized trajectories'. Together they form a unique fingerprint.

Cite this