Article

Spatio-temporal similarity analysis between trajectories on road networks

Authors:

Jung-Rae Hwang,

Hye-Young Kang,

Ki-Joune LiAuthors Info & Claims

ER'05: Proceedings of the 24th international conference on Perspectives in Conceptual Modeling

Pages 280 - 289

https://doi.org/10.1007/11568346_30

Published: 24 October 2005 Publication History

Abstract

In order to analyze the behavior of moving objects, a measure for determining the similarity of trajectories needs to be defined. Although research has been conducted that retrieved similar trajectories of moving objects in Euclidean space, very little research has been conducted on moving objects in the space defined by road networks. In terms of real applications, most moving objects are located in road network space rather than in Euclidean space. In this paper, we investigate the properties of similar trajectories in road network space. And we propose a method to retrieve similar trajectories based on this observation and similarity measure between trajectories on road network space. Experimental results show that this method provides not only a practical method for searching for similar trajectories but also a clustering method for trajectories.

References

[1]

Dieter Pfoser, Christian S. Jensen, and Yannis Theodoridis. Novel Approaches in Query Processing for Moving Object Trajectories. In Proceedings of the 26th International Conference on Very Large Data Bases, pages 395-406, 2000.

Digital Library

Google Scholar

[2]

Michail Vlachos, George Kollios, and Dimitrios Gunopulos. Discovering Similar Multidimensional Trajectories. In Proceedings of the Eighteenth International Conference on Data Engineering, pages 673-684. IEEE Computer Society, 2002.

Digital Library

Google Scholar

[3]

Yutaka Yanagisawa, Jun ichi Akahani, and Tetsuji Satoh. Shape-Based Similarity Query for Trajectory of Mobile Objects. In Proceedings of the Fourth International Conference on Mobile Data Management, pages 63-77. Springer-Verlag, 2003.

Digital Library

Google Scholar

[4]

Laurynas Speicys, Christian S. Jensen, and Augustas Kligys. Computational Data Modeling for Network-constrained Moving Objects. In Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems, pages 118-125, 2003.

Digital Library

Google Scholar

[5]

Michalis Vazirgiannis and Ouri Wolfson. A Spatiotemporal Model and Language for Moving Objects on Road Networks. In Proceedings of the Seventh International Symposium on Spatial and Temporal Databases, pages 20-35. Springer-Verlag, 2001.

Digital Library

Google Scholar

[6]

Ramaswamy Hariharan and Kentaro Toyama. Project Lachesis: Parsing and Modeling Location Histories. In Third International Conference, GIScience, pages 106-124. Springer-Verlag, 2004.

Google Scholar

[7]

K. Hornsby and M. Egenhofer. Modeling Moving Objects over Multiple Granularities. Annals of Mathematics and Artificial Intelligence, 36:177-194, 2002.

Digital Library

Google Scholar

[8]

Christian S. Jensen, Jan Kolárvr, Torben Bach Pedersen, and Igor Timko. Nearest Neighbor Queries in Road Networks. In Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems, pages 1-8, 2003.

Digital Library

Google Scholar

[9]

Nico Van de Weghe, Anthony G. Cohn, Peter Bogaert, and Philippe De Maeyer. Representation of Moving Objects along a Road Network. In Proceedings of the twelfth International Conference on Geoinformatics.

Google Scholar

[10]

Michail Vlachos, Dimitrios Gunopulos, and George Kollios. Robust Similarity Measures for Mobile Object Trajectories. In Proceedings of the Thirteenth International Workshop on Database and Expert Systems Applications, pages 721-728. IEEE Computer Society, 2002.

Digital Library

Google Scholar

[11]

Choon-Bo Shim and Jae-Woo Chang. Similar Sub-Trajectory Retrieval for Moving Objects in Spatio-temporal Databases. In Proceedings of the Seventh East-European Conference on Advances in Databases and Informations Systems, pages 308-322. Springer-Verlag, 2003.

Google Scholar

[12]

Tian Zhang, Raghu Ramakrishnan, and Miron Livny. BIRCH: An Efficient Data Clustering Method for Very Large Databases. In Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, pages 103-114. ACM Press, 1996.

Digital Library

Google Scholar

[13]

Haixun Wang, Wei Wang, Jiong Yang, and Philip S. Yu. Clustering by Pattern Similarity in Large Data Sets. In Proceedings of the 2002 ACM SIGMOD international conference on Management of data, pages 394-405. ACM Press, 2002.

Digital Library

Google Scholar

[14]

Swanwa Liao, Mario A. Lopez, and Scott T. Leutenegger. High Dimensional Similartity Search With Space Filling Curves. In Proceedings of the seventeenth International Conference on Data Engineering, pages 615-622. IEEE Computer Society, 2001.

Digital Library

Google Scholar

Cited By

View all

Sousa RBoukerche ALoureiro A(2020)Vehicle Trajectory SimilarityACM Computing Surveys10.1145/340609653:5(1-32)Online publication date: 28-Sep-2020
https://dl.acm.org/doi/10.1145/3406096
Doocy LPrager SKider Jr JWiegand R(2019)Robust Path Matching and Anomalous Route Detection Using Posterior Weighted GraphsACM Transactions on Spatial Algorithms and Systems10.1145/33389055:2(1-19)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3338905
Abdalla MHendawi AElGamal NMokhtar HAli MKrumm J(2018)SimilarMoveProceedings of the 2nd ACM SIGSPATIAL Workshop on Prediction of Human Mobility10.1145/3283590.3283593(15-24)Online publication date: 6-Nov-2018
https://dl.acm.org/doi/10.1145/3283590.3283593
Show More Cited By

Spatio-temporal similarity analysis between trajectories on road networks
1. Information systems
  1. Information systems applications

Recommendations

Searching for similar trajectories on road networks using spatio-temporal similarity
ADBIS'06: Proceedings of the 10th East European conference on Advances in Databases and Information Systems

In order to search similar moving object trajectories, the previously used methods focused on Euclidean distance and considered only spatial similarity. Euclidean distance is not appropriate for road network space, where the distance is limited to the ...
Spatio-temporal Similarity Measure for Trajectories on Road Networks
ICICSE '09: Proceedings of the 2009 Fourth International Conference on Internet Computing for Science and Engineering

Trajectories play an important role in analyzing the behavior of moving objects. Many researches have been conducted that retrieved similar trajectories of moving objects in Euclidean space rather than in road network space. However, in real ...
Multi-Entry Generalized Search Trees for Indexing Trajectories
SIGSPATIAL '24: Proceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems

The idea of generalized indices is one of the success stories of database systems research. It has found its way to implementation in common database systems. GiST (Generalized Search Tree) and SP-GiST (Space-Partitioned Generalized Search Tree) are two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ER'05: Proceedings of the 24th international conference on Perspectives in Conceptual Modeling

October 2005

474 pages

ISBN:3540293957

Editors:
Jacky Akoka
Conservatoire National des Arts et Métiers and INT, France
,
Stephen W. Liddle
Information Systems Department, Brigham Young Univeristy, Provo, Utah
,
Il-Yeol Song
College of Information Science and Technology, Drexel University, Provo, Utah
,
Michela Bertolotto
College of Information Science and Technology, University College, Dublin, Ireland
,
Isabelle Comyn-Wattiau
College of Information Science and Technology, CEDRIC-CNAM and ESSEC, Dublin

In-Cooperation

GI Gesellschaft für Informatik e.V.: GI Gesellschaft für Informatik e.V.
Austrian Comp Soc: Austrian Computer Society

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 24 October 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Sousa RBoukerche ALoureiro A(2020)Vehicle Trajectory SimilarityACM Computing Surveys10.1145/340609653:5(1-32)Online publication date: 28-Sep-2020
https://dl.acm.org/doi/10.1145/3406096
Doocy LPrager SKider Jr JWiegand R(2019)Robust Path Matching and Anomalous Route Detection Using Posterior Weighted GraphsACM Transactions on Spatial Algorithms and Systems10.1145/33389055:2(1-19)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3338905
Abdalla MHendawi AElGamal NMokhtar HAli MKrumm J(2018)SimilarMoveProceedings of the 2nd ACM SIGSPATIAL Workshop on Prediction of Human Mobility10.1145/3283590.3283593(15-24)Online publication date: 6-Nov-2018
https://dl.acm.org/doi/10.1145/3283590.3283593
Ayhan SSamet H(2015)DICLERGEProceedings of the 8th ACM SIGSPATIAL International Workshop on Computational Transportation Science10.1145/2834882.2834887(7-14)Online publication date: 3-Nov-2015
https://dl.acm.org/doi/10.1145/2834882.2834887
Evans MOliver DShekhar SHarvey FKoonin SWolfson OZheng Y(2013)Fast and exact network trajectory similarity computationProceedings of the 2nd ACM SIGKDD International Workshop on Urban Computing10.1145/2505821.2505835(1-8)Online publication date: 11-Aug-2013
https://dl.acm.org/doi/10.1145/2505821.2505835
Xia YWang GZhang XKim GBae H(2010)Research of spatio-temporal similarity measure on network constrained trajectory dataProceedings of the 5th international conference on Rough set and knowledge technology10.5555/1929344.1929421(491-498)Online publication date: 15-Oct-2010
https://dl.acm.org/doi/10.5555/1929344.1929421
Chang JChowdhury NLee H(2010)New travel time prediction algorithms for intelligent transportation systemsJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.5555/1734979.173498121:1, 2(5-7)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.5555/1734979.1734981
Abraham SLal P(2010)Trajectory similarity of network constrained moving objects and applications to traffic securityProceedings of the 2010 Pacific Asia conference on Intelligence and Security Informatics10.1007/978-3-642-13601-6_5(31-43)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-13601-6_5
Kharrat APopa IZeitouni KFaiz SMenga DSèdes F(2009)Caractérisation de la densité de trafic et de son évolution à partir de trajectoires d'objets mobilesProceedings of the 5th French-Speaking Conference on Mobility and Ubiquity Computing10.1145/1739268.1739275(33-40)Online publication date: 7-Jul-2009
https://dl.acm.org/doi/10.1145/1739268.1739275
Jensen CTiešytė DCahill V(2008)TransDBProceedings of the 5th Annual International Conference on Mobile and Ubiquitous Systems: Computing, Networking, and Services10.4108/ICST.MOBIQUITOUS2008.3890(1-6)Online publication date: 21-Jul-2008
https://dl.acm.org/doi/10.4108/ICST.MOBIQUITOUS2008.3890
Show More Cited By

Abstract

References

Cited By

Recommendations

Searching for similar trajectories on road networks using spatio-temporal similarity

Spatio-temporal Similarity Measure for Trajectories on Road Networks

Multi-Entry Generalized Search Trees for Indexing Trajectories

Comments

Information

Published In

Sponsors

In-Cooperation

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations