Indexing Trajectories for Travel-Time Histogram Retrieval

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

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

2 Citationer (Scopus)
16 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.

TitelAdvances in Database Technology - EDBT 2019 : 22nd International Conference on Extending Database Technology, Proceedings
RedaktørerBerthold Reinwald, Carsten Binnig, Zoi Kaoudi, Helena Galhardas, Melanie Herschel, Irini Fundulaki
Antal sider12
Publikationsdato29 mar. 2019
ISBN (Elektronisk)9783893180813
StatusUdgivet - 29 mar. 2019
Begivenhed22nd International Conference on Extending Database Technology, EDBT 2019 - Lisbon, Portugal
Varighed: 26 mar. 201929 mar. 2019


Konference22nd International Conference on Extending Database Technology, EDBT 2019
NavnAdvances in Database Technology

Fingeraftryk Dyk ned i forskningsemnerne om 'Indexing Trajectories for Travel-Time Histogram Retrieval'. Sammen danner de et unikt fingeraftryk.

  • Citationsformater

    Waury, R., S. Jensen, C., Koide, S., Ishikawa, Y., & Xiao, C. (2019). Indexing Trajectories for Travel-Time Histogram Retrieval. I B. Reinwald, C. Binnig, Z. Kaoudi, H. Galhardas, M. Herschel, & I. Fundulaki (red.), Advances in Database Technology - EDBT 2019: 22nd International Conference on Extending Database Technology, Proceedings (s. 157-168). Advances in Database Technology