More Web Proxy on the site http://driver.im/

article

Finding long and similar parts of trajectories

Authors:

Marc van Kreveld,

Jun LuoAuthors Info & Claims

Computational Geometry: Theory and Applications, Volume 44, Issue 9

Pages 465 - 476

https://doi.org/10.1016/j.comgeo.2011.05.004

Published: 01 November 2011 Publication History

Abstract

A natural time-dependent similarity measure for two trajectories is their average distance at corresponding times. We give algorithms for computing the most similar subtrajectories under this measure, assuming the two trajectories are given as two polygonal, possibly self-intersecting lines with time stamps. For the case when a minimum duration of the subtrajectories is specified and the subtrajectories must start at corresponding times, we give a linear-time algorithm. The algorithm is based on a result of independent interest: We present a linear-time algorithm to find, for a piece-wise monotone function, an interval of at least a given length that has minimum average value. In the case that the subtrajectories may start at non-corresponding times, it appears difficult to give exact algorithms, even if the duration of the subtrajectories is fixed. For this case, we give (1+@e)-approximation algorithms, for both fixed duration and when only a minimum duration is specified.

References

[1]

Barequet, G., Chen, D.Z., Daescu, O., Goodrich, M.T. and Snoeyink, J., Efficiently approximating polygonal paths in three and higher dimensions. Algorithmica. v33. 150-167.

[2]

T. Bernholt, F. Eisenbrand, T. Hofmeister, A geometric framework for solving subsequence problems in computational biology efficiently, in: Proc. 23rd ACM Symp. on Comput. Geom. (SOCG¿07), 2007, pp. 310-318.

Digital Library

[3]

Buchin, K., Buchin, M. and Gudmundsson, J., Constrained free space diagrams: a tool for trajectory analysis. International Journal of Geographical Information Science. v24. 1101-1125.

[4]

K. Buchin, M. Buchin, J. Gudmundsson, M. Löffler, J. Luo, Detecting commuting patterns by clustering subtrajectories, Int. J. Comput. Geom. and Appl., Special Issue: Selected Papers from the 19th Int. Symp. on Algorithms and Computation (ISAAC¿08), in press.

[5]

K. Buchin, M. Buchin, Y. Wang, Exact algorithms for partial curve matching via the Fréchet distance, in: Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA¿09), 2009, pp. 645-654.

[6]

Cao, H., Wolfson, O. and Trajcevski, G., Spatio-temporal data reduction with deterministic error bounds. VLDB Journal. v15. 211-228.

[7]

Chung, K.-M. and Lu, H.-I., An optimal algorithm for the maximum-density segment problem. SIAM J. Comput. v34. 373-387.

[8]

L. Chen, M. Tamer Özsu, V. Oria, Robust and fast similarity search for moving object trajectories, in: Proc. 2005 ACM SIGMOD Int. Conf. on Management of data (SIGMOD¿05), 2005, pp. 491-502.

Digital Library

[9]

E. Frentzos, K. Gratsias, Y. Theodoridis, Index-based most similar trajectory search, in: Proc. IEEE 23rd Int. Conf. on Data Engineering, 2007, pp. 816-825.

[10]

Goldwasser, M.H., Kao, M.-Y. and Lu, H.-I., Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications. J. Comput. Syst. Sci. v70. 128-144.

Digital Library

[11]

J. Gudmundsson, J. Katajainen, D. Merrick, C. Ong, T. Wolle, Compressing spatio-temporal trajectories, in: Proc. Int. Symp. on Algorithms and Computation (ISAAC¿07), 2007, pp. 763-775.

[12]

Gudmundsson, J., Laube, P. and Wolle, T., Movement patterns in spatio-temporal data. In: Shekhar, S., Xiong, H. (Eds.), Encyclopedia of GIS, Springer, Heidelberg. pp. 726-732.

[13]

Halperin, D., Arrangements. In: Goodman, J.E., O'Rourke, J. (Eds.), Handbook of Discrete and Computational Geometry, CRC Press. pp. 389-412.

[14]

E.J. Keogh, M.J. Pazzani, Scaling up dynamic time warping for datamining applications, in: Proc. 4th Asia-Pacific Conf. on Knowledge Discovery and Data Mining (PADKK¿00), 2000, pp. 285-289.

[15]

M. van Kreveld, J. Luo, The definition and computation of trajectory and subtrajectory similarity, in: Proc. 15th ACM Int. Symp. on Geographic Information Systems (ACM-GIS¿07), 2007, pp. 44-47.

[16]

Lee, J., Han, J., Li, X. and Gonzalez, H., TraClass: Trajectory classification using hierarchical region-based and trajectory-based clustering. Proceedings of the VLDB Endowment. v1. 1081-1094.

[17]

J. Lee, J. Han, K.-Y. Whang, Trajectory clustering: a partition-and-group framework, in: Proc. 2007 ACM SIGMOD International Conference on Management of Data (SIGMOD¿07), 2007, pp. 593-604.

[18]

Lin, Y.-L., Jiang, T. and Chao, K.-M., Efficient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis. J. Comput. Syst. Sci. v65. 570-586.

Digital Library

[19]

Nanni, M. and Pedreschi, D., Time-focused clustering of trajectories of moving objects. J. Intell. Inf. Syst. v27. 267-289.

Digital Library

[20]

Sinha, G. and Mark, D.M., Measuring similarity between geospatial lifelines in studies of environment health. J. Geographical Systems. v7. 115-136.

[21]

G. Trajcevski, H. Ding, P. Scheuermann, R. Tamassia, D. Vaccaro, Dynamics-aware similarity of moving objects trajectories, in: Proc. 15th ACM Int. Symp. on Geographic Information Systems (ACM-GIS¿07), 2007, pp. 1-8.

Digital Library

[22]

Vlachos, M., Kollios, G. and Gunopulous, D., Discovering similar multidimensional trajectories. In: Proc. 18th International Conference on Data Engineering (ICDE¿02), pp. 673-684.

[23]

M. Vlachos, D. Gunopulos, G. Das, Rotation invariant distance measures for trajectories, in: Proc. 10th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD¿04), 2004, pp. 707-712.

[24]

Y. Yanagisawa, J. Akahani, T. Satoh, Shape-based similarity query for trajectory of mobile objects, in: Proc. 4th Int. Conf. on Mobile Data Management (MDM¿03), 2003, pp. 63-77.

Cited By

Passos PDiniz AGalvão Silveira Fernandes AOliveira dos Passos JDantas de Macedo Borges LCampos T(2023)Improvements (or not!) in the hand trajectory of stroke patients due to practice of a virtual gameAdaptive Behavior - Animals, Animats, Software Agents, Robots, Adaptive Systems10.1177/1059712323116359531:4(365-378)Online publication date: 29-Jun-2023
https://dl.acm.org/doi/10.1177/10597123231163595
Tampakis PDoulkeridis CPelekis NTheodoridis Y(2020)Distributed Subtrajectory Join on Massive DatasetsACM Transactions on Spatial Algorithms and Systems10.1145/33736426:2(1-29)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3373642
Wiratma Lvan Kreveld MLöffler MStaals F(2019)An Experimental Evaluation of Grouping Definitions for Moving EntitiesProceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3347146.3359346(89-98)Online publication date: 5-Nov-2019
https://dl.acm.org/doi/10.1145/3347146.3359346
Show More Cited By

Finding long and similar parts of trajectories
1. Computing methodologies
  1. Computer graphics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Finding long and similar parts of trajectories
GIS '09: Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

A natural time-dependent similarity measure for two trajectories is their average distance at corresponding times. We give algorithms for computing the most similar subtrajectories under this measure, assuming the two trajectories are given as two ...
Computing similarity of coarse and irregular trajectories using space-time prisms
SIGSPATIAL'13: Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems

Increasing volumes of trajectory data require analysis methods which go beyond the visual. Methods for computing trajectory analysis typically assume linear interpolation between quasi-regular sampling points. This assumption, however, is often not ...
BACR: set similarities with lower bounds and application to spatial trajectories
SIGSPATIAL '15: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems

This paper proposes a length-independent feature representation of sets of strings based on Bloom filters called BACR for similarity search in databases. Further, we show how a Z-curve-based discretization of geospatial trajectories can be used in order ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Geometry: Theory and Applications

Computational Geometry: Theory and Applications Volume 44, Issue 9

November, 2011

79 pages

ISSN:0925-7721

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2011.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 November 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Passos PDiniz AGalvão Silveira Fernandes AOliveira dos Passos JDantas de Macedo Borges LCampos T(2023)Improvements (or not!) in the hand trajectory of stroke patients due to practice of a virtual gameAdaptive Behavior - Animals, Animats, Software Agents, Robots, Adaptive Systems10.1177/1059712323116359531:4(365-378)Online publication date: 29-Jun-2023
https://dl.acm.org/doi/10.1177/10597123231163595
Tampakis PDoulkeridis CPelekis NTheodoridis Y(2020)Distributed Subtrajectory Join on Massive DatasetsACM Transactions on Spatial Algorithms and Systems10.1145/33736426:2(1-29)Online publication date: 4-Feb-2020
https://dl.acm.org/doi/10.1145/3373642
Wiratma Lvan Kreveld MLöffler MStaals F(2019)An Experimental Evaluation of Grouping Definitions for Moving EntitiesProceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/3347146.3359346(89-98)Online publication date: 5-Nov-2019
https://dl.acm.org/doi/10.1145/3347146.3359346
Agarwal PFox KMunagala KNath APan JTaylor EVan den Bussche JArenas M(2018)Subtrajectory ClusteringProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3196959.3196972(75-87)Online publication date: 27-May-2018
https://dl.acm.org/doi/10.1145/3196959.3196972
Ta NLi GXie YLi CHao SFeng J(2017)Signature-Based Trajectory Similarity JoinIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2017.265182129:4(870-883)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1109/TKDE.2017.2651821
Park JKim TPark BCho HOssowski S(2016)Virtual running of vehicle trajectories for automatic map generationProceedings of the 31st Annual ACM Symposium on Applied Computing10.1145/2851613.2851712(572-579)Online publication date: 4-Apr-2016
https://dl.acm.org/doi/10.1145/2851613.2851712
Jiang ZEvans MOliver DShekhar S(2016)Identifying K Primary Corridors from urban bicycle GPS trajectories on a road networkInformation Systems10.1016/j.is.2015.10.00957:C(142-159)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1016/j.is.2015.10.009
Buchin MPurves RKnoblock CSchneider MKröger PKrumm JWidmayer P(2013)Computing similarity of coarse and irregular trajectories using space-time prismsProceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2525314.2525459(456-459)Online publication date: 5-Nov-2013
https://dl.acm.org/doi/10.1145/2525314.2525459
Gudmundsson Jvan Kreveld MStaals FKnoblock CSchneider MKröger PKrumm JWidmayer P(2013)Algorithms for hotspot computation on trajectory dataProceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2525314.2525359(134-143)Online publication date: 5-Nov-2013
https://dl.acm.org/doi/10.1145/2525314.2525359
Huang XLuo JWang XKoonin SWolfson OZheng Y(2013)Finding frequent sub-trajectories with time constraintsProceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing10.1145/2505821.2505824(1-8)Online publication date: 11-Aug-2013
https://dl.acm.org/doi/10.1145/2505821.2505824
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents