Global distance-based segmentation of trajectories

ABSTRACT

This work introduces distance-based criteria for segmentation of object trajectories. Segmentation leads to simplification of the original objects into smaller, less complex primitives that are better suited for storage and retrieval purposes. Previous work on trajectory segmentation attacked the problem locally, segmenting separately each trajectory of the database. Therefore, they did not directly optimize the inter-object separability, which is necessary for mining operations such as searching, clustering, and classification on large databases. In this paper we analyze the trajectory segmentation problem from a global perspective, utilizing data aware distance-based optimization techniques, which optimize pairwise distance estimates hence leading to more efficient object pruning. We first derive exact solutions of the distance-based formulation. Due to the intractable complexity of the exact solution, we present anapproximate, greedy solution that exploits forward searching of locally optimal solutions. Since the greedy solution also imposes a prohibitive computational cost, we also put forward more light weight variance-based segmentation techniques, which intelligently "relax" the pairwise distance only in the areas that affect the least the mining operation.

REFERENCES

• 1: Bob Abarbanel , William McNeely, FlyThru the Boeing 777, ACM SIGGRAPH 96 Visual Proceedings: The art and interdisciplinary programs of SIGGRAPH '96, p.124, August 04-09, 1996, New Orleans, Louisiana, United States [doi>10.1145/253607.253800]
• 2: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 3: Vassilis Athitsos , Marios Hadjieleftheriou , George Kollios , Stan Sclaroff, Query-sensitive embeddings, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066238]
• 4: M. Cardle, M. Vlachos, S. Brooks, E. Keogh, and D. Gunopulos. Fast Motion Capture Matching with Replicated Motion Editing. In ACM Siggraph, 2003.
• 5: Philip K. Chan , Matthew V. Mahoney, Modeling Multiple Time Series for Anomaly Detection, Proceedings of the Fifth IEEE International Conference on Data Mining, p.90-97, November 27-30, 2005 [doi>10.1109/ICDM.2005.101]
• 6: Jonathan D. Cohen , Ming C. Lin , Dinesh Manocha , Madhav Ponamgi, I-COLLIDE: an interactive and exact collision detection system for large-scale environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.189-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199437]
• 7: Arjen P. de Vries , Nikos Mamoulis , Niels Nes , Martin Kersten, Efficient k-NN search on vertically decomposed data, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564729]
• 8: Marios Hadjieleftheriou , George Kollios , Vassilis J. Tsotras , Dimitrios Gunopulos, Efficient Indexing of Spatiotemporal Objects, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.251-268, March 25-27, 2002
• 9: E. Keogh. UCR time series data mining archive. http://www.cs.ucr.edu/~eamonn/TSDMA/.
• 10: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 11: E. Keogh, T. Palpanas, V. Zordan, D. Gunopulos, and M. Cardle. Indexing Large Human-Motion Databases. In VLDB, 2004.
• 12: Richard Mann , Allan D. Jepson , Thomas El-Maraghi, Trajectory Segmentation Using Dynamic Programming, Proceedings of the 16 th International Conference on Pattern Recognition (ICPR'02) Volume 1, p.10331, August 11-15, 2002
• 13: Slobodan Rasetic , Jörg Sander , James Elding , Mario A. Nascimento, A trajectory splitting model for efficient spatio-temporal indexing, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 14: B. M. Ursing and U. Arnason. Analyses of mitochondrial genomes strongly support a hippopotamus-whale clade. In Proc. of the Royal Society of London, Series B, volume 265, pages 2251--2255, 1998.
• 15: Michail Vlachos , Marios Hadjieleftheriou , Dimitrios Gunopulos , Eamonn Keogh, Indexing multi-dimensional time-series with support for multiple distance measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956777]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
DNA visualization, data simplification