[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/3347146.3359098acmconferencesArticle/Chapter ViewAbstractPublication PagesgisConference Proceedingsconference-collections
poster
Public Access

Simple Distances for Trajectories via Landmarks

Published: 05 November 2019 Publication History

Abstract

We develop a new class of distances for trajectories, based on the distance to a set of landmarks. These distances easily and interpretably map objects to a Euclidean space, are simple to compute, and perform well in data analysis tasks. For trajectories, they match and in some cases significantly out-perform all state-of-the-art other metrics, can effortlessly be used in k-means clustering, and directly plugged into approximate nearest neighbor approaches which immediately out-perform the best recent advances in trajectory similarity search by several orders of magnitude. These distances do not require complicated alignment (common in trajectory case). We show reasonable and often simple conditions under which these distances are metrics.

References

[1]
Maria Astefanoaei, Paul Cesaretti, Panagiota Katsikouli, and Mayank Goswami and Rik Sarkar. 2018. Multi-resolution sketches and locality sensitive hashing for fast trajectory processing. In SIGSPATIAL.
[2]
Lei Chen, M. Tamer Özsu, and Vincent Oria. 2005. Robust and fast similarity search for moving object trajectories. In SIGMOD.
[3]
Michael O. Cruz, Hendrik Macedo, R. Barreto, and Adolfo Guimaraes. 2016. GPS Trajectories Data Set. https://archive.ics.uci.edu/ml/datasets/GPS+Trajectories
[4]
Thomas Eiter and Heikki Mannila. 1994. Computing Discrete Frechet Distance. Technical Report. Christian Doppler Laboratory for Expert Systems.
[5]
Yixiang Fang, Reynold Cheng, Wenbin Tang, Silviu Maniu, and Xuan S. Yang:. 2016. Scalable algorithms for nearest-neighbor joins on big trajectory data. In ICDE.
[6]
Elias Frentzos, Kostas Gratsias, Nikos Pelekis, and Yannis Theodoridis. 2005. Nearest Neighbor Search on Moving Object Trajectories. In SSTD.
[7]
Ralf Hartmut Güting, Thomas Behr, and Jianqiu Xu. 2010. Efficient k-nearest neighbor search on moving object trajectories. In VLDB.
[8]
Dan Lin, Rui Zhang, and Aoying Zhou. 2006. Indexing Fast Moving Objects for kNN Queries Based on Nearest Landmarks. GeoInformatica 10 (2006), 423--445.
[9]
Facundo Mémoli. 2008. Gromov-Hausdorff distances in Euclidean spaces. Nonrigid shape analysis and deformable image registration Workshop (2008).
[10]
Jeff M. Phillips and Pingfan Tang. 2019. Simple Distances for Trajectories via Landmarks. Technical Report. arXiv: 1804.11284.
[11]
Jeff M. Phillips and Pingfan Tang. 2019. Sketched MinDist. Technical Report. arXiv: 1907.02171.
[12]
Zeyuan Shang, Guoliang Li, and Zhifeng Bao. 2018. DITA: Distributed in-memory trajectory analytics. In SIGMOD.
[13]
Michail Vlachos, George Kollios, and Dimitrios Gunopulos. 2002. Discovering similar multidimensional trajectories. In ICDE.
[14]
Fei Wu, Zhenhui Li, Wang-Chien Lee, Hongjian Wang, and Zhuojie Huang. 2015. Semantic Annotation of Mobility Data using Social Media. In WWW.
[15]
Dong Xie, Feifei Li, and Jeff M. Phillips. 2017. Distributed trajectory similarity search. In VLDB.
[16]
Byoung-Kee Yi, H.V. Jagadish, and Christos Faloutsos. 1998. Efficient retrieval of similar time sequences under time warping. In ICDE.
[17]
Zhang Zhang, Kaiqi Huang, and Tieniu Tan. 2006. Comparison of similarity measures for trajectory clustering in outdoor surveillance scenes. In ICPR.
[18]
Yu Zheng, Hao Fu, Xing Xie, Wei-Ying Ma, and Quannan Li. 2011. Geolife GPS trajectory dataset - User Guide. https://www.microsoft.com/en-us/research/publication/geolife-gps-trajectory-dataset-user-guide/

Cited By

View all
  • (2024)Spatio-Temporal Trajectory Similarity Measures: A Comprehensive Survey and Quantitative StudyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3323535(1-21)Online publication date: 2024
  • (2022)An experimental study on classifying spatial trajectoriesKnowledge and Information Systems10.1007/s10115-022-01802-565:4(1587-1609)Online publication date: 20-Dec-2022

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
SIGSPATIAL '19: Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
November 2019
648 pages
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2019

Check for updates

Author Tags

  1. sketching1
  2. trajectory classification
  3. trajectory similarity

Qualifiers

  • Poster
  • Research
  • Refereed limited

Funding Sources

Conference

SIGSPATIAL '19
Sponsor:

Acceptance Rates

SIGSPATIAL '19 Paper Acceptance Rate 34 of 161 submissions, 21%;
Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)70
  • Downloads (Last 6 weeks)5
Reflects downloads up to 10 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Spatio-Temporal Trajectory Similarity Measures: A Comprehensive Survey and Quantitative StudyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3323535(1-21)Online publication date: 2024
  • (2022)An experimental study on classifying spatial trajectoriesKnowledge and Information Systems10.1007/s10115-022-01802-565:4(1587-1609)Online publication date: 20-Dec-2022

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media