×

Semantic trajectory representation and retrieval via hierarchical embedding. (English) Zbl 1474.68345

Summary: Trajectory mining has gained growing attention due to its emerging applications, such as location-based services, urban computing, and movement behavior analyses. One critical and fundamental mining task is to retrieve specific locations or trajectories that satisfy particular patterns. However, existing approaches mainly represent the trajectory as a collection of geographic and temporal features, so the latent semantic properties are barely considered. In this paper, we introduce a new semantic trajectory representation method, which considers trajectory structures, temporal information, and domain knowledge to make efficient semantic retrieval possible. Specifically, we first introduce a synchronization-based model to identify multi-resolution regions of interest (ROIs) to extract structures from disordered raw trajectories. Afterward, we proposed a hierarchical embedding model to embed ROIs as well as trajectories on the hierarchical ROI network as continuous vectors by considering multiple kinds of semantic similarity. As a result, users can easily retrieve desirable ROIs or trajectories by computing the similarity among embedded vectors. Experiments show that our approach excels both classical trajectory metric-based models and state-of-the-art deep network embedding models in terms of retrieving interpretable ROIs and trajectories.

MSC:

68T30 Knowledge representation
62H30 Classification and discrimination; cluster analysis (statistical aspects)
68P20 Information storage and retrieval of data
Full Text: DOI

References:

[1] J.D. Mazimpaka, S. Timpf, Trajectory data mining: a review of methods and applications, vol. 13, 2016, pp. 61-99, doi: 10.5311/JOSIS.2016.13.263, URL: https://doi.org/10.5311/JOSIS.2016.13.263.
[2] Bogorny, V.; Kuijpers, B.; Alvares, L. O., ST-DMQL: a semantic trajectory data mining query language, Int. J. Geogr. Inf. Sci., 23, 10, 1245-1276 (2009), URL:http://www.informaworld.com/smpp/content
[3] Yuan, N. J.; Zheng, Y.; Zhang, L.; Xie, X., T-finder: a recommender system for finding passengers and vacant taxis, IEEE Trans. Knowl. Data Eng., 2390-2403 (25(10), 2013,), URL: https://doi.org/10.1109/TKDE.2012.153
[4] Anagnostopoulos, A.; Atassi, R.; Becchetti, L.; Fazzone, A.; Silvestri, F., Tour recommendation for groups, Data Min. Knowl. Discov., 31, 5, 1157-1188 (2017), URL: https://doi.org/10.1007/s10618-016-0477-7 · Zbl 1411.90287
[5] J.-G. Lee, J. Han, K.-Y. Whang, Trajectory clustering: A partition-and-group framework, in: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data, SIGMOD ’07, ACM, New York, NY, USA, 2007, pp. 593-604, doi: 10.1145/1247480.1247546. URL: http://doi.acm.org/10.1145/1247480.1247546.
[6] W.-C. Lee, J. Krumm, in: Computing with Spatial Trajectories, 2011, pp. 3-33, doi: 10.1007/978-1-4614-1629-6_1, URL:https://link.springer.com/chapter/10.1007
[7] Annoni, R.; Forster, C. H.Q., Analysis of aircraft trajectories using fourier descriptors and kernel density estimation, (2012 15th International IEEE Conference on Intelligent Transportation Systems (2012)), 1441-1446, URL:https://ieeexplore.ieee.org/document/6338863
[8] Ardakani, I. S.; Hashimoto, K., Encoding bird’s trajectory using recurrent neural networks, 2017 IEEE International Conference on Mechatronics and Automation (ICMA), 1644-1649 (2017)
[9] B.-K. Yi, H.V. Jagadish, C. Faloutsos, Efficient retrieval of similar time sequences under time warping, in: Proceedings of the Fourteenth International Conference on Data Engineering, ICDE ’98, IEEE Computer Society, Washington, DC, USA, 1998, pp. 201-208 URL:http://dl.acm.org/citation.cfm?id=645483.653609.
[10] M. Vlachos, D. Gunopoulos, G. Kollios, Discovering similar multidimensional trajectories, in: Proceedings of the 18th International Conference on Data Engineering, ICDE ’02, IEEE Computer Society, Washington, DC, USA, 2002, pp. 673-684, URL:http://dl.acm.org/citation.cfm?id=876875.878994.
[11] L. Chen, M.T. Özsu, V. Oria, Robust and fast similarity search for moving object trajectories, in: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, SIGMOD ’05, ACM, New York, NY, USA, 2005, pp. 491-502, doi: 10.1145/1066157.1066213, URL: http://doi.acm.org/10.1145/1066157.1066213.
[12] T. Eiter, H. Mannila, Computing discrete fréchet distance, Tech. rep., 1994.
[13] Q. Li, Y. Zheng, X. Xie, Y. Chen, W. Liu, W.-Y. Ma, Mining user similarity based on location history, in: Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS ’08, ACM, New York, NY, USA, 2008, pp. 34:1-34:10, doi: 10.1145/1463434.1463477, URL: http://doi.acm.org/10.1145/1463434.1463477.
[14] Z. Li, B. Ding, J. Han, R. Kays, P. Nye, Mining periodic behaviors for moving objects, in: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’10, ACM, New York, NY, USA, 2010, pp. 1099-1108, doi: 10.1145/1835804.1835942. URL: http://doi.acm.org/10.1145/1835804.1835942.
[15] Y. Zheng, L. Liu, L. Wang, X. Xie, Learning transportation mode from raw gps data for geographic applications on the web, in: Proceedings of the 17th International Conference on World Wide Web, WWW ’08, ACM, New York, NY, USA, 2008, pp. 247-256, doi: 10.1145/1367497.1367532, URL: http://doi.acm.org/10.1145/1367497.1367532
[16] G. Kellaris, N. Pelekis, Y. Theodoridis, Trajectory compression under network constraints, in: Proceedings of the 11th International Symposium on Advances in Spatial and Temporal Databases, SSTD ’09, Springer-Verlag, Berlin, Heidelberg, 2009, pp. 392-398, doi: 10.1007/978-3-642-02982-0_27, URL: https://doi.org/10.1007/978-3-642-02982-0_27.
[17] Song, R.; Sun, W.; Zheng, B.; Zheng, Y., Press: A novel framework of trajectory compression in road networks, Proc. VLDB Endow., 7, 9, 661-672 (2014), URL https://doi.org/10.14778/2732939.2732940
[18] M. Gariel, A.N. Srivastava, E. Feron, Trajectory clustering and an application to airspace monitoring, in: Transactions on Intelligent Transportation Systems, vol. 12, 2011, pp. 1511-1524, doi: 10.1109/TITS.2011.2160628, URL:https://ieeexplore.ieee.org/abstract/document/5959983/.
[19] Q. Gao, F. Zhou, K. Zhang, G. Trajcevski, X. Luo, F. Zhang, Identifying human mobility via trajectory embeddings, in: Proceedings of the 26th International Joint Conference on Artificial Intelligence, IJCAI’17, AAAI Press, 2017, pp. 1689-1695, URL:http://dl.acm.org/citation.cfm?id=3172077.3172122.
[20] R. Agrawal, C. Faloutsos, A.N. Swami, Efficient similarity search in sequence databases, in: Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, FODO ’93, Springer-Verlag, Berlin, Heidelberg, 1993, pp. 69-84, URL:http://dl.acm.org/citation.cfm?id=645415.652239.
[21] Pfoser, D.; Jensen, C. S.; Theodoridis, Y., Novel approaches in query processing for moving object trajectories, (Proceedings of the 26th International Conference on Very Large Data Bases, VLDB ’00 (2000), Morgan Kaufmann Publishers Inc.: Morgan Kaufmann Publishers Inc. San Francisco, CA, USA), 395-406
[22] M.A. Nascimento, J.R.O. Silva, Towards historical r-trees, in: Proceedings of the 1998 ACM Symposium on Applied Computing, SAC ’98, ACM, New York, NY, USA, 1998, pp. 235-240, doi: 10.1145/330560.330692, URL: http://doi.acm.org/10.1145/330560.330692.
[23] V.P. Chakka, A. Everspaugh, J.M. Patel, Indexing large trajectory data sets with SETI, in: CIDR 2003, First Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 5-8, 2003, Online Proceedings, 2003, URL:http://www-db.cs.wisc.edu/cidr/cidr2003/program/p15.pdf.
[24] Bengio, Y.; Ducharme, R.; Vincent, P.; Janvin, C., A neural probabilistic language model, J. Mach. Learn. Res., 3, 1137-1155 (2003), URL:http://dl.acm.org/citation.cfm?id=944919.944966 · Zbl 1061.68157
[25] T. Mikolov, I. Sutskever, K. Chen, G. Corrado, J. Dean, Distributed representations of words and phrases and their compositionality, in: Proceedings of the 26th International Conference on Neural Information Processing Systems, vol. 2, NIPS’13, Curran Associates Inc., USA, 2013, pp. 3111-3119, URL:http://dl.acm.org/citation.cfm?id=2999792.2999959.
[26] Mitchell, J.; Lapata, M., Composition in distributional models of semantics, Cogn. Sci., 34, 8, 1388-1429 (2010), URL: https://doi.org/10.1111/j.1551-6709.2010.01106.x
[27] M. Iyyer, V. Manjunatha, J.L. Boyd-Graber, H.D. III, Deep unordered composition rivals syntactic methods for text classification, in: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing, ACL 2015, July 26-31, 2015, Beijing, China, Long Papers, vol. 1, 2015, pp. 1681-1691, URL:https://www.aclweb.org/anthology/P15-1162/.
[28] N. Kalchbrenner, E. Grefenstette, P. Blunsom, A convolutional neural network for modelling sentences, in: Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL 2014, June 22-27, 2014, Baltimore, MD, USA, Long Papers, vol. 1, 2014, pp. 655-665, URL:https://www.aclweb.org/anthology/P14-1062/.
[29] K.S. Tai, R. Socher, C.D. Manning, Improved semantic representations from tree-structured long short-term memory networks, in: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian Federation of Natural Language Processing, ACL 2015, July 26-31, 2015, Beijing, China, Long Papers, vol. 1, 2015, pp. 1556-1566, URL:https://www.aclweb.org/anthology/P15-1150/.
[30] Perozzi, B.; Al-Rfou, R.; Skiena, S., Deepwalk: Online learning of social representations, (Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14 (2014), Association for Computing Machinery: Association for Computing Machinery New York, NY, USA), 701-710
[31] T. Mikolov, K. Chen, G. Corrado, J. Dean, Efficient estimation of word representations in vector space, in: arXiv preprint arXiv:1301.3781, 2013.
[32] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, Q. Mei, Line: Large-scale information network embedding, in: Proceedings of the 24th International Conference on World Wide Web, WWW ’15, International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 2015, p. 1067-1077, doi: 10.1145/2736277.2741093.
[33] Grover, A.; Leskovec, J., Node2vec: Scalable feature learning for networks, (Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16 (2016), Association for Computing Machinery: Association for Computing Machinery New York, NY, USA), 855-864, URL: https://doi.org/10.1145/2939672.2939754
[34] Yin, H.; Zou, L.; Nguyen, Q. V.H.; Huang, Z.; Zhou, X., Joint event-partner recommendation in event-based social networks, (2018 IEEE 34th International Conference on Data Engineering (ICDE) (2018)), 929-940
[35] Y. Dong, N.V. Chawla, A. Swami, Metapath2vec: Scalable representation learning for heterogeneous networks, in: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’17, ACM, New York, NY, USA, 2017, pp. 135-144, doi: 10.1145/3097983.3098036, URL: http://doi.acm.org/10.1145/3097983.3098036.
[36] J. Yu, M. Gao, J. Li, H. Yin, H. Liu, Adaptive implicit friends identification over heterogeneous network for social recommendation, in: Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM ’18, ACM, New York, NY, USA, 2018, pp. 357-366, doi: 10.1145/3269206.3271725, URL: http://doi.acm.org/10.1145/3269206.3271725.
[37] C. Böhm, C. Plant, J. Shao, Q. Yang, Clustering by synchronization, in: KDD’10, ACM, New York, NY, USA, 2010, pp. 583-592, doi: 10.1145/1835804.1835879, URL: http://doi.acm.org/10.1145/1835804.1835879.
[38] J. Shao, X. He, C. Bohm, Q. Yang, C. Plant, Synchronization-inspired partitioning and hierarchical clustering, IEEE Trans. Knowl. Data Eng. 25 (4) (2013) 893-905, doi: 10.1109/TKDE.2012.32, URL: https://doi.org/10.1109/TKDE.2012.32.
[39] C.S. Kim, C.S. Bae, H.J. Tcha, A phase synchronization clustering algorithm for identifying interesting groups of genes from cell cycle expression data, vol. 9, 2008, doi: 10.1186/1471-2105-9-56.
[40] P. Seliger, S.C. Young, L.S. Tsimring, Plasticity and learning in a network of coupled phase oscillators, Vol. 65, 2002, p. 041906. · Zbl 1244.34078
[41] J. Shao, Z. Han, Q. Yang, T. Zhou, Community detection based on distance dynamics, in: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’15, ACM, New York, NY, USA, 2015, pp. 1075-1084, doi: 10.1145/2783258.2783301, URL: http://doi.acm.org/10.1145/2783258.2783301.
[42] J. Shao, C. Gao, W. Zeng, J. Song, Q. Yang, Synchronization-inspired co-clustering and its application to gene expression data, in: 2017 IEEE International Conference on Data Mining, ICDM 2017, New Orleans, LA, USA, November 18-21, 2017, 2017, pp. 1075-1080, doi: 10.1109/ICDM.2017.141.
[43] Z. Zhang, D. Kang, C. Gao, J. Shao, Semisync: Semi-supervised clustering by synchronization, in: International Conference on Database Systems for Advanced Applications, Springer, 2019, pp. 358-362, doi: 10.1007/978-3-030-18590-9_45, URL: https://doi.org/10.1007/978-3-030-18590-9_45.
[44] Gao, C.; Zhao, Y.; Wu, R.; Yang, Q.; Shao, J., Semantic trajectory compression via multi-resolution synchronization-based clustering, Knowl.-Based Syst., 174, 177-193 (2019), URL: https://doi.org/10.1016/j.knosys.2019.03.006
[45] W. Blacoe, M. Lapata, A comparison of vector-based representations for semantic composition, in: Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, EMNLP-CoNLL ’12, Association for Computational Linguistics, Stroudsburg, PA, USA, 2012, pp. 546-556, URL: http://dl.acm.org/citation.cfm?id=2390948.2391011.
[46] J. Wieting, M. Bansal, K. Gimpel, K. Livescu, Towards universal paraphrastic sentence embeddings, in: 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016, URL: http://arxiv.org/abs/1511.08198.
[47] Kavraki, L. E.; Svestka, P.; Latombe, J.; Overmars, M. H., Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Trans. Robot. Automat., 12, 4, 566-580 (1996), URL: https://doi.org/10.1109/70.508439
[48] Y. Zheng, L. Zhang, X. Xie, W.-Y. Ma, Mining interesting locations and travel sequences from gps trajectories, in: Proceedings of the 18th International Conference on World Wide Web, WWW ’09, ACM, New York, NY, USA, 2009, pp. 791-800, doi: 10.1145/1526709.1526816, URL: http://doi.acm.org/10.1145/1526709.1526816.
[49] J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, Y. Huang, T-drive: Driving directions based on taxi trajectories, in: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS ’10, ACM, New York, NY, USA, 2010, pp. 99-108, doi: 10.1145/1869790.1869807, URL: http://doi.acm.org/10.1145/1869790.1869807.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.