RealTE: Real-time Trajectory Estimation Over Large-Scale Road Networks

Authors

  • Qibin Zhou School of International Education, Shanghai Jian Qiao University, Shanghai, China
  • Qingang Su School of Kaiserslautern Intelligent Manufacturing, Shanghai Dian Ji University, Shanghai, China
  • Dingyu Yang Alibaba Group, Shanghai, China; School of Electronics and Information, Shanghai Dian Ji University, Shanghai, China

DOI:

https://doi.org/10.13052/jwe1540-9589.21210

Keywords:

Trajectory prediction; Road network partition; Histogram estimation

Abstract

Real-time traffic estimation focuses on predicting the travel time of one travel path, which is capable of helping drivers selecting an appropriate or favor path. Statistical analysis or neural network approaches have been explored to predict the travel time on a massive volume of traffic data. These methods need to be updated when the traffic varies frequently, which incurs tremendous overhead. We build a system RealTER⁢e⁢a⁢l⁢T⁢E, implemented on a popular and open source streaming system StormS⁢t⁢o⁢r⁢m to quickly deal with high speed trajectory data. In RealTER⁢e⁢a⁢l⁢T⁢E, we propose a locality-sensitive partition and deployment algorithm for a large road network. A histogram estimation approach is adopted to predict the traffic. This approach is general and able to be incremental updated in parallel. Extensive experiments are conducted on six real road networks and the results illustrate RealTE achieves higher throughput and lower prediction error than existing methods. The runtime of a traffic estimation is less than 11 seconds over a large road network and it takes only 619619 microseconds for model updates.

Downloads

Download data is not yet available.

Author Biographies

Qibin Zhou, School of International Education, Shanghai Jian Qiao University, Shanghai, China

Qibin Zhou, received her M.Sc. degree from Huazhong University of Science and Technology in 2013. She is the deputy director of the Information Office and the vice president of the college of International Education in Shanghai Jianqiao University now. Her present research interests include network security, data analysis, smart campus construction, etc.

Qingang Su, School of Kaiserslautern Intelligent Manufacturing, Shanghai Dian Ji University, Shanghai, China

Qinggang Su, received the B.Sc. degree in Computer Science from Anhui University of Technology in 2002, and got the M.Sc. degree in Communication Engineering in Shanghai Jiao Tong University, and is studying for Ph.D. degree at East China Normal University. He became a faculty member in the school of electronic information, Shanghai Dianji University China from 2002, and he is the vice dean of Chinesisch-Deutsche Kolleg für Intelligente Produktion of Shanghai Dianji University now. He is a member of China Computer Federation (CCF), and his research is currently focused on wireless networks, 5G application and smart manufacturing.

Dingyu Yang, Alibaba Group, Shanghai, China; School of Electronics and Information, Shanghai Dian Ji University, Shanghai, China

Dingyu Yang received the B.E. and M.E. degrees from the Kunming University of Science and Technology, and the Ph.D. degree from the Shanghai Jiao Tong University. He is currently a data scientist at Alibaba Group. His research interests include resource prediction, anomaly detection in cloud computing and distributed stream processing.

References

Guerrero-Ibáñez, Antonio and Flores-Cortés, Carlos and Damián-Reyes, Pedro and Andrade-Aréchiga, M and Pulido, JRG (2012). Emerging technologies for urban traffic management. Urban Development, 59.

Ma, J., Chan, J., Ristanoski, G., Rajasegarar, S., and Leckie, C. (2019). Bus travel time prediction with real-time traffic information. Transportation Research Part C: Emerging Technologies, 105, 536–549.

Lee, S., and Fambro, D. B. (1999). Application of subset autoregressive integrated moving average model for short-term freeway traffic volume forecasting. Transportation Research Record, 1678(1), 179–188.

Zhang, D., Yang, D., Wang, Y., Tan, K. L., Cao, J., and Shen, H. T. (2017). Distributed shortest path query processing on dynamic road networks. The VLDB Journal, 26(3), 399–419.

Chan, K. Y., Dillon, T. S., Singh, J., and Chang, E. (2011). Neural-network-based models for short-term traffic flow forecasting using a hybrid exponential smoothing and Levenberg–Marquardt algorithm. IEEE Transactions on Intelligent Transportation Systems, 13(2), 644–654.

Hunter, T., Hofleitner, A., Reilly, J., Krichene, W., Thai, J., Kouvelas, A., and Bayen, A. (2013). Arriving on time: estimating travel time distributions on large-scale road networks. arXiv preprint arXiv:1302.6617.

Yuan, H., Li, G., Bao, Z., and Feng, L. (2020). Effective travel time estimation: When historical trajectories over road networks matter. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (pp. 2135–2149).

Box, G. E., Jenkins, G. M., Reinsel, G. C., and Ljung, G. M. (2015). Time series analysis: forecasting and control. John Wiley and Sons.

Karypis, G., and Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on scientific Computing, 20(1), 359–392.

Twitter Storm. https://github.com/nathanmarz/storm

Babcock, B., Babu, S., Datar, M., Motwani, R., and Widom, J. (2002). Models and issues in data stream systems. In Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (pp. 1–16).

Hua, Y. A. N. G., and Xing, W. E. I. (2020). An Application of CHNN for FANETs routing optimization. Journal of Web Engineering, 830–844.

Yang, D., Wang, F., and Ji, C. (2016). Hite: Histogram-based traffic estimation on real-time trajectory. In IEEE ICSAI (pp. 444–449). IEEE.

Buccafurri, F., Lax, G., Sacca, D., Pontieri, L., and Rosaci, D. (2008). Enhancing histograms by tree-like bucket indices. The VLDB journal, 17(5), 1041–1061.

Fu, K., Meng, F., Ye, J., and Wang, Z. (2020). Compacteta: A fast inference system for travel time prediction. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (pp. 3337–3345).

Yang, D., Zhang, D., Tan, K.L., Cao, J. and Le Mouël, F., 2014. CANDS: continuous optimal navigation via distributed stream processing. Proceedings of the VLDB Endowment (PVLDB), 8(2), pp.137–148.

Zhang, D., Yang, D., Wang, Y., Tan, K.L., Cao, J. and Shen, H.T., 2017. Distributed shortest path query processing on dynamic road networks. The VLDB Journal, 26(3), pp. 399–419.

Poosala, V., Haas, P. J., Ioannidis, Y. E., and Shekita, E. J. (1996). Improved histograms for selectivity estimation of range predicates. ACM Sigmod Record, 25(2), 294–305.

Jagadish, H. V., Koudas, N., Muthukrishnan, S., Poosala, V., Sevcik, K. C., and Suel, T. (1998). Optimal histograms with quality guarantees. In VLDB (Vol. 98, pp. 24–27).

Matias, Y., Vitter, J. S., and Wang, M. (1998). Wavelet-based histograms for selectivity estimation. In Proceedings of the 1998 ACM SIGMOD international conference on Management of data (pp. 448–459).

Yang, D., Guo, J., Wang, Z. J., Wang, Y., Zhang, J., Hu, L., … and Cao, J. (2018). Fastpm: An approach to pattern matching via distributed stream processing. Information Sciences, 453, 263–280.

Neumeyer, L., Robbins, B., Nair, A., and Kesari, A. (2010, December). S4: Distributed stream computing platform. In 2010 IEEE International Conference on Data Mining Workshops (pp. 170–177). IEEE.

Yang, D., Cao, J., Fu, J., Wang, J. and Guo, J., 2013. A pattern fusion model for multi-step-ahead CPU load prediction. Journal of Systems and Software, 86(5), pp. 1257–1266.

Zhang, D., Ding, M., Yang, D., Liu, Y., Fan, J. and Shen, H.T., 2018. Trajectory simplification: an experimental study and quality analysis. Proceedings of the VLDB Endowment, 11(9), pp. 934–946.

Spark. http://spark.incubator.apache.org

Flink. http://flink.apache.org

Hilger, M., Köhler, E., Möhring, R. H., and Schilling, H. (2009). Fast point-to-point shortest path computations with arc-flags. The Shortest Path Problem: Ninth DIMACS Implementation Challenge, 74, 41–72.

Zheng, Y., Liu, Y., Yuan, J., and Xie, X. (2011). Urban computing with taxicabs. In Proceedings of the 13th international conference on Ubiquitous computing (pp. 89–98).

Wei, H., Wang, Y., Forman, G., Zhu, Y., and Guan, H. (2012). Fast Viterbi map matching with tunable weight functions. In Proceedings of the 20th international conference on advances in geographic information systems (pp. 613–616).

US Road Network. http://www.dis.uniroma1.it/challenge9/download. shtml

Nakata, T., and Takeuchi, J. I. (2004). Mining traffic data from probe-car system for travel time prediction. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 817–822).

Lei, J., Chu, X., and He, W. (2021). Trajectory Data Restoring: A Way of Visual Analysis of Vessel Identity Base on OPTICS. Journal of Web Engineering., 20(2), 413–430.

Merah, A. F., Samarah, S., and Boukerche, A. (2012). Vehicular movement patterns: a prediction-based route discovery technique for VANETs. In 2012 IEEE International conference on communications (ICC) (pp. 5291-5295).

Zhang, B., Xing, K., Cheng, X., Huang, L., and Bie, R. (2012). Traffic clustering and online traffic prediction in vehicle networks: A social influence perspective. In 2012 Proceedings IEEE Infocom (pp. 495–503).

Pan, B., Demiryurek, U., and Shahabi, C. (2012). Utilizing real-world transportation data for accurate traffic prediction. In 2012 IEEE 12th International Conference on Data Mining (pp. 595–604).

Abraham, S., and Lal, P. S. (2012). Spatio-temporal similarity of network-constrained moving object trajectories using sequence alignment of travel locations. Transportation research part C: emerging technologies, 23, 109–123.

Chen, L., Lv, M., and Chen, G. (2010). A system for destination and future route prediction based on trajectory mining. Pervasive and Mobile Computing, 6(6), 657–676.

Yuan, J., Zheng, Y., Xie, X., and Sun, G. (2011). Driving with knowledge from the physical world. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 316–324).

Chen, F., Chen, D., Wang, L., and Botao, Y. (2021). Optimal Design of Electrical Capacitance Tomography Sensor and Improved ART Image Reconstruction Algorithm Based On the Internet of Things. Journal of Web Engineering, 1027–1052.

Nakata, T., and Takeuchi, J. I. (2004). Mining traffic data from probe-car system for travel time prediction. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 817–822).

Lee, W. H., Tseng, S. S., and Tsai, S. H. (2009). A knowledge based real-time travel time prediction system for urban network. Expert systems with Applications, 36(3), 4239–4247.

Xu, H., and Ying, J. (2017). Bus arrival time prediction with real-time and historic data. Cluster Computing, 20(4), 3099–3106.

Downloads

Published

2022-01-12

How to Cite

Zhou, Q. ., Su, Q. ., & Yang, D. . (2022). RealTE: Real-time Trajectory Estimation Over Large-Scale Road Networks. Journal of Web Engineering, 21(02), 365–390. https://doi.org/10.13052/jwe1540-9589.21210

Issue

2022: Vol 21 Iss 2

Section

Articles