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

Abstract

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
PublisherOpenProceedings.org
Publication date29 Mar 2019
Pages157-168
ISBN (Electronic)9783893180813
DOIs
Publication statusPublished - 29 Mar 2019
Event22nd International Conference on Extending Database Technology, EDBT 2019 - Lisbon, Portugal
Duration: 26 Mar 201929 Mar 2019

Conference

Conference22nd International Conference on Extending Database Technology, EDBT 2019
CountryPortugal
CityLisbon
Period26/03/201929/03/2019
SeriesAdvances in Database Technology - EDBT
Volume2019-March

Fingerprint

Travel time
Trajectories
Probability distributions
Global positioning system
Availability
Data storage equipment

Cite this

Waury, R., S. Jensen, C., Koide, S., Ishikawa, Y., & Xiao, C. (2019). Indexing Trajectories for Travel-Time Histogram Retrieval. In B. Reinwald, C. Binnig, Z. Kaoudi, H. Galhardas, M. Herschel, & I. Fundulaki (Eds.), Advances in Database Technology - EDBT 2019: 22nd International Conference on Extending Database Technology, Proceedings (pp. 157-168). OpenProceedings.org. Advances in Database Technology - EDBT, Vol.. 2019-March https://doi.org/10.5441/002/edbt.2019.15
Waury, Robert ; S. Jensen, Christian ; Koide, Satoshi ; Ishikawa, Yoshiharu ; Xiao, Chuan. / Indexing Trajectories for Travel-Time Histogram Retrieval. Advances in Database Technology - EDBT 2019: 22nd International Conference on Extending Database Technology, Proceedings. editor / Berthold Reinwald ; Carsten Binnig ; Zoi Kaoudi ; Helena Galhardas ; Melanie Herschel ; Irini Fundulaki. OpenProceedings.org, 2019. pp. 157-168 (Advances in Database Technology - EDBT, Vol. 2019-March).
@inproceedings{01690e5d7cf549fa8f25e7e01d11d735,
title = "Indexing Trajectories for Travel-Time Histogram Retrieval",
abstract = "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.",
author = "Robert Waury and {S. Jensen}, Christian and Satoshi Koide and Yoshiharu Ishikawa and Chuan Xiao",
year = "2019",
month = "3",
day = "29",
doi = "10.5441/002/edbt.2019.15",
language = "English",
series = "Advances in Database Technology - EDBT",
publisher = "OpenProceedings.org",
pages = "157--168",
editor = "Berthold Reinwald and Carsten Binnig and Zoi Kaoudi and Helena Galhardas and Melanie Herschel and Irini Fundulaki",
booktitle = "Advances in Database Technology - EDBT 2019",

}

Waury, R, S. Jensen, C, Koide, S, Ishikawa, Y & Xiao, C 2019, Indexing Trajectories for Travel-Time Histogram Retrieval. in B Reinwald, C Binnig, Z Kaoudi, H Galhardas, M Herschel & I Fundulaki (eds), Advances in Database Technology - EDBT 2019: 22nd International Conference on Extending Database Technology, Proceedings. OpenProceedings.org, Advances in Database Technology - EDBT, vol. 2019-March, pp. 157-168, 22nd International Conference on Extending Database Technology, EDBT 2019, Lisbon, Portugal, 26/03/2019. https://doi.org/10.5441/002/edbt.2019.15

Indexing Trajectories for Travel-Time Histogram Retrieval. / Waury, Robert; S. Jensen, Christian; Koide, Satoshi; Ishikawa, Yoshiharu; Xiao, Chuan.

Advances in Database Technology - EDBT 2019: 22nd International Conference on Extending Database Technology, Proceedings. ed. / Berthold Reinwald; Carsten Binnig; Zoi Kaoudi; Helena Galhardas; Melanie Herschel; Irini Fundulaki. OpenProceedings.org, 2019. p. 157-168 (Advances in Database Technology - EDBT, Vol. 2019-March).

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

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

T3 - Advances in Database Technology - EDBT

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

ER -

Waury R, S. Jensen C, Koide S, Ishikawa Y, Xiao C. Indexing Trajectories for Travel-Time Histogram Retrieval. In Reinwald B, Binnig C, Kaoudi Z, Galhardas H, Herschel M, Fundulaki I, editors, Advances in Database Technology - EDBT 2019: 22nd International Conference on Extending Database Technology, Proceedings. OpenProceedings.org. 2019. p. 157-168. (Advances in Database Technology - EDBT, Vol. 2019-March). https://doi.org/10.5441/002/edbt.2019.15