PathletRL: Trajectory Pathlet Dictionary Construction using Reinforcement Learning
Article No.: 72, Pages 1 - 12
Abstract
Sophisticated location and tracking technologies have led to the generation of vast amounts of trajectory data. Of interest is constructing a small set of basic building blocks that can represent a wide range of trajectories, known as a trajectory pathlet dictionary. This dictionary can be useful in various tasks and applications, such as trajectory compression, travel time estimation, route planning, and navigation services. Existing methods for constructing a pathlet dictionary use a top-down approach, which generates a large set of candidate pathlets and selects the most popular ones to form the dictionary. However, this approach is memory-intensive and leads to redundant storage due to the assumption that pathlets can overlap. To address these limitations, we propose a bottom-up approach for constructing a pathlet dictionary that significantly reduces memory storage needs of baseline methods by multiple orders of magnitude (by up to ~24K× better). The key idea is to initialize unit-length pathlets and iteratively merge them, while maximizing utility. The utility is defined using newly introduced metrics of trajectory loss and representability. A deep reinforcement learning method is proposed, PathletRL, that uses Deep Q Networks (Dqn) to approximate the utility function. Experiments show that our method outperforms the current state-of-the-art, both on synthetic and real-world data. Our method can reduce the size of the constructed dictionary by up to 65.8% compared to other methods. It is also shown that only half of the pathlets in the dictionary is needed to reconstruct 85% of the original trajectory data.
References
[1]
P. K. Agarwal, K. Fox, K. Munagala, A. Nath, J. Pan, and E. Taylor. 2018. Subtrajectory Clustering: Models and Algorithms. In Proc. of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Sys. (PODS '18). 75--87.
[2]
F. Aleskerov, D. Bouyssou, and B. Monjardet. 2007. Utility Maximization, Choice and Preference. Springer Berlin Heidelberg, Berlin, Heidelberg.
[3]
G. Alix, N. Yanin, T. Pechlivanoglou, J. Li, F. Heidari, and M. Papagelis. 2022. A Mobility-based Recommendation System for Mitigating the Risk of Infection during Epidemics. In 2022 23rd IEEE Intl. Conf. on Mobile Data Mgt. (MDM). 292--5.
[4]
M. Alsaeed, A. Agrawal, and M. Papagelis. 2023. Trajectory-User Linking using Higher-order Mobility Flow Representations. In 2023 24th IEEE International Conference on Mobile Data Management (MDM). 158--167.
[5]
F. Arasteh, S. SheikhGarGar, and M. Papagelis. 2022. Network-Aware Multi-Agent Reinforcement Learning for the Vehicle Navigation Problem. In Proc. of the 30th Intl. Conf. on Adv. in Geographic Info. Sys. (ACM SIGSPATIAL '22). Article 69.
[6]
G. Atluri, A. Karpatne, and V. Kumar. Spatio-Temporal Data Mining: A Survey of Problems and Methods. ACM Comp. Surveys 51, 4, Article 83 (Aug 2018).
[7]
L. Bracciale, M. Bonola, P. Loreti, G. Bianchi, R. Amici, and A. Rabuffi. 2014. CRAWDAD Roma/taxi dataset. https://crawdad.org/roma/taxi/20140717.
[8]
C. Chen, H. Su, Q. Huang, L. Zhang, and L. Guibas. 2013. Pathlet Learning for Compressing and Planning Trajectories. In Proc. of the 21st ACM SIGSPATIAL Intl. Conf. on Adv. in Geographic Info. Sys. (ACM SIGSPATIAL'13). 392--5.
[9]
Y. Chen, H. Zhang, W. Sun, and B. Zheng. 2022. RNTrajRec: Road Network Enhanced Trajectory Recovery with Spatial-Temporal Transformer.
[10]
A. Datta. Seizing The Future: Geospatial Industry Technology Trends and Directions. GWPrime (Feb 2022).
[11]
Z. Fang, Y. Du, X. Zhu, D. Hu, L. Chen, Y. Gao, and C. S. Jensen. 2022. SpatioTemporal Trajectory Similarity Learning in Road Networks. In Proc. of the 28th ACM SIGKDD Conf. on Knowledge Discovery & Data Mining (ACM SIGKDD '22). 347--56.
[12]
A. Faraji, J. Li, G. Alix, M. Alsaeed, N. Yanin, A. Nadiri, and M. Papagelis. 2023. Point2Hex: Higher-order Mobility Flow Data and Resources. In Proc. of the 31st Intl. Conf. on Adv. in Geographic Info. Sys. (SIGSPATIAL '23).
[13]
W. Fedus, P. Ramachandran, R. Agarwal, Y. Bengio, H. Larochelle, M. Rowland, and W. Dabney. 2020. Revisiting Fundamentals of Experience Replay. In Proc. of the 37th Intl. Conf. on Machine Learning (ICML'20). JMLR, Article 287.
[14]
Y. Geng, E. Liu, R. Wang, and Y. Liu. Deep Reinforcement Learning Based Dynamic Route Planning for Minimizing Travel Time. CoRR (2020).
[15]
A. Hamdi, K. Shaban, A. Erradi, A. Mohamed, S. K. Rumi, and F. D. Salim. Spatiotemporal data mining: a survey on challenges and open problems. Artificial Intelligence Review 55, 2 (Feb 2022), 1441--1488.
[16]
N. Han, S. Qiao, K. Yue, J. Huang, Q. He, T. Tang, F. Huang, C. He, and C.-A. Yuan. Algorithms for Trajectory Points Clustering in Location-Based Social Networks. ACM Trans. Intell. Syst. Technol. 13, 3, Article 43 (mar 2022).
[17]
Q. Han, Y. Lei, L. Zeng, G. He, L. Ye, and L. Qi. 2021. Research on Travel Time Prediction of Multiple Bus Trips Based on MDARNN. In 2021 IEEE Intl. Intelligent Transportation Sys. Conf. (ITSC). 3718--3725.
[18]
Z. He, L. Tao, Z. Xie, and C. Xu. Discovering spatial interaction patterns of near repeat crime by spatial association rules mining. Sci. Reports 10, 1 (Oct 2020).
[19]
J. Kober and J. Peters. 2014. Reinforcement Learning in Robotics: A Survey. Springer Intl. Publishing, Cham, 9--67.
[20]
J.-G. Lee, J. Han, and K.-Y. Whang. 2007. Trajectory Clustering: A Partition-and-Group Framework. In Proc. of the 2007 ACM SIGMOD Intl. Conf. on Mgt. of Data (ACM SIGMOD '07). 593--604.
[21]
L. Li, R. Jiang, Z. He, X. M. Chen, and X. Zhou. Trajectory data-based traffic flow studies: A revisit. Transportation Research Part C: Emerging Technologies 114 (2020), 225--240.
[22]
M. Li, P. Tong, M. Li, Z. Jin, J. Huang, and X.-S. Hua. Traffic Flow Prediction with Vehicle Trajectories. Proceedings of the AAAI Conference on Artificial Intelligence 35, 1 (May 2021), 294--302.
[23]
T. Li, J. Gao, and X. Peng. 2021. Deep Learning for Spatiotemporal Modeling of Urbanization. In Proc. of the 35th Conf. on Neural Info. Proc. Sys. (NeurIPS 2021).
[24]
Y. Li, D. Gunopulos, C. Lu, and L. J. Guibas. Personalized Travel Time Prediction Using a Small Number of Probe Vehicles. ACM Trans. Spatial Algorithms Syst. 5, 1, Article 4 (may 2019).
[25]
Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, and Y. Huang. 2009. Map-Matching for Low-Sampling-Rate GPS Trajectories. In Proc. of the 17th ACM SIGSPATIAL Intl. Conf. on Adv. in Geographic Info. Sys. (Seattle, Washington) (GIS '09). Assoc. for Comp. Machinery, New York, NY, USA, 352--361.
[26]
K. McCormick. An Essay on the Origin of the Rational Utility Maximization Hypothesis and a Suggested Modification. Eastern Eco. Journal 23 ('97), 17--30.
[27]
S. Mehmood and M. Papagelis. 2020. Learning Semantic Relationships of Geographical Areas based on Trajectories. In 2020 21st IEEE Intl. Conf. on Mobile Data Mgt. (MDM). 109--118.
[28]
V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. 2013. Playing Atari With Deep Reinforcement Learning. In NIPS Deep Learning Workshop.
[29]
J. Muckell, J.-H. Hwang, C. T. Lawson, and S. S. Ravi. 2010. Algorithms for Compressing GPS Trajectory Data: An Empirical Evaluation. In Proc. of the 18th SIGSPATIAL Intl. Conf. on Adv. in Geographic Info. Sys. (ACM GIS '10). 402--405.
[30]
A. Nematichari, T. Pechlivanoglou, and M. Papagelis. 2022. Evaluating and Forecasting the Operational Performance of Road Intersections. In Proc. of the 30th Intl. Conf. on Adv. in Geographic Info. Sys. (ACM SIGSPATIAL '22). Article 31.
[31]
M. E. J. Newman. 2018. Networks (second edition ed.). Oxford University Press, Oxford, United Kingdom; New York, NY, United States of America.
[32]
P. Newson and J. Krumm. 2009. Hidden Markov Map Matching through Noise and Sparseness. In Proc. of the 17th ACM SIGSPATIAL Intl. Conf. on Adv. in Geographic Info. Sys. (GIS '09). 336--343.
[33]
M. Nyhan, S. Grauwin, R. Britter, B. Misstear, A. McNabola, F. Laden, S. R. H. Barrett, and C. Ratti. "Exposure Track"---The Impact of Mobile-Device-Based Mobility Patterns on Quantifying Population Exposure to Air Pollution. Environmental Science & Technology 50, 17 (2016), 9671--9681.
[34]
P. J. Olver and C. Shakiban. 2018. Applied Linear Algebra (2nd ed. 2018 ed.). Springer International Publishing: Imprint: Springer, Cham.
[35]
C. Panagiotakis, N. Pelekis, I. Kopanakis, E. Ramasso, and Y. Theodoridis. Segmentation and Sampling of Moving Object Trajectories Based on Representativeness. IEEE Trans. on Knowledge and Data Eng. 24, 7 (2012), 1328--1343.
[36]
M. K. Pandey, P. Srivastava, and G. Petropoulos. 2021. Chapter 21 - Future pathway for research and emerging applications in GPS/GNSS. In GPS and GNSS Technology in Geosciences. Elsevier, 429--438.
[37]
T. Pechlivanoglou, G. Alix, N. Yanin, J. Li, F. Heidari, and M. Papagelis. 2022. Microscopic Modeling of Spatiotemporal Epidemic Dynamics. In Proc. of the 3rd ACM SIGSPATIAL Intl. Workshop on Spatial Comp. for Epidemiology (SpatialEpi '22). 11--21.
[38]
T. Pechlivanoglou, J. Li, J. Sun, F. Heidari, and M. Papagelis. Epidemic Spreading in Trajectory Networks. Big Data Research 27 (2022).
[39]
T. Pechlivanoglou and M. Papagelis. 2018. Fast and Accurate Mining of Node Importance in Trajectory Networks. In 2018 IEEE Intl. Conf. on Big Data (Big Data). 781--790.
[40]
T. Ruth. Why Location Services and IoT are Leading the 5G Trends of 2022. Quuppa (Sep 2022).
[41]
S. Sankararaman, P. K. Agarwal, T. Mølhave, J. Pan, and A. P. Boedihardjo. 2013. Model-Driven Matching and Segmentation of Trajectories. In Proc. of the 21st ACM SIGSPATIAL Intl. Conf. on Adv. in Geographic Info. Sys. (Orlando, Florida) (SIGSPATIAL'13). Assoc. for Comp. Machinery, New York, NY, USA, 234--43.
[42]
A. Sawas, A. Abuolaim, M. Afifi, and M. Papagelis. 2018. Tensor Methods for Group Pattern Discovery of Pedestrian Trajectories. In 19th IEEE Intl. Conf. on Mobile Data Mgt. (MDM). 76--85.
[43]
A. Sawas, A. Abuolaim, M. Afifi, and M. Papagelis. A versatile computational framework for group pattern mining of pedestrian trajectories. GeoInformatica 23, 4 (Oct 2019), 501--531.
[44]
D. Silver, T. Hubert, J. Schrittwieser, I. Antonoglou, M. Lai, A. Guez, M. Lanctot, L. Sifre, D. Kumaran, T. Graepel, T. Lillicrap, K. Simonyan, and D. Hassabis. A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play. Science 362, 6419 (2018), 1140--1144.
[45]
A. Strzelecki. The Apple Mobility Trends Data in Human Mobility Patterns during Restrictions and Prediction of COVID-19: A Systematic Review and Meta-Analysis. Healthcare 10, 12 (2022).
[46]
S.-H. Sun, T.-L. Wu, and J. J. Lim. 2020. Program Guided Agent. In Intl. Conf. on Learning Representations.
[47]
R. S. Sutton and A. G. Barto. 2018. Reinforcement Learning: An Introduction. A Bradford Book, Cambridge, MA, USA.
[48]
M. van Kreveld and L. Wiratma. 2011. Median Trajectories Using Well-Visited Regions and Shortest Paths. In Proc. of the 19th ACM SIGSPATIAL Intl. Conf. on Adv. in Geographic Info. Sys. (GIS '11). 241--250.
[49]
M. van Otterlo and M. Wiering. 2012. Reinforcement Learning and Markov Decision Processes. Springer Berlin Heidelberg, Berlin, Heidelberg, 3--42.
[50]
J. Wang, N. Wu, and W. Zhao. Personalized Route Recommendation With Neural Network Enhanced Search Algorithm. IEEE Transactions on Knowledge & Data Engineering 34, 12 (Dec 2022), 5910--5924.
[51]
S. Wang, Z. Bao, J. S. Culpepper, T. Sellis, and X. Qin. Fast Large-Scale Trajectory Clustering. Proc. VLDB Endow. 13, 1 (Sep 2019), 29--42.
[52]
S. Wang, J. Cao, and P. Yu. Deep Learning for Spatio-Temporal Data Mining: A Survey. IEEE Trans. on Knowledge & Data Eng. 34, 08 (Aug 2022), 3681--700.
[53]
T. Wang, S. Huang, Z. Bao, J. S. Culpepper, and R. Arablouei. 2022. Representative Routes Discovery from Massive Trajectories. In Proc. of the 28th ACM SIGKDD Conf. on Knowledge Discovery and Data Mining (Washington DC, USA) (KDD '22). Assoc. for Comp. Machinery, New York, NY, USA, 4059--69.
[54]
Z. Wang, C. Long, and G. Cong. 2021. Trajectory Simplification with Reinforcement Learning. In 2021 IEEE 37th Intl. Conf. on Data Eng. (ICDE). 684--695.
[55]
Z. Wang, Y. Zhu, Q. Zhang, H. Liu, C. Wang, and T. Liu. Graph-Enhanced Spatial-Temporal Network for Next POI Recommendation. ACM Trans. Knowl. Discov. Data 16, 6, Article 104 (Jul 2022).
[56]
J. Xu, J. Zhao, R. Zhou, C. Liu, P. Zhao, and L. Zhao. Predicting Destinations by a Deep Learning based Approach. IEEE Trans. on Knowledge and Data Eng. 33, 2 (2021), 651--666.
[57]
H. Xue, B. P. Voutharoja, and F. D. Salim. 2022. Leveraging Language Foundation Models for Human Mobility Forecasting. In Proc. of the 30th Intl. Conf. on Adv. in Geographic Info. Sys. (ACM SIGSPATIAL '22). Article 90.
[58]
R. K. Yadav, G. Kishor, Himanshu, and K. Kashyap. 2020. Comparative Analysis of Route Planning Algorithms on Road Networks. In 2020 5th Intl. Conf. on Comm. and Electronics Sys. (ICCES). 401--406.
[59]
M. Yassin and E. Rachid. 2015. A survey of positioning techniques and location based services in wireless networks. In 2015 IEEE Intl. Conf. on Signal Processing, Informatics, Communication and Energy Systems (SPICES). 1--5.
[60]
J. Yuan, Y. Zheng, C. Zhang, X. Xie, and G.-Z. Sun. 2010. An Interactive-Voting Based Map Matching Algorithm. In 2010 11th Intl. Conf. on Mobile Data Mgt. 43--52.
[61]
J. Zhao, J. Xu, R. Zhou, P. Zhao, C. Liu, and F. Zhu. 2018. On Prediction of User Destination by Sub-Trajectory Understanding: A Deep Learning Based Approach. In Proc. of the 27th ACM Intl. Conf. on Info. and Knowledge Mgt. (ACM CIKM 2018). 1413--1422.
[62]
Y. Zhao, S. Shang, Y. Wang, B. Zheng, Q. V. H. Nguyen, and K. Zheng. 2018. REST: A Reference-Based Framework for Spatio-Temporal Trajectory Compression. In Proc. of the 24th ACM SIGKDD Intl. Conf. on Knowledge Discovery Data Mining (ACM SIGKDD '18). 2797--2806.
[63]
Y. Zheng. Trajectory Data Mining: An Overview. ACM Trans. Intell. Syst. Technol. 6, 3, Article 29 (May 2015).
[64]
Y. Zhou and T. S. Huang. 2008. 'Bag of segments' for motion trajectory analysis. In 2008 15th IEEE Intl. Conf. on Image Processing. 757--760.
Index Terms
- PathletRL: Trajectory Pathlet Dictionary Construction using Reinforcement Learning
Recommendations
Trajectory Data Mining: An Overview
Survey Paper, Regular Papers and Special Section on Participatory Sensing and Crowd IntelligenceThe advances in location-acquisition and mobile computing techniques have generated massive spatial trajectory data, which represent the mobility of a diversity of moving objects, such as people, vehicles, and animals. Many techniques have been proposed ...
A general methodology for n-dimensional trajectory clustering
Highlights- Propose a robust n-dimensional trajectory clustering framework.
- The framework ...
AbstractTrajectory data is rich in dimensionality, often containing valuable patterns in more than just the spatial and temporal dimensions. Yet existing trajectory clustering techniques only consider a fixed number of dimensions. We propose a ...
A framework for anomaly detection in maritime trajectory behavior
Rapid growth in location data acquisition techniques has led to a proliferation of trajectory data related to moving objects. This large body of data has expanded the scope for trajectory research and made it applicable to a more diverse range of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2023
686 pages
ISBN:9798400701689
DOI:10.1145/3589132
- General Chairs:
- Maria Luisa Damiani,
- Matthias Renz,
- Program Chairs:
- Ahmed Eldawy,
- Peer Kröger,
- Mario A Nascimento
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part 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 components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 December 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Natural Sciences and Engineering Research Council of Canada (NSERC)
Conference
SIGSPATIAL '23
Sponsor:
SIGSPATIAL '23: 31st ACM International Conference on Advances in Geographic Information Systems
November 13 - 16, 2023
Hamburg, Germany
Acceptance Rates
Overall Acceptance Rate 257 of 1,238 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 103Total Downloads
- Downloads (Last 12 months)92
- Downloads (Last 6 weeks)2
Reflects downloads up to 31 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in