TY - GEN
T1 - On limits of travel time predictions
T2 - 2014 IEEE 34th International Conference on Distributed Computing Systems, ICDCS 2014
AU - Ganti, Raghu
AU - Srivatsa, Mudhakar
AU - Abdelzaher, Tarek
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2014/8/29
Y1 - 2014/8/29
N2 - The proliferation of location sensors has resulted in the wide availability of historical location and time data. A prominent use of such data is to develop models to estimate travel-times (between arbitrary points in a city) accurately. The problem of travel-time estimation/prediction has been well studied in the past, where the proposed techniques span a spectrum of statistical methods, such as k-nearest neighbors, Gaussian regression, Artificial Neural Networks, and Support Vector Machines. In this paper, we demonstrate that, contrary to popular intuition, empirical data suggests that simple travel time predictors come very close to the fundamental error bounds achievable in delay prediction. We derive such bounds by estimating entropy that remains in travel time distributions, even after all spatio-temporal delay-influencing factors have been accounted for. Our results are based on analysis of cab traces from New York City, that feature 15 million trips. While we cannot claim generalizability to other cities, the results suggest the diminishing return of complex travel-time predictors due to the inherent nature of uncertainty in trip delays. We demonstrate a simple travel-time predictor, whose error approaches the uncertainty bound. It predicts delay based only on total distance traveled and time-of-day and is close to the optimal solution.
AB - The proliferation of location sensors has resulted in the wide availability of historical location and time data. A prominent use of such data is to develop models to estimate travel-times (between arbitrary points in a city) accurately. The problem of travel-time estimation/prediction has been well studied in the past, where the proposed techniques span a spectrum of statistical methods, such as k-nearest neighbors, Gaussian regression, Artificial Neural Networks, and Support Vector Machines. In this paper, we demonstrate that, contrary to popular intuition, empirical data suggests that simple travel time predictors come very close to the fundamental error bounds achievable in delay prediction. We derive such bounds by estimating entropy that remains in travel time distributions, even after all spatio-temporal delay-influencing factors have been accounted for. Our results are based on analysis of cab traces from New York City, that feature 15 million trips. While we cannot claim generalizability to other cities, the results suggest the diminishing return of complex travel-time predictors due to the inherent nature of uncertainty in trip delays. We demonstrate a simple travel-time predictor, whose error approaches the uncertainty bound. It predicts delay based only on total distance traveled and time-of-day and is close to the optimal solution.
KW - Information theory
KW - New York city case study
KW - Travel time prediction
KW - location based services
UR - http://www.scopus.com/inward/record.url?scp=84907781894&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84907781894&partnerID=8YFLogxK
U2 - 10.1109/ICDCS.2014.25
DO - 10.1109/ICDCS.2014.25
M3 - Conference contribution
AN - SCOPUS:84907781894
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 166
EP - 175
BT - Proceedings - International Conference on Distributed Computing Systems
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 30 June 2014 through 3 July 2014
ER -