TY - GEN
T1 - Indexing Trajectories for Travel-Time Histogram Retrieval
AU - Waury, Robert
AU - S. Jensen, Christian
AU - Koide, Satoshi
AU - Ishikawa, Yoshiharu
AU - Xiao, Chuan
PY - 2019/3/29
Y1 - 2019/3/29
N2 - A key service in vehicular transportation is routing according to estimated travel times. With the availability of massive volumes of vehicle trajectory data, it has become increasingly feasible to estimate travel times, which are typically modeled as probability distributions in the form of histograms. An earlier study shows that use of a carefully selected, context-dependent subset of available trajectories when estimating a travel-time histogram along a user-specified path can significantly improve the accuracy of the estimates. This selection of trajectories cannot occur in a pre-processing step, but must occur online—it must be integrated into the routing itself. It is then a key challenge to be able to select very efficiently the "right" subset of trajectories that offer the best accuracy when the cost of a route is to be assessed. To address this challenge, we propose a solution that applies novel indexing to all available trajectories and that then is capable of selecting the most relevant trajectories and of computing a travel-time distribution based on these trajectories. Specifically, the solution utilizes an in-memory trajectory index and a greedy algorithm to identify and retrieve the relevant trajectories. The paper reports on an extensive empirical study with a large real-world GPS data set that offers insight into the accuracy and efficiency of the proposed solution. The study shows that the proposed online selection of trajectories can be performed efficiently and is able to provide highly accurate travel-time distributions.
AB - A key service in vehicular transportation is routing according to estimated travel times. With the availability of massive volumes of vehicle trajectory data, it has become increasingly feasible to estimate travel times, which are typically modeled as probability distributions in the form of histograms. An earlier study shows that use of a carefully selected, context-dependent subset of available trajectories when estimating a travel-time histogram along a user-specified path can significantly improve the accuracy of the estimates. This selection of trajectories cannot occur in a pre-processing step, but must occur online—it must be integrated into the routing itself. It is then a key challenge to be able to select very efficiently the "right" subset of trajectories that offer the best accuracy when the cost of a route is to be assessed. To address this challenge, we propose a solution that applies novel indexing to all available trajectories and that then is capable of selecting the most relevant trajectories and of computing a travel-time distribution based on these trajectories. Specifically, the solution utilizes an in-memory trajectory index and a greedy algorithm to identify and retrieve the relevant trajectories. The paper reports on an extensive empirical study with a large real-world GPS data set that offers insight into the accuracy and efficiency of the proposed solution. The study shows that the proposed online selection of trajectories can be performed efficiently and is able to provide highly accurate travel-time distributions.
UR - http://www.scopus.com/inward/record.url?scp=85064939071&partnerID=8YFLogxK
U2 - 10.5441/002/edbt.2019.15
DO - 10.5441/002/edbt.2019.15
M3 - Article in proceeding
AN - SCOPUS:85064939071
T3 - Advances in Database Technology
SP - 157
EP - 168
BT - Advances in Database Technology - EDBT 2019
A2 - Reinwald, Berthold
A2 - Binnig, Carsten
A2 - Kaoudi, Zoi
A2 - Galhardas, Helena
A2 - Herschel, Melanie
A2 - Fundulaki, Irini
PB - OpenProceedings.org
T2 - 22nd International Conference on Extending Database Technology, EDBT 2019
Y2 - 26 March 2019 through 29 March 2019
ER -