Document Open Access Logo

Similarity Search for Spatial Trajectories Using Online Lower Bounding DTW and Presorting Strategies

Authors Marie Kiermeier, Martin Werner

PDF
Thumbnail PDF

File

LIPIcs.TIME.2017.18.pdf
  • Filesize: 2.44 MB
  • 15 pages

Document Identifiers

Author Details

Marie Kiermeier
Martin Werner

Cite As Get BibTex

Marie Kiermeier and Martin Werner. Similarity Search for Spatial Trajectories Using Online Lower Bounding DTW and Presorting Strategies. In 24th International Symposium on Temporal Representation and Reasoning (TIME 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 90, pp. 18:1-18:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.TIME.2017.18

Abstract

Similarity search with respect to time series has received much attention from research and industry in the last decade. Dynamic time warping is one of the most widely used distance measures in this context. This is due to the simplicity of its definition and the surprising quality of dynamic time warping for time series classification. However, dynamic time warping is not well-behaving with respect to many dimensionality reduction techniques as it does not fulfill the triangle inequality. Additionally, most research on dynamic time warping has been performed with one-dimensional time series or in multivariate cases of varying dimensions. With this paper, we propose three extensions to LB_Rotation for two-dimensional time series (trajectories). We simplify LB_Rotation and adapt it to the online and data streaming case and show how to tune the pruning ratio in similarity search by using presorting strategies based on simple summaries of trajectories. Finally, we provide a thorough valuation of these aspects on a large variety of datasets of spatial trajectories.

Subject Classification

Keywords
  • Trajectory Computing
  • Similarity Search
  • Dynamic Time Warping
  • Lower Bounds
  • k Nearest Neighbor Search
  • Spatial Presorting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Assaf Almog, Avi Levi, and Alfred M. Bruckstein. Spatial de-interlacing using dynamic time warping. In IEEE International Conference on Image Processing, volume 2, pages 1006-1010. IEEE, 2005. Google Scholar
  2. Anthony Bagnall, Jason Lines, Jon Hills, and Aaron Bostrom. Time-series classification with COTE: the collective of transformation-based ensembles. IEEE Transactions on Knowledge and Data Engineering, 27(9):2522-2535, 2015. Google Scholar
  3. Christian Bauckhage and Christian Thurau. Making archetypal analysis practical. In Pattern Recognition, pages 272-281. Springer, 2009. Google Scholar
  4. Donald J. Berndt and James Clifford. Using dynamic time warping to find patterns in time series. In KDD workshop, pages 359-370. Seattle, WA, 1994. Google Scholar
  5. Lorenzo Bracciale, Marco Bonola, Pierpaolo Loreti, Giuseppe Bianchi, Raul Amici, and Antonello Rabuffi. CRAWDAD dataset roma/taxi (v. 2014-07-17). Downloaded from http://crawdad.org/roma/taxi/20140717, July 2014. URL: http://dx.doi.org/10.15783/C7QC7M.
  6. Won-Du Chang and Jungpil Shin. Modified dynamic time warping for stroke-based on-line signature verification. In Ninth International Conference on Document Analysis and Recognition (ICDAR), volume 2, pages 724-728. IEEE, 2007. Google Scholar
  7. Hui Ding, Goce Trajcevski, Peter Scheuermann, Xiaoyue Wang, and Eamonn Keogh. Querying and mining of time series data: experimental comparison of representations and distance measures. Proceedings of the VLDB Endowment, 1(2):1542-1552, 2008. Google Scholar
  8. David H. Douglas and Thomas K. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica: The International Journal for Geographic Information and Geovisualization, 10(2):112-122, 1973. Google Scholar
  9. Fosca Giannotti and Dino Pedreschi. Mobility, data mining and privacy: Geographic knowledge discovery. Springer Science &Business Media, 2008. Google Scholar
  10. Xudong Gong, Yan Xiong, Wenchao Huang, Lei Chen, Qiwei Lu, and Yiqing Hu. Fast similarity search of multi-dimensional time series via segment rotation. In Database Systems for Advanced Applications, pages 108-124. Springer, 2015. Google Scholar
  11. Fumitada Itakura. Minimum prediction residual principle applied to speech recognition. IEEE Transactions on Acoustics, Speech and Signal Processing, 23(1):67-72, 1975. Google Scholar
  12. Eamonn Keogh and Chotirat Ann Ratanamahatana. Exact indexing of dynamic time warping. Knowledge and information systems, 7(3):358-386, 2005. Google Scholar
  13. Sang-Wook Kim, Sanghyun Park, and Wesley W. Chu. An index-based approach for similarity search supporting time warping in large sequence databases. In Proceedings of the 17th International Conference on Data Engineering, pages 607-614. IEEE, 2001. Google Scholar
  14. Benoit Legrand, C. S. Chang, S. H. Ong, Soek-Ying Neo, and Nallasivam Palanisamy. Chromosome classification using dynamic time warping. Pattern Recognition Letters, 29(3):215-222, 2008. Google Scholar
  15. Daniel Lemire. Faster retrieval with a two-pass dynamic-time-warping lower bound. Pattern recognition, 42(9):2169-2180, 2009. Google Scholar
  16. M. Lichman. UCI machine learning repository. http://archive.ics.uci.edu/ml, 2013.
  17. Patrick Mair, Jan de Leeuw, and Patrick J. F. Groenen. Multidimensional Scaling in R: SMACOF. URL: https://cran.r-project.org/web/packages/smacof/vignettes/smacof.pdf.
  18. Andrés Marzal, Vicente Palazón, and Guillermo Peris. Contour-based shape retrieval using dynamic time warping. In Current Topics in Artificial Intelligence, pages 190-199. Springer, 2005. Google Scholar
  19. Gustavo Niemeyer. Geohash. http://geohash.org/, 2008.
  20. Toni M. Rath and R. Manmatha. Lower-bounding of dynamic time warping distances for multivariate time series. Available at http://works.bepress.com/r_manmatha/19/, 2003.
  21. Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech and Signal Processing, 26(1):43-49, 1978. Google Scholar
  22. Stan Salvador and Philip Chan. Toward accurate dynamic time warping in linear time and space. Intelligent Data Analysis, 11(5):561-580, 2007. Google Scholar
  23. V. M. Velichko and N. G. Zagoruyko. Automatic recognition of 200 words. International Journal of Man-Machine Studies, 2(3):223-234, 1970. Google Scholar
  24. Haozhou Wang, Han Su, Kai Zheng, Shazia Sadiq, and Xiaofang Zhou. An effectiveness study on trajectory similarity measures. In Proceedings of the Twenty-Fourth Australasian Database Conference-Volume 137, pages 13-22. Australian Computer Society, Inc., 2013. Google Scholar
  25. Martin Werner. Dataset containing trajectories of four players playing one hour of Urban Terror Capture and Hold on the map Prague. Available at http://trajectorycomputing.com/datasets/prague-ego-shooter-dataset/, 2014.
  26. Martin Werner. BACR: Set Similarities with Lower Bounds and Application to Spatial Trajectories. In 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2015), 2015. Google Scholar
  27. Martin Werner. GISCUP 2015: Notes on Routing with Polygonal Constraints. In SIGSPATIAL GIS CUP 15, in conjunction with 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2015), 2015. URL: http://www.martinwerner.de/preprint/GISCUP.pdf.
  28. Martin Werner. Dataset containing 500 random shortest paths in greater San Francisco Area. Available at http://www.martinwerner.de/files/fastest_sanfrancisco.tgz, 2016.
  29. Byoung-Kee Yi, H. V. Jagadish, and Christos Faloutsos. Efficient retrieval of similar time sequences under time warping. In Proceedings of the 14th International Conference on Data Engineering, pages 201-208. IEEE, 1998. Google Scholar
  30. Chun-Ting Zhang, Ren Zhang, and Hong-Yu Ou. The Z curve database: a graphic representation of genome sequences. Bioinformatics, 19(5):593-599, 2003. Google Scholar
  31. Yu Zheng, Quannan Li, Yukun Chen, Xing Xie, and Wei-Ying Ma. Understanding mobility based on GPS data. In Proceedings of the 10th international conference on Ubiquitous computing, pages 312-321. ACM, 2008. Google Scholar
  32. Yu Zheng, Xing Xie, and Wei-Ying Ma. GeoLife: A Collaborative Social Networking Service among User, Location and Trajectory. IEEE Data Engineering Bulletin, 33(2):32-39, 2010. Google Scholar
  33. Yu Zheng and Xiaofang Zhou. Computing with spatial trajectories. Springer Science &Business Media, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact