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

Resumé

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.

OriginalsprogEngelsk
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
ForlagOpenProceedings.org
Publikationsdato29 mar. 2019
Sider157-168
ISBN (Elektronisk)9783893180813
DOI
StatusUdgivet - 29 mar. 2019
Begivenhed22nd International Conference on Extending Database Technology, EDBT 2019 - Lisbon, Portugal
Varighed: 26 mar. 201929 mar. 2019

Konference

Konference22nd International Conference on Extending Database Technology, EDBT 2019
LandPortugal
ByLisbon
Periode26/03/201929/03/2019
NavnAdvances in Database Technology - EDBT
Vol/bind2019-March

Fingerprint

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

Citer dette

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). OpenProceedings.org. Advances in Database Technology - EDBT, Bind. 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. red. / Berthold Reinwald ; Carsten Binnig ; Zoi Kaoudi ; Helena Galhardas ; Melanie Herschel ; Irini Fundulaki. OpenProceedings.org, 2019. s. 157-168 (Advances in Database Technology - EDBT, Bind 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. 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. OpenProceedings.org, Advances in Database Technology - EDBT, bind 2019-March, s. 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. red. / Berthold Reinwald; Carsten Binnig; Zoi Kaoudi; Helena Galhardas; Melanie Herschel; Irini Fundulaki. OpenProceedings.org, 2019. s. 157-168 (Advances in Database Technology - EDBT, Bind 2019-March).

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer 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

AN - SCOPUS:85064939071

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. I Reinwald B, Binnig C, Kaoudi Z, Galhardas H, Herschel M, Fundulaki I, red., Advances in Database Technology - EDBT 2019: 22nd International Conference on Extending Database Technology, Proceedings. OpenProceedings.org. 2019. s. 157-168. (Advances in Database Technology - EDBT, Bind 2019-March). https://doi.org/10.5441/002/edbt.2019.15