Discovering Similar MultiDimensional Trajectories

M. Vlachos, G. Kollios, D. Gunopulos

Abstract:

We investigate techniques for analysis and retrieval of object trajectories in a two or three dimensional space. Such kind of data usually contain a great amount of noise, that makes all previously used metrics fail. Therefore, here we formalize non-metric similarity functions based on the Longest Common Subsequence (LCSS), which are very robust to noise and furthermore provide an intuitive notion of similarity between trajectories by giving more weight to the similar portions of the sequences. Stretching of sequences in time is allowed, as well as global translating of the sequences in space. Efficient approximate algorithms that compute these similarity measures are also provided. We compare these new methods to the widely used Euclidean and Time Warping distance functions (for real and synthetic data) and show the superiority of our approach, especially under the strong presence of noise. We prove a weaker version of the triangle inequality and employ it in an indexing structure to answer nearest neighbor queries. Finally, we present experimental results that validate the accuracy and efficiency of our approach.

 


Cited by:
  1. "A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing", Slobodan Rasetic Jörg Sander James Elding Mario A. Nascimento, International Conference on Very Large Databases (VLDB), 2005
  2. "Assessing Similarity of Geographic Processes and Events", J. McIntosh, M. Yuan, Transactions in GIS, 2005
  3. "HMM-Based Motion Recognition System using Segmented PCA", F Bashir, W Qu, A Khokhar, D Schonfeld, IEEE International Conference on Image Processing (ICIP), 2005
  4. "MotionSearch: Object Motion Trajectory-Based Video Database System, - Indexing, Retrieval, Classification, and Recognition", F. Bashir, Ph.D. Thesis, College of Engineering, University of Illinois Chicago, 2005
  5. "Efficient Trajectory Joins using Symbolic Representations", P. Bakalov, M Hadjieleftheriou, E. Keogh and V. Tsotras, 6th International Conference on Mobile Data Management (MDM), 2005
  6. "Indexing Spatio-temporal Archives", M. Hadjieleutheriou, G. Kollios, V. Tsotras and D. Gunopulos, VLDB Journal, 2005
  7. "Symbolization of Mobile Object Trajectories with the Support to Motion Data Mining", X. Jin , J. Wang and J. Sun, CoMoGIS, Spatial Representation and Spatial Services, 2004
  8. "Outerproduct of Trajectory Matrix for Acoustic Modeling using Support Vector Machines", R Anitha, DS Satish and CC Sekhar, Int. Workshop on Machine Learning for Signal Processing, 2004
  9. "Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials", Y. Cai and R. Ng, ACM SIGMOD, 2004
  10. "A PCA-based Similarity Measure for Multivariate Time Series", K. Yang and C. Shahabi, ACM International Workshop On Multimedia Databases, 2004
  11. "Bounded similarity querying for time-series data", D. Goldin, T. Millstein, A. Kutlu, Journal of Information and Computation, 2004
  12. "Efficient Detection of Motion Patterns in Spatio-Temporal Data Sets", J. Gudmundsson, M. van Kreveld, B. Speckmann, 12th International Symposium on Advances in Geographic Information Systems (ACM GIS), pp. 250-257, 2004
  13. "PCA/MDS Visualization for Trajectory Data", H.W. Lauw, Technical Report, 2004
  14. "Optimizing Similarity Search for Arbitrary Length Time Series Queries", Tamer Kahveci, Ambuj K. Singh, IEEE Trans. Knowl. Data Eng. 16(4), pp. 418-433, 2004
  15. "Mining Heterogeneous Multivariate Time-Series for Learning Meaningful Patterns:Application to Home Health Telecare", F. Duchene,C. Garbayl, V. Rialle, Laboratory TIMC-IMAG, Facult'e de m'edecine de Grenoble, France, 2004
  16. "Density-based clustering of time series subsequences", A. Denton, 3rd Workshop on Mining Temporal and Sequential Data (TDM), 2004
  17. "Indexing Large Human-Motion Databases", E. Keogh, T. Palpanas, V. Zordan, D. Gunopulos, International Conference on Very Large Databases (VLDB), 2004
  18. "Extraction non supervisee de motifs temporels, multidimensionnels et h´et´erog`enes Application `a la t´el´esurveillance m´edicale `a domicile" F. Duchene, C. Garbay, INRIA Technical Report, 2004
  19. "Patrons de mobilite: proposition de definition, de methode de representation et d’interrogation", S. Chardonne, C. du Mouza, M.C. Fauvet, D. Josselin, P. Rigaux, Journées Cassini, 2004
  20. "Similarity Search for Interval Time Sequences", B-K.Yi and J-W. Roh, International Conference Database Systems for Advanced Applications (DASFAA), pp 232-243, 2004
  21. "Making Time-series Classification More Accurate Using Learned Constraints", C.A. Ratanamahatana, E. Keogh, SIAM International Conference on Data Mining (SDM), 2004
  22. "Extraction and Clustering of Motion Trajectories in Video" D. Buzan, S. Sclaroff, G Kollios, International Conference on Pattern Recognition (ICPR), 2004
  23. "Multi-scale Classification of Moving Objects Trajectories", C. du Mouza, P Rigaux, International Conference on Statistical and Scientific Database Management (SSDBM), 2004
  24. "FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space", S. Salvador & P. Chan, KDD Workshop on Mining Temporal and Sequential Data, 2004.
  25. "Tracking Resource Usage Using Heterogeneous Feature Spaces with Local Exceptions", T. Steinberg, J. Ford, Y. Ouyang, L. Shen, Y. Wang, W. Zheng, F. Makedon, Proc. ClustWeb 04, workshop of EDBT'04, 2004.
  26. "Robust Tracking of Human Motion", D. Buzan, Boston University, MSc Thesis, 2003
  27. "Probabilistic Discovery of Time Series Motifs", B. Chiu, E. Keogh, S. Lonardi, International Conference on Knowledge Discovery & Data-Mining (ACM SIGKDD), 2003
  28. "A Spatio-temporal Multi-modal Data Management and Analysis Environment for Tracking MS Lesions", T. Steinberg, Y. Wang, F. Makedon, L. Shen, A. Saykin, International Conference on Scientific and Statistical Database Management (SSDBM), 2003
  29. "A Novel Technique for Indexing Video Surveillance Data", E. Keogh, B. Celly, C. A. Ratanamahatana, V. Zordan, ACM SIGMM Workshop on Video Surveillance, 2003
  30. "A symbolic representation of time series, with implications for streaming algorithms", J. Lin, E. Keogh, S. Lonardi, B. Chiu, 8th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2003
  31. "Retrieval of Coordinated Motions", L. Olsen, Dept. of Computer Science, University of Calgary, Research Report
  32. "Multi-Scale Summaries of Temporal Trajectories", R Yang, Univ. of British Columbia, MSc thesis, 2003
  33. "Efficiently finding arbitrarily scaled patterns in massive time series databases", E. Keogh, International Conference of Practice of Knowledge Discovery in Databases (PKDD), 2003
  34. "Methods for Comparison of Animated Motion Generators", M. Kulbacki, IEEE International Conference on Computational Cybernetics, 2003
  35. "A safe information sharing framework for e-government communication", F. Makedon, G. Pantziou, M. Conalis-Kontos, C. Sudborough, In Electronic Democracy: Information Society and Citizens' Rights, 2003.
  36. "Exact Indexing of Dynamic Time Warping", E. Keogh, C.A. Ratanamahatana, International Conference on Very Large Databases (VLDB), 2003,
  37. "Ten benchmark database queries for location-based services", Y. Theodoridis, Computer Journal, 2003
  38. "Spatio-temporal data reduction with deterministic error bounds", H. Cao, O. Wolfson, G. Trajcevski, Proceedings of the joint workshop on Foundations of Mobile Computing, 2003
  39. "Accuracy and Resource Concumption in Tracking and Location Prediction", O. Wolfson, H. Yin, International Conference on Spatial & Temporal Databases (SSTD), 2003
  40. Symbolic Representation and Retrieval of Moving Object Trajectories L. Chen, T. Ozsu, V. Oria Univ. of Waterloo, Technical report, 2003
  41. "Similarity-Based Retrieval of Time-Series Data Using Multi-Scale Histograms" L. Chen, T. Ozsu, Univ. of Waterloo, Technical Report CS-2003-31, 2003
  42. "Mining Motifs in Massive Time Series Databases" P. Patel, E. Keogh, J. Lin, S. Lonardi, International Conference on Data-Mining (ICDM), 2002
  43. "Aggregation and comparison of trajectories", N. Meratnia, ACM GIS, 2002
  44. "Similarity Searching for Multi-Attribute Sequences", T. Kahveci, A. Singh, A. Guerel, International Conference on Statistical & Scientific Databases (SSDBM), 2002