Indexing Trajectories for Travel-Time Histogram Retrieval

Robert Waury, Christian S. Jensen, Satoshi Koide, Yoshiharu Ishikawa, Chuan Xiao

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

2 Citations (Scopus)
32 Downloads (Pure)


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.

Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2019 : 22nd International Conference on Extending Database Technology, Proceedings
EditorsBerthold Reinwald, Carsten Binnig, Zoi Kaoudi, Helena Galhardas, Melanie Herschel, Irini Fundulaki
Number of pages12
Publication date29 Mar 2019
ISBN (Electronic)9783893180813
Publication statusPublished - 29 Mar 2019
Event22nd International Conference on Extending Database Technology, EDBT 2019 - Lisbon, Portugal
Duration: 26 Mar 201929 Mar 2019


Conference22nd International Conference on Extending Database Technology, EDBT 2019
SeriesAdvances in Database Technology

Fingerprint Dive into the research topics of 'Indexing Trajectories for Travel-Time Histogram Retrieval'. Together they form a unique fingerprint.

Cite this