LIPIcs.SEA.2020.24.pdf
- Filesize: 1.87 MB
- 13 pages
Document
Finding Structurally and Temporally Similar Trajectories in Graphs
Authors
-
Part of:
Volume:
18th International Symposium on Experimental Algorithms (SEA 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Experimental Algorithms (SEA) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-12
File
Document Identifiers
Acknowledgements
We are in debt with Ioanna Miliou for helping us with the Milan GPS dataset.
Cite AsGet BibTex
Roberto Grossi, Andrea Marino, and Shima Moghtasedi. Finding Structurally and Temporally Similar Trajectories in Graphs. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SEA.2020.24
https://doi.org/10.4230/LIPIcs.SEA.2020.24
Abstract
The analysis of similar motions in a network provides useful information for different applications like route recommendation. We are interested in algorithms to efficiently retrieve trajectories that are similar to a given query trajectory. For this task many studies have focused on extracting the geometrical information of trajectories. In this paper we investigate the properties of trajectories moving along the paths of a network. We provide a similarity function by making use of both the temporal aspect of trajectories and the structure of the underlying network. We propose an approximation technique that offers the top-k similar trajectories with respect to a query trajectory in an efficient way with acceptable precision. We investigate our method over real-world networks, and our experimental results show the effectiveness of the proposed method.
Subject Classification
ACM Subject Classification
- Information systems → Similarity measures
- Information systems → Nearest-neighbor search
Keywords
- Graph trajectory
- approximated similarity
- top-k similarity query
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Rakesh Agrawal, Christos Faloutsos, and Arun Swami. Efficient similarity search in sequence databases. In International conference on foundations of data organization and algorithms, pages 69-84. Springer, 1993.
-
Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational geometry: algorithms and applications. Springer-Verlag TELOS, 2008.
-
Lei Chen and Raymond Ng. On the marriage of Lp-norms and edit distance. In Proceedings of the Thirtieth international conference on Very large data bases-Volume 30, pages 792-803. VLDB Endowment, 2004.
-
Lei Chen, M Tamer Özsu, and Vincent Oria. Robust and fast similarity search for moving object trajectories. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data, pages 491-502. ACM, 2005.
-
Zaiben Chen, Heng Tao Shen, Xiaofang Zhou, Yu Zheng, and Xing Xie. Searching trajectories by locations: an efficiency study. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pages 255-266. ACM, 2010.
-
Martin Erwig. The graph Voronoi diagram with applications. Networks: An International Journal, 36(3):156-163, 2000.
-
Christos Faloutsos, Mudumbai Ranganathan, and Yannis Manolopoulos. Fast subsequence matching in time-series databases. In Proceedings of ACM SIGMOD, pages 419-429, Minneapolis, MN, 1994.
-
Jung-Rae Hwang, Hye-Young Kang, and Ki-Joune Li. Searching for similar trajectories on road networks using spatio-temporal similarity. In East European Conference on Advances in Databases and Information Systems, pages 282-295. Springer, 2006.
-
Eamonn Keogh and Chotirat Ann Ratanamahatana. Exact indexing of dynamic time warping. Knowledge and information systems, 7(3):358-386, 2005.
-
Cristina Ioana Muntean, Franco Maria Nardini, Fabrizio Silvestri, and Ranieri Baraglia. On learning prediction models for tourists paths. ACM Transactions on Intelligent Systems and Technology (TIST), 7(1):1-34, 2015.
-
Shuo Shang, Ruogu Ding, Kai Zheng, Christian S Jensen, Panos Kalnis, and Xiaofang Zhou. Personalized trajectory matching in spatial networks. The VLDB Journal, 23(3):449-468, 2014.
-
Eleftherios Tiakas, Apostolos N Papadopoulos, Alexandros Nanopoulos, Yannis Manolopoulos, Dragan Stojanovic, and Slobodanka Djordjevic-Kajan. Trajectory similarity search in spatial networks. In null, pages 185-192. IEEE, 2006.
-
Eleftherios Tiakas and Dimitrios Rafailidis. Scalable trajectory similarity search based on locations in spatial networks. In Model and Data Engineering, pages 213-224. Springer, 2015.
-
Michail Vlachos, George Kollios, and Dimitrios Gunopulos. Discovering similar multidimensional trajectories. In Data Engineering, 2002. Proceedings. 18th International Conference on, pages 673-684. IEEE, 2002.
-
Jung-Im Won, Sang-Wook Kim, Ji-Haeng Baek, and Junghoon Lee. Trajectory clustering in road network environment. In Computational Intelligence and Data Mining, 2009. CIDM'09. IEEE Symposium on, pages 299-305. IEEE, 2009.
-
Ying Xia, Guo-Yin Wang, Xu Zhang, Gyoung-Bae Kim, and Hae-Young Bae. Spatio-temporal similarity measure for network constrained trajectory data. International Journal of Computational Intelligence Systems, 4(5):1070-1079, 2011.