More Web Proxy on the site http://driver.im/

research-article

TraPlan: An Effective Three-in-One Trajectory-Prediction Model in Transportation Networks

Authors:

Louis Alberto GutierrezAuthors Info & Claims

IEEE Transactions on Intelligent Transportation Systems, Volume 16, Issue 3

Pages 1188 - 1198

https://doi.org/10.1109/TITS.2014.2353302

Published: 29 May 2015 Publication History

Abstract

The existing approaches for trajectory prediction (TP) are primarily concerned with discovering frequent trajectory patterns (FTPs) from historical movement data. Moreover, most of these approaches work by using a linear TP model to depict the positions of objects, which does not lend itself to the complexities of most real-world applications. In this research, we propose a three-in-one TP model in road-constrained transportation networks called TraPlan. TraPlan contains three essential techniques: 1) constrained network R-tree (CNR-tree), which is a two-tiered dynamic index structure of moving objects based on transportation networks; 2) a region-of-interest (RoI) discovery algorithm is employed to partition a large number of trajectory points into distinct clusters; and 3) a FTP-tree-based TP approach, called FTP-mining, is proposed to discover FTPs to infer future locations of objects moving within RoIs. In order to evaluate the results of the proposed CNR-tree index structure, we conducted experiments on synthetically generated data sets taken from real-world transportation networks. The results show that the CNR-tree can reduce the time cost of index maintenance by an average gap of about 40% when compared with the traditional NDTR-tree, as well as reduce the time cost of trajectory queries. Moreover, compared with fixed network R-Tree (FNR-trees), the accuracy of range queries has shown an on average improvement of about 32%. Furthermore, the experimental results show that the TraPlan demonstrates accurate and efficient prediction of possible motion curves of objects in distinct trajectory data sets by over 80% on average. Finally, we evaluate these results and the performance of the TraPlan model in regard to TP by comparing it with other TP algorithms.

References

[1]

C. Zaniolo, “ Event-oriented data models and temporal queries in transaction-time databases,” in Proc. 16th Int. Symp. Temporal Represent. Reasoning, Washington, D.C., USA, 2009, pp. 47– 53, IEEE Computer Society.

[2]

J. Zhang, et al., “ Data-driven intelligent transportation systems: A survey,” IEEE Trans. Intell. Transp. Syst., vol. 12, no. 4, pp. 1624– 1639, Dec. 2011.

Digital Library

[3]

Y. Zheng, and X. Zhou, Computing With Spatial Trajectories, Berlin, Germany: Springer-Verlag, 2011.

Digital Library

[4]

C. Song, Z. Qu, N. Blumm, and A.-L. Barabsi, “ Limits of predictability in human mobility,” Science, vol. 327, no. 5968, pp. 1018– 1021, Feb. 2010.

[5]

F. Y. Wang, “ Parallel control and management for intelligent transportation systems: Concepts, architectures, applications,” IEEE Trans. Intell. Transp. Syst., vol. 11, no. 3, pp. 630– 638, Sep. 2010.

Digital Library

[6]

J. Yang, and M. Hu, “ TrajPattern: Mining sequential patterns from imprecise trajectories of mobile objects,” in Proc. 10th Int. Conf. Adv. Database Technol., Berlin, Germany, 2006, pp. 664– 681, Springer.

[7]

M. Morzy, “ Mining frequent trajectories of moving objects for location prediction,” in Proc. 5th Int. Conf. Mach. Learn. Data Mining Pattern Recog., Berlin, Germany, 2007, pp. 667– 680, Springer.

Digital Library

[8]

S. Qiao, T. Li, J. Peng, and J. Qiu, “ Parallel sequential pattern mining of massive trajectory data,” Int. J. Comput. Intell. Syst., vol. 3, no. 3, pp. 343– 356, Sep. 2010.

[9]

J. C. Ying, W. C. Lee, T. C. Weng, and S. Tseng, “ Semantic trajectory mining for location prediction,” in Proc. 19th ACM SIGSPATIAL Int. Conf. Adv. Geographic Inf. Syst., New York, NY, USA, 2011, pp. 34– 43, ACM.

[10]

A. Sadilek, and J. Krumm, “ Far out: Predicting long-term human mobility,” in Proc. 26th AAAI Conf. Artif. Intell., Palo Alto, CA, USA, AAAI Press.

[11]

T. Hunter, P. Abbeel, and A. M. Bayen, “ The path inference filter: Model-based low-latency map matching of probe vehicle data,” IEEE Trans. Intell. Transp. Syst., vol. 15, no. 2, pp. 507– 529, Apr. 2014.

[12]

J. Zhou, K. H. Tung, W. Wu, and W. S. Ng, “ A “semi-lazy” approach to probabilistic path prediction in dynamic environments,” in Proc. 19th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, New York, NY, USA, 2013, pp. 748– 756, ACM.

Digital Library

[13]

T. L. Pan, A. Sumalee, R. X. Zhong, and N. Indra-payoong, “ Short-term traffic state prediction based on temporalspatial correlation,” IEEE Trans. Intell. Transp. Syst., vol. 14, no. 3, pp. 1– 23, Sep. 2013.

[14]

L. Wang, K. Hu, T. Ku, and X. Yan, “ Mining frequent trajectory pattern based on vague space partition,” Knowl.-Based Syst., vol. 50, pp. 100– 111, Sep. 2013.

Digital Library

[15]

S. Qiao, D. Shen, X. Wang, N. Han, and W. Zhu, “ A self-adaptive parameter selection trajectory prediction approach via hidden Markov models,” IEEE Trans. Intell. Transp. Syst., vol. 16, no. 1, pp. 284– 296, Feb. 2015.

Digital Library

[16]

Y. Tao, D. Papadias, and J. Sun, “ The TPR*-tree: An optimized spatio-temporal access method for predictive queries,” in Proc. 29th Int. Conf. Very Large Data Bases, 2003, pp. 790– 801, ser. VLDB'03. VLDB Endowment.

[17]

J. Chen, and X. Meng, “ Update-efficient indexing of moving objects in road networks,” Geoinformatica, vol. 13, no. 4, pp. 397– 424, Dec. 2009.

Digital Library

[18]

E. Frentzos, “ Indexing objects moving on fixed networks,” in Proc. 8th Int. Symp. Spatial Temporal Databases, Berlin, Germany, 2003, pp. 289– 305, Springer.

[19]

V. T. Almeida, and R. H. Güting, “ Indexing the trajectories of moving objects in networks,” Geoinformatica, vol. 9, no. 1, pp. 33– 60, Mar. 2005.

Digital Library

[20]

Z. Ding, X. Li, and B. Yu, “ Indexing the historical, current, future locations of network-constrained moving objects,” (in Chinese), J. Softw., vol. 20, no. 12, pp. 3193– 3204, 2009.

[21]

J. Yuan, Y. Zheng, and X. Xie, “ Discovering regions of different functions in a city using human mobility and POIs,” in Proc. 18th ACM SIGKDD Int. Conf. Knowledge Discovery Data Mining, New York, NY, USA, 2012, pp. 186– 194, ser. KDD'12, ACM.

Digital Library

[22]

J. Sander, M. Ester, H. P. Kriegel, and X. Xu, “ Density-based clustering in spatial databases: The algorithm DBSCAN and its applications,” Data Mining Knowl. Discovery, vol. 2, no. 2, pp. 169– 194, 1998.

Digital Library

[23]

J. Han, J. Pei, Y. Yin, and R. Mao, “ Mining frequent patterns without candidate generation: A frequent-pattern tree approach,” Data Mining Knowl. Discovery, vol. 8, no. 1, pp. 53– 87, Jan. 2004.

Digital Library

[24]

T. Brinkhoff, “ A framework for generating network-based moving objects,” Geoinformatica, vol. 6, no. 2, pp. 153– 180, Jun. 2002.

Digital Library

[25]

S. Qiao, et al., “ PutMode: Prediction of uncertain trajectories in moving objects databases,” Appl. Intell., vol. 33, no. 3, pp. 370– 386, 2010.

Digital Library

Cited By

Li ZShao X(2024)Future locations prediction with multi-graph attention networks based on spatial–temporal LSTM frameworkThe Journal of Supercomputing10.1007/s11227-024-06249-980:14(20020-20041)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1007/s11227-024-06249-9
Chen SHuang YLu W(2022)Anomaly Detection and Restoration for AIS Raw DataWireless Communications & Mobile Computing10.1155/2022/59544832022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/5954483
Han NQiao SYue KHuang JHe QTang THuang FHe CYuan C(2022)Algorithms for Trajectory Points Clustering in Location-based Social NetworksACM Transactions on Intelligent Systems and Technology10.1145/348097213:3(1-29)Online publication date: 3-Mar-2022
https://dl.acm.org/doi/10.1145/3480972
Show More Cited By

Index Terms

TraPlan: An Effective Three-in-One Trajectory-Prediction Model in Transportation Networks
1. Human-centered computing
  1. Visualization
    1. Visualization application domains
      1. Geographic visualization
2. Information systems
  1. Information systems applications
    1. Data mining
    2. Spatial-temporal systems

Index terms have been assigned to the content through auto-classification.

Recommendations

One Way Distance: For Shape Based Similarity Search of Moving Object Trajectories

An interesting issue in moving object databases is to find similar trajectories of moving objects. Previous work on this topic focuses on movement patterns (trajectories with time dimension) of moving objects, rather than spatial shapes (trajectories ...
Indexing frequently updated trajectories of network-constrained moving objects
DEXA'11: Proceedings of the 22nd international conference on Database and expert systems applications - Volume Part II

Index is a key technique in improving the query processing performance of moving objects databases. However, current index methods for moving object trajectories take trajectory units as the basic index records and frequent index updates are needed when ...
Moving Objects Databases Based on Dynamic Transportation Networks: Modeling, Indexing, and Implementation
IWHDM: Revised Selected Papers of the APWeb 2008 International Workshops on Advanced Web and Network Technologies, and Applications - Volume 4977

In this paper, a new moving objects database model, Route-based model for Moving Objects on Dynamic Transportation Networks RMODTN, is proposed which is suited for dealing with the interrelationship between moving objects and the underlying ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Intelligent Transportation Systems

IEEE Transactions on Intelligent Transportation Systems Volume 16, Issue 3

June 2015

548 pages

Issue’s Table of Contents

Copyright © 2014.

Publisher

IEEE Press

Publication History

Published: 29 May 2015

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li ZShao X(2024)Future locations prediction with multi-graph attention networks based on spatial–temporal LSTM frameworkThe Journal of Supercomputing10.1007/s11227-024-06249-980:14(20020-20041)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1007/s11227-024-06249-9
Chen SHuang YLu W(2022)Anomaly Detection and Restoration for AIS Raw DataWireless Communications & Mobile Computing10.1155/2022/59544832022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/5954483
Han NQiao SYue KHuang JHe QTang THuang FHe CYuan C(2022)Algorithms for Trajectory Points Clustering in Location-based Social NetworksACM Transactions on Intelligent Systems and Technology10.1145/348097213:3(1-29)Online publication date: 3-Mar-2022
https://dl.acm.org/doi/10.1145/3480972
Qiao SHan NHuang JYue KMao RShu HHe QWu X(2021)A Dynamic Convolutional Neural Network Based Shared-Bike Demand Forecasting ModelACM Transactions on Intelligent Systems and Technology10.1145/344798812:6(1-24)Online publication date: 29-Nov-2021
https://dl.acm.org/doi/10.1145/3447988
Chen MYu XLiu Y(2019)TraLFM: Latent Factor Modeling of Traffic Trajectory DataIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2019.291207520:12(4624-4634)Online publication date: 20-Dec-2019
https://dl.acm.org/doi/10.1109/TITS.2019.2912075
Meng FYuan GLv SWang ZXia S(2019)An overview on trajectory outlier detectionArtificial Intelligence Review10.1007/s10462-018-9619-152:4(2437-2456)Online publication date: 1-Dec-2019
https://dl.acm.org/doi/10.1007/s10462-018-9619-1
Chen GLi Z(2019)Improved particle swarm optimization LSSVM spatial location trajectory data prediction model in health care monitoring systemPersonal and Ubiquitous Computing10.1007/s00779-019-01291-426:3(795-805)Online publication date: 13-Aug-2019
https://dl.acm.org/doi/10.1007/s00779-019-01291-4
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
Yi YQiao SZhou WZheng CLiu QWang J(2018)Adaptive multiple graph regularized semi-supervised extreme learning machineSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-018-3109-x22:11(3545-3562)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s00500-018-3109-x
Cui JZhou XZhu YShen Y(2018)A Road-Aware Neural Network for Multi-step Vehicle Trajectory PredictionDatabase Systems for Advanced Applications10.1007/978-3-319-91452-7_45(701-716)Online publication date: 21-May-2018
https://dl.acm.org/doi/10.1007/978-3-319-91452-7_45

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents