Cited By
View all- Abdalla MHendawi AMokhtar HElgamal NKrumm JAli M(2020)$DeepMotions$ : A Deep Learning System for Path Prediction Using Similar MotionsIEEE Access10.1109/ACCESS.2020.29669828(23881-23894)Online publication date: 2020
SimilarMove: Similarity-based Prediction for Moving Object Future Path
Authors: 
Mohammed Abdalla, Abdeltawab Hendawi, Neveen ElGamal, Hoda M. O. Mokhtar, Mohamed Ali, John KrummAuthors Info & Claims
Pages 15 - 24
Abstract
Trajectory prediction has a significant impact on many location-based services such as local search, traffic management, and routing services. Existing trajectory prediction techniques utilize the object's motion history to predict the future path(s). However, these techniques fail when the history is unavailable which realistically happens for multiple reasons such as; history might be difficult to obtain, newly registered user has no past history, or previously recorded data is protected for privacy reasons. This paper introduces a novel system named SimilarMove to predict the future paths of moving objects on road networks without relying on their past trajectories. SimilarMove analyzes the motion pattern of the moving object under investigation and identifies other moving objects that show similar motion patterns. Then, a Markov Model is adopted to digest this set of similar motion patterns and produce the next potential movements of the object under investigation along with their likelihoods. A key aspect of SimilarMove lies in achieving a high quality prediction while being efficient in terms of performance.
References
[1]
Abdeltawab M. Hendawi, Mohamed Khalefa, Harry Liu, Mohamed Ali, John A. Stankovic. A Vision for Micro and Macro Location Aware Services. In Proceedings of the 23rd ACM SIGSPATIAL GIS, Francisco Bay Area, CA, October 2016.
[2]
Abdeltawab M. Hendawi, Mohamed Ali, and Mohamed F. Mokbel. Panda*: A Generic and Scalable Framework for Predictive Spatio-temporal Queries. GeoInformatica, 1--34, 2012.
[3]
Helmut Alt and Michael Godau. Computing the fréchet distance between two polygonal curves. International Journal of Computational Geometry and Applications, 05(01n02), 1995.
[4]
Abdeltawab M. Hendawi, Jie Bao, and Mohamed F. Mokbel. iRoad: A Framework For Scalable Predictive Query Processing On Road Networks. In Proceedings of the International Conference on Very Large Databases, VLDB 2013, Riva Del Garda, Italy, August, 2013.
[5]
Francisco Neto, Cláudio Baptista, and Claudio Campelo. Prediction of Destinations and Routes in Urban Trips with Automated Identification of Place Types and Stay Points. Brazilian Journal of Cartography, 2016.
[6]
Chaoming Song, Zehui Qu, Nicholas Blumm, and Albert-László Barabási. Limits of predictability in human mobility. Science, 327(5968), 2010.
[7]
Abdeltawab M. Hendawi, Jayant Gupta, Youying Shi, Hossam Fattah, and Mohamed Ali. The Microsoft Reactive Framework Meets The Internet of Moving Things. In the proceedings of the IEEE ICDE, 2017.
[8]
Youying Shi, Abdeltawab M. Hendawi, Hossam Fattah, and Mohamed Ali. RxSpatial: Reactive Spatial Library for Real-Time Location Tracking and Processing. In Proceedings of the ACM International Conference on Management of Data, ACM SIGMOD 2016, San Francisco, USA, June, 20163.
[9]
Youying Shi, Abdeltawab M. Hendawi, Hossam Fattah, and Mohamed Ali. Reactive Spatial Library for Real-Time Location Tracking and Processing. In proceedings of the 23rd ACM SIGSPATIAL GIS, Francisco Bay Area, CA, October 2016.
[10]
Jon Froehlich and John Krumm. Route Prediction from Trip Observations. SAE Technical Paper Series, 2008.
[11]
M. Vlachos, D. Gunopulos, and G. Kollios. Robust Similarity Measures for Mobile Object Trajectories. Proceedings. 13th International Workshop on Database and Expert Systems Applications, 2002.
[12]
Abdeltawab Hendawi and Mohamed Mokbel. Predictive Spatio-Temporal Queries: A Comprehensive Survey and Future Directions. In Proceeding of the first ACM SIGSPATIAL International Workshop on Mobile Geographic Information Systems, MobiGIS 2012, Redondo Beach, CA, November 2012.
[13]
Abdeltawab M. Hendawi and Mohamed F. Mokbel. Panda: A Predictive Spatio-Temporal Query Processor. In Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2012, Redondo Beach, CA, Nov., 2012.
[14]
Heng Shen, Hoyoung Jeung, Qing Liu and Xiaofang Zhou. A Hybrid Prediction Model for Moving Objects. 2008 IEEE 24th International Conference on Data Engineering, 2008.
[15]
Byoung-Kee Yi, H. Jagadish, and C. Faloutsos. Efficient retrieval of similar time sequences under time warping. Proceedings 14th International Conference on Data Engineering, 1998.
[16]
Jung-Rae Hwang, Hye-Young Kang, and Ki-Joune Li. Spatio-temporal similarity analysis between trajectories on road networks. Perspectives in Conceptual Modeling Lecture Notes in Computer Science, 2005.
[17]
Jung-Rae Hwang, Hye-Young Kang, and Ki-Joune Li. Searching for Similar Trajectories on Road Networks Using Spatio-temporal Similarity. Advances in Databases and Information Systems Lecture Notes in Computer Science, 2006.
[18]
Hassan Karimi and Xiong Liu. A predictive location model for location-based services. In Proceedings of the ACM-GIS'03, 2003.
[19]
Yo-Sub Han, Sang-KiKo, and Kai Salomaa. Computing the Edit-Distance between a Regular Language and a Context-Free Language. Developments in Language Theory Lecture Notes in Computer Science, 2012.
[20]
Michail Vlachos, George Kollios, and Dimitrios Gunopulos. Discovering Similar Multidimensional Trajectories. Proceedings 18th International Conference on Data Engineering, 2002.
[21]
Timo Koski. Hidden Markov Models: an Overview. Hidden Markov Models for Bioinformatics Computational Biology, 2001.
[22]
John Krumm. Real Time Destination Prediction Based On Efficient Routes. SAE Technical Paper Series, 2006.
[23]
John Krumm. A Markov Model for Driver Turn Prediction. SAE Technical Paper Series, 2008.
[24]
Anil Maheshwari and Jiehua Yi. On Computing Fréchet Distance of Two Paths on a Convex Polyhedron. 21st European Workshop on Computational Geometry, 2005.
[25]
Abdeltawab M. Hendawi, Jie Bao, Mohamed F. Mokbel, and Mohamed Ali. Predictive Tree: An Efficient Index for Predictive Queries On Road Networks. In Proceedings of the 31th IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April, 2015.
[26]
Emilian Necula. Dynamic traffic flow prediction based on GPS Data. 2014 IEEE 26th International Conference on Tools with Artificial Intelligence, 2014.
[27]
OpenStreetMap. https://www.openstreetmap.org/, accessed on april 2018.
[28]
Hongbin Zhao, Qilong Han, Haiwei Pan, and Guisheng Yin. Spatio-temporal Similarity Measure for Trajectories on Road Networks. 2009 Fourth International Conference on Internet Computing for Science and Engineering, 2009.
[29]
Lei Chen, M. Qzsu, and Vincent Oria. Robust and fast similarity search for moving object trajectories. Proceedings of the 2005 ACM SIGMOD international conference on Management of data-SIGMOD 05, 2005.
[30]
Stan Salvador and Philip Chan. Toward accurate dynamic time warping in linear time and space. Intelligent Data Analysis, 11(5), 2007.
[31]
Vacláv Chvátal, David Sankoff, and Vaclav Chvatal. Longest common subsequences of two random sequences. Journal of Applied Probability, 12(2), 1975.
[32]
J. Sun, Dimitris Papadias, Yufei Tao, and Bin Liu. Querying about the past, the present, and the future in spatio-temporal databases. Proceedings. 20th International Conference on Data Engineering, 2004.
[33]
Kevin Toohey and Matt Duckham. Trajectory similarity measures. SIGSPATIAL Special, 7(1), 2015.
[34]
Yisong Zheng, Qian Wang, Wangling, and Mo Kuang. Research into the driver's route choice under existing real-time traffic information. 2008 IEEE International Conference on Industrial Engineering and Engineering Management, 2008.
[35]
R. Simmons, B. Browning, Yilu Zhang, and V. Sadekar. Learning to Predict Driver Route and Destination Intent. 2006 IEEE Intelligent Transportation Systems Conference, 2006.
[36]
Yu Zheng, Xing Xie, and Wei-Ying Ma. Geolife: A collaborative social networking service among user, location and trajectory. IEEE Data Eng. Bull., 33(2):32--39, 2010.
[37]
Shaojie Qiao, Nan Han, William Zhu, and Louis Gutierrez. TraPlan: an effective three-in-one trajectory-prediction model in transportation networks. IEEE Transactions on Intelligent Transportation Systems, 16(3), 2015.
Index Terms
- SimilarMove: Similarity-based Prediction for Moving Object Future Path
Recommendations
Predictive spatio-temporal queries: a comprehensive survey and future directions
MobiGIS '12: Proceedings of the First ACM SIGSPATIAL International Workshop on Mobile Geographic Information SystemsPredictive queries over spatio-temporal data proved to be vital in many location-based services including traffic management, ride sharing, and advertising. In the last few years, one of the most exciting work on spatio-temporal data management is about ...
From destination prediction to route prediction
A prediction of a vehicle's route would be useful for giving the driver advance warnings and alerts about upcoming situations and opportunities. This paper presents a new algorithm for predicting a driver's route based on a probabilistic prediction of ...
Searching for similar trajectories in spatial networks
In several applications, data objects move on pre-defined spatial networks such as road segments, railways, and invisible air routes. Many of these objects exhibit similarity with respect to their traversed paths, and therefore two objects can be ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2018
50 pages
ISBN:9781450360425
DOI:10.1145/3283590
Copyright © 2018 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 ACM 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: 06 November 2018
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
SIGSPATIAL '18
Sponsor:
SIGSPATIAL '18: 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
November 6, 2018
WA, Seattle, USA
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 82Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)2
Reflects downloads up to 13 Dec 2024
Other Metrics
Citations
Cited By
View all- Abdalla MHendawi AMokhtar HElgamal NKrumm JAli M(2020)$DeepMotions$ : A Deep Learning System for Path Prediction Using Similar MotionsIEEE Access10.1109/ACCESS.2020.29669828(23881-23894)Online publication date: 2020
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