Abstract
Trajectories have been massively collected in a wide range of domains and play a critical role in data-driven task support. However, trajectories are often highly sparse and incomplete, which has become a key bottleneck that limits the applicability of trajectory analysis techniques. While many existing sequential models are seemingly applicable to the trajectory completion problem, they often suffer severely from data sparsity and irregularity and yield poor performance in practice. We propose an effective method, named TrajCom, for completing sparse and irregular trajectories. To address data sparsity, TrajCom leverages rich context information to filter a set of reference trajectories that correlate strongly with the target incomplete trajectory. Then, TrajCom learns time-aware encodings of these trajectories by a newly proposed time-aware recurrent unit. Moreover, a popularity-weighted attention mechanism is proposed to complete the missing locations. Extensive experiments on four datasets show that TrajCom outperforms competitive baselines with up to 25% relative improvements.
D. Yao and F. Guo—Equal contribution.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We consider 24 hourly intervals for both weekdays and weekends.
- 2.
There is an additional entry for \(\textbf{E}_{l}\), due to the placeholder location \(\tilde{l}\) used in the construction of the anchor record \({r}_{A}\).
- 3.
The time gap value for the first record in any trajectory is always zero, i.e. \(t^{gap}_{1} = 0\).
References
Bao, J., He, T., Ruan, S., Li, Y., Zheng, Y.: Planning bike lanes based on sharing-bikes’ trajectories. In: SIGKDD 2017, pp. 1377–1386 (2017)
Chandler, J., Obermaier, H., Joy, K.I.: Interpolation-based pathline tracing in particle-based flow visualization. IEEE Trans. Vis. Comput. Graph. 21(1), 68–80 (2015)
Cho, E., Myers, S.A., Leskovec, J.: Friendship and mobility: user movement in location-based social networks. In: SIGKDD 2011, pp. 1082–1090 (2011)
Feng, J., et al.: DeepMove: predicting human mobility with attentional recurrent networks. In: WWW 2018, pp. 1459–1468 (2018)
Feng, S., et al.: Personalized ranking metric embedding for next new POI recommendation. In: IJCAI 2015, pp. 2069–2075 (2015)
Han, P., Shang, S., Sun, A., Zhao, P., Zheng, K., Kalnis, P.: AUC-MF: point of interest recommendation with AUC maximization. In: ICDE 2019, pp. 1558–1561 (2019)
He, X., Liao, L., Zhang, H., Nie, L., Hu, X., Chua, T.: Neural collaborative filtering. In: WWW 2017, pp. 173–182 (2017)
Hu, G., Shao, J., Liu, F., Wang, Y., Shen, H.T.: IF-Matching: towards accurate map-matching with information fusion. In: ICDE 2017, pp. 9–10 (2017)
Kong, D., Wu, F.: HST-LSTM: a hierarchical spatial-temporal long-short term memory network for location prediction. In: IJCAI 2018, pp. 2341–2347 (2018)
Li, M., Ahmed, A., Smola, A.J.: Inferring movement trajectories from GPS snippets. In: WSDM 2015, pp. 325–334 (2015)
Li, R., Shen, Y., Zhu, Y.: Next point-of-interest recommendation with temporal and multi-level context attention. In: ICDM 2018, pp. 1110–1115 (2018)
Li, X., Cong, G., Li, X., Pham, T.N., Krishnaswamy, S.: Rank-GeoFM: a ranking based geographical factorization method for point of interest recommendation. In: SIGIR 2015, pp. 433–442 (2015)
Li, Y., Li, Y., Gunopulos, D., Guibas, L.J.: Knowledge-based trajectory completion from sparse GPS samples. In: SIGSPATIAL 2016, pp. 33:1–33:10 (2016)
Liao, D., Liu, W., Zhong, Y., Li, J., Wang, G.: Predicting activity and location with multi-task context aware recurrent neural network. In: IJCAI 2018, pp. 3435–3441 (2018)
Liu, Q., Wu, S., Wang, L., Tan, T.: Predicting the next location: a recurrent model with spatial and temporal contexts. In: AAAI 2016, pp. 194–200 (2016)
Liu, Y., Cong, M., Dong, H., Liu, D.: Reinforcement learning and EGA-based trajectory planning for dual robots. I. J. Robot. Autom. 33(4) (2018)
Long, J.A.: Kinematic interpolation of movement data. Int. J. Geogr. Inf. Sci. 30(5), 854–868 (2016)
Meng, C., Yi, X., Su, L., Gao, J., Zheng, Y.: City-wide traffic volume inference with loop detector data and taxi trajectories. In: SIGSPATIAL 2017, pp. 1:1–1:10 (2017)
Pek, C., Althoff, M.: Computationally efficient fail-safe trajectory planning for self-driving vehicles using convex optimization. In: ITSC 2018, pp. 1447–1454 (2018)
Rendle, S., Freudenthaler, C., Gantner, Z., Schmidt-Thieme, L.: BPR: Bayesian personalized ranking from implicit feedback. In: UAI 2009, pp. 452–461 (2009)
Serrano, M.E., Godoy, S.A., Montoya, L.Q., Scaglia, G.J.E.: Interpolation based controller for trajectory tracking in mobile robots. J. Intell. Rob. Syst. 86(3–4), 569–581 (2017)
Shen, T., Zhou, T., Long, G., Jiang, J., Wang, S., Zhang, C.: Reinforced self-attention network: a hybrid of hard and soft attention for sequence modeling. In: IJCAI 2018, Sweden, pp. 4345–4352 (2018)
Silva, F.A., Celes, C., Boukerche, A., Ruiz, L.B., Loureiro, A.A.F.: Filling the gaps of vehicular mobility traces. In: MSWiM 2015, pp. 47–54 (2015)
Su, H., Zheng, K., Huang, J., Wang, H., Zhou, X.: Calibrating trajectory data for spatio-temporal similarity analysis. VLDB J. 24(1), 93–116 (2015). https://doi.org/10.1007/s00778-014-0365-y
Vaswani, A., et al.: Attention is all you need. In: NIPS 2017, pp. 6000–6010 (2017)
Werbos, P.J.: Backpropagation through time: what it does and how to do it. Proc. IEEE 78(10), 1550–1560 (1990)
Yang, C., Bai, L., Zhang, C., Yuan, Q., Han, J.: Bridging collaborative filtering and semi-supervised learning: a neural approach for POI recommendation. In: SIGKDD 2017, pp. 1245–1254 (2017)
Yao, D., Zhang, C., Huang, J., Bi, J.: SERM: a recurrent model for next location prediction in semantic trajectories. In: CIKM 2017, pp. 2411–2414 (2017)
Yavas, G., Katsaros, D., Ulusoy, Ö., Manolopoulos, Y.: A data mining approach for location prediction in mobile environments. Data Knowl. Eng. 54(2), 121–146 (2005)
Ying, J.J., Lee, W., Weng, T., Tseng, V.S.: Semantic trajectory mining for location prediction. In: ACM-GIS 2011, pp. 34–43 (2011)
Zhang, C., Zhang, K., Yuan, Q., Zhang, L., Hanratty, T., Han, J.: GMove: group-level mobility modeling using geo-tagged social media. In: SIGKDD 2016, pp. 1305–1314 (2016)
Zhang, W., Wang, J.: Location and time aware social collaborative retrieval for new successive point-of-interest recommendation. In: CIKM 2015, pp. 1221–1230 (2015)
Zhao, P., et al.: Where to go next: a spatio-temporal gated network for next POI recommendation. In: AAAI 2019, pp. 5877–5884 (2019)
Zheng, Y., Wang, L., Zhang, R., Xie, X., Ma, W.: GeoLife: managing and understanding your past life over maps. In: MDM 2008, pp. 211–212 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Yao, D. et al. (2024). Trajectory Completion via Context-Guided Neural Filtering and Encoding. In: Onizuka, M., et al. Database Systems for Advanced Applications. DASFAA 2024. Lecture Notes in Computer Science, vol 14850. Springer, Singapore. https://doi.org/10.1007/978-981-97-5552-3_1
Download citation
DOI: https://doi.org/10.1007/978-981-97-5552-3_1
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-5551-6
Online ISBN: 978-981-97-5552-3
eBook Packages: Computer ScienceComputer Science (R0)