Article

Symbolic representation and retrieval of moving object trajectories

Authors:

M. Tamer Özsu,

Vincent OriaAuthors Info & Claims

MIR '04: Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval

Pages 227 - 234

https://doi.org/10.1145/1026711.1026749

Published: 15 October 2004 Publication History

Abstract

Searching moving object trajectories of video databases has been applied to many fields, such as video data analysis, content-based video retrieval, video scene classification. In this paper, we propose a novel representation of trajectories, called <i>movement pattern strings</i>, which convert the trajectories into symbolic representations. Movement pattern strings encode both the movement direction and the movement distance information of the trajectories. The distances that are computed in a symbolic space are lower bounds of the distances of original trajectory data, which guarantees that no false dismissals will be introduced using movement pattern strings to retrieve trajectories. In order to improve the retrieval efficiency, we define a <i>modified frequency distance</i> for frequency vectors that are obtained from movement pattern strings to reduce the dimensionality and the computation cost. The experimental results show that using movement pattern strings is almost as effective as using raw trajectories. In addition, the cost of retrieving similar trajectories can greatly be reduced when the modified frequency distance is used as a filter

References

[1]

R. Agrawal, G. Psaila, E. L. Wimmers, and M. Zaït. Querying shapes of histories. In Proc. 21th Int. Conf. on Very Large Data Bases, pages 502--514, 1995.

Digital Library

[2]

Y. Cai and R. Ng. Indexing spatio-temporal trajectoires with chebyshev polynomials. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 599--610, 2004.

Digital Library

[3]

L. Chen and R. Ng. On the marriage of edit distance and lp norms. In Proc. 30th Int. Conf. on Very Large Data Bases.

Digital Library

[4]

L. Chen, M. T. Özsu, and V. Oria. Robust and fast similarity search for moving object trajectories. In CS Tech. Report. CS-2004-33, School of Computer Science, University of Waterloo.

[5]

S.-C. Chen and R. L. Kashyap. A spatio temporal semantic model for multimedia presentations and multimedia database systems. IEEE Trans. Knowledge and Data Eng., 13(4):607--622, 2001.

Digital Library

[6]

C. Faloutsos, M. Ranganathan, and Y. Manolopoulos. Fast subsequence matching in time-series databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 419--429, 1994.

Digital Library

[7]

J. Gips, M. Betke, and P. Fleming. The camera mouse: Preliminary invertigation of automated visaul tracking for computer access. In In Proc. Conf. on Rehabilitation Engineering and Assistive Technology Society of North America, pages 98--100, 2000.

[8]

Y. Huang and P. S. Yu. Adaptive query processing for time-series data. In Proc. 5th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pages 282--286, 1999.

Digital Library

[9]

A. K. Jain and R. C. Dubes. Algorithms for Clustering Data. Prentice-Hall, 1988.

Digital Library

[10]

T. Kahveci and A. Singh. Variable length queries for time series data. In Proc. 17th Int. Conf. on Data Engineering, pages 273--282, 2001.

Digital Library

[11]

E. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Locally adaptive dimensionality reduction for indexing large time series databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 151--162, 2001.

Digital Library

[12]

E. Keogh and S. Kasetty. On the need for time series data mining benchmarks: a survey and empirical demonstration. In Proc. 8th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pages 102--111, 2002.

Digital Library

[13]

E. Keogh and M. Pazzani. Scaling up dynamic time warping for datamining applications. In Proc. 6th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, pages 285--289, 2000.

Digital Library

[14]

S.-L. Lee, S.-J. Chun, D.-H. Kim, J.-H. Lee, and C.-W. Chung. Similarity search for multidimensional data sequences. In Proc. 16th Int. Conf. on Data Engineering, pages 599--608, 2000.

Digital Library

[15]

V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Cybernetics and Control Theory, 10(8):707--710, 1966.

[16]

J.Z. Li, M.T. Özsu, and D. Szafron. Modeling of moving objects in a video databas. In Proc. 4th Int. Conf. on Multimedia and Computing System, pages 336--343, 1997.

Digital Library

[17]

J. Lin, E. Keogh, S. Lonardi, and P. Patel. Finding motifs in time series. In Proc. 2nd Int. Workshop Temporal Data Mining, pages 370--377, 2002.

[18]

J. L. Little and Z. Gu. Video retrieval by spatial and temporal sturcture of trajectories. In Proc. 13th Int. Symp. on Storage and Retrieval for Image and Video Databases, pages 544--553, 2001.

[19]

M. Vlachos, G. Kollios, and D. Gunopulos. Discovering similar multidimensional trajectories. In Proc. 18th Int. Conf. on Data Engineering, pages 673--684, 2002.

Digital Library

[20]

M. Vlachos, J. Lin, E. Keogh, and D. Gunopulos. A wavelet-based anytime algorithm for k-means clustering of time series. In Proc. Workshop on Clustering High Dimensionality Data and Its Applications, pages 23--30, 2003.

[21]

T. T. Y. Wai and A. L. P. Chen. Retrieving video data via motion tracks of content symbols. In Proc. 6th Int. Conf. on Information and Knowledge Management, pages 105--112, 1997.

Digital Library

[22]

Y. Yanagisawa, J. Akahani, and T. Satoh. Shape-based similarity query for trajectory of mobile objects. In Proc. 4th Int. Conf. on Mobile Data Management, pages 63--77, 2003.

Digital Library

Cited By

Cai CJiang WLin D(2023)Social Community Recommendation based on Large-scale Semantic Trajectory Analysis Using Deep LearningProceedings of the 18th International Symposium on Spatial and Temporal Data10.1145/3609956.3609957(110-120)Online publication date: 23-Aug-2023
https://dl.acm.org/doi/10.1145/3609956.3609957
Cai CLin D(2023)Find Another me Across the World - Large-Scale Semantic Trajectory Analysis Using SparkIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.321893035:9(8905-8918)Online publication date: 1-Sep-2023
https://doi.org/10.1109/TKDE.2022.3218930
Fu ZZheng K(2022)Searching Similar Trajectories Based on ShapeBig Data10.1007/978-981-19-8331-3_1(1-20)Online publication date: 23-Nov-2022
https://doi.org/10.1007/978-981-19-8331-3_1
Show More Cited By

Index Terms

Symbolic representation and retrieval of moving object trajectories
1. Information systems
  1. Information retrieval
    1. Retrieval tasks and goals
      1. Document filtering
      2. Information extraction
  2. Information systems applications
    1. Multimedia information systems
      1. Multimedia databases

Recommendations

Preserving topological information in sub-trajectories-based representation for spatio-temporal trajectories indexing and retrieval
MM '09: Proceedings of the 17th ACM international conference on Multimedia

Trajectories of moving objects are known as one of the most important cues for understanding semantics in video data. Although there are a lot of significant researches dealing with trajectory analysis tailored to indexing and retrieval, several ...
Indexing frequently updated trajectories of network-constrained moving objects
DEXA'11: Proceedings of the 22nd international conference on Database and expert systems applications - Volume Part II

Index is a key technique in improving the query processing performance of moving objects databases. However, current index methods for moving object trajectories take trajectory units as the basic index records and frequent index updates are needed when ...
A New Signature-Based Indexing Scheme for Trajectories of Moving Objects on Spatial Networks
ICCS '08: Proceedings of the 8th international conference on Computational Science, Part I

Because moving objects usually move on spatial networks, their trajectories play an important role in indexing them for spatial network databases. In this paper, we propose a new signature-based indexing scheme for moving objects' trajectories on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MIR '04: Proceedings of the 6th ACM SIGMM international workshop on Multimedia information retrieval

October 2004

334 pages

ISBN:1581139403

DOI:10.1145/1026711

General Chairs:
Michael S. Lew
LIACS Media Lab, The Netherlands
,
Nicu Sebe
University of Amsterdam, The Netherlands
,
Chabane Djeraba
LIFL, France

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 October 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MM04

Sponsor:

MM04: 2004 12th Annual ACM International Conference on Multimedia

October 15 - 16, 2004

NY, New York, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
520
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cai CJiang WLin D(2023)Social Community Recommendation based on Large-scale Semantic Trajectory Analysis Using Deep LearningProceedings of the 18th International Symposium on Spatial and Temporal Data10.1145/3609956.3609957(110-120)Online publication date: 23-Aug-2023
https://dl.acm.org/doi/10.1145/3609956.3609957
Cai CLin D(2023)Find Another me Across the World - Large-Scale Semantic Trajectory Analysis Using SparkIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.321893035:9(8905-8918)Online publication date: 1-Sep-2023
https://doi.org/10.1109/TKDE.2022.3218930
Fu ZZheng K(2022)Searching Similar Trajectories Based on ShapeBig Data10.1007/978-981-19-8331-3_1(1-20)Online publication date: 23-Nov-2022
https://doi.org/10.1007/978-981-19-8331-3_1
Ding WTian JLee YYang KNam K(2020)VVS: Fast Similarity Measuring of FoV-Tagged VideosIEEE Access10.1109/ACCESS.2020.30314858(190734-190745)Online publication date: 2020
https://doi.org/10.1109/ACCESS.2020.3031485
Izakian ZMesgari MWeibel R(2020)A feature extraction based trajectory segmentation approach based on multiple movement parametersEngineering Applications of Artificial Intelligence10.1016/j.engappai.2019.10339488(103394)Online publication date: Feb-2020
https://doi.org/10.1016/j.engappai.2019.103394
Amouzandeh KGoudarzi SKarimipour F(2018)Contextual Analysis of Spatio-Temporal Walking ObservationsComputational Science and Its Applications – ICCSA 201810.1007/978-3-319-95165-2_32(461-471)Online publication date: 4-Jul-2018
https://doi.org/10.1007/978-3-319-95165-2_32
Karki MBasu SDiBiano RMukhopadhyay SWeltman JStagg M(2016)A symbolic framework for recognizing activities in full motion surveillance videos2016 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI.2016.7850118(1-7)Online publication date: Dec-2016
https://doi.org/10.1109/SSCI.2016.7850118
Magdy NSakr MMostafa TEl-Bahnasy K(2015)Review on trajectory similarity measures2015 IEEE Seventh International Conference on Intelligent Computing and Information Systems (ICICIS)10.1109/IntelCIS.2015.7397286(613-619)Online publication date: Dec-2015
https://doi.org/10.1109/IntelCIS.2015.7397286
Afonso MNascimento J(2015)Predictive multiple motion fields for trajectory completion: Application to surveillance systems2015 IEEE International Conference on Image Processing (ICIP)10.1109/ICIP.2015.7351262(2547-2551)Online publication date: Sep-2015
https://doi.org/10.1109/ICIP.2015.7351262
Hu WTian GLi XMaybank S(2013)An Improved Hierarchical Dirichlet Process-Hidden Markov Model and Its Application to Trajectory Modeling and RetrievalInternational Journal of Computer Vision10.1007/s11263-013-0638-8105:3(246-268)Online publication date: 1-Dec-2013
https://dl.acm.org/doi/10.1007/s11263-013-0638-8
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents