Adaptive fastest path computation on a road network: A traffic mining approach

Hector Gonzalez, Jiawei Han, Xiaolei Li, Margaret Myslinska, John Paul Sondag

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Efficient fastest path computation in the presence of varying speed conditions on a large scale road network is an essential problem in modern navigation systems. Factors affecting road speed, such as weather, time of day, and vehicle type, need to be considered in order to select fast routes that match current driving conditions. Most existing systems compute fastest paths based on road Euclidean distance and a small set of predefined road speeds. However, "History is often the best teacher". Historical traffic data or driving patterns are often more useful than the simple Euclidean distance-based computation because people must have good reasons to choose these routes, e.g., they may want to avoid those that pass through high crime areas at night or that likely encounter accidents, road construction, or traffic jams. In this paper, we present an adaptive fastest path algorithm capable of efficiently accounting for important driving and speed patterns mined from a large set of traffic data. The algorithm is based on the following observations: (1) The hierarchy of roads can be used to partition the road network into areas, and different path pre-computation strategies can be used at the area level, (2) we can limit our route search strategy to edges and path segments that are actually frequently traveled in the data, and (3) drivers usually traverse the road network through the largest roads available given the distance of the trip, except if there are small roads with a significant speed advantage over the large ones. Through an extensive experimental evaluation on real road networks we show that our algorithm provides desirable (short and well-supported) routes, and that it is significantly faster than competing methods.

Original languageEnglish (US)
Title of host publication33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings
EditorsJohannes Gehrke, Christoph Koch, Minos Garofalakis, Karl Aberer, Carl-Christian Kanne, Erich J. Neuhold, Venkatesh Ganti, Wolfgang Klas, Chee-Yong Chan, Divesh Srivastava, Dana Florescu, Anand Deshpande
PublisherAssociation for Computing Machinery, Inc
Pages794-805
Number of pages12
ISBN (Electronic)9781595936493
StatePublished - Jan 1 2007
Event33rd International Conference on Very Large Data Bases, VLDB 2007 - Vienna, Austria
Duration: Sep 23 2007Sep 27 2007

Publication series

Name33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings

Other

Other33rd International Conference on Very Large Data Bases, VLDB 2007
CountryAustria
CityVienna
Period9/23/079/27/07

Fingerprint

Road construction
Crime
Navigation systems
Accidents
History
Road network
Roads
Euclidean distance
Factors
Pass-through
Navigation
Weather
Search strategy
Evaluation

ASJC Scopus subject areas

  • Hardware and Architecture
  • Information Systems and Management
  • Information Systems
  • Software

Cite this

Gonzalez, H., Han, J., Li, X., Myslinska, M., & Sondag, J. P. (2007). Adaptive fastest path computation on a road network: A traffic mining approach. In J. Gehrke, C. Koch, M. Garofalakis, K. Aberer, C-C. Kanne, E. J. Neuhold, V. Ganti, W. Klas, C-Y. Chan, D. Srivastava, D. Florescu, ... A. Deshpande (Eds.), 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings (pp. 794-805). (33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings). Association for Computing Machinery, Inc.

Adaptive fastest path computation on a road network : A traffic mining approach. / Gonzalez, Hector; Han, Jiawei; Li, Xiaolei; Myslinska, Margaret; Sondag, John Paul.

33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings. ed. / Johannes Gehrke; Christoph Koch; Minos Garofalakis; Karl Aberer; Carl-Christian Kanne; Erich J. Neuhold; Venkatesh Ganti; Wolfgang Klas; Chee-Yong Chan; Divesh Srivastava; Dana Florescu; Anand Deshpande. Association for Computing Machinery, Inc, 2007. p. 794-805 (33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Gonzalez, H, Han, J, Li, X, Myslinska, M & Sondag, JP 2007, Adaptive fastest path computation on a road network: A traffic mining approach. in J Gehrke, C Koch, M Garofalakis, K Aberer, C-C Kanne, EJ Neuhold, V Ganti, W Klas, C-Y Chan, D Srivastava, D Florescu & A Deshpande (eds), 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings. 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings, Association for Computing Machinery, Inc, pp. 794-805, 33rd International Conference on Very Large Data Bases, VLDB 2007, Vienna, Austria, 9/23/07.
Gonzalez H, Han J, Li X, Myslinska M, Sondag JP. Adaptive fastest path computation on a road network: A traffic mining approach. In Gehrke J, Koch C, Garofalakis M, Aberer K, Kanne C-C, Neuhold EJ, Ganti V, Klas W, Chan C-Y, Srivastava D, Florescu D, Deshpande A, editors, 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings. Association for Computing Machinery, Inc. 2007. p. 794-805. (33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings).
Gonzalez, Hector ; Han, Jiawei ; Li, Xiaolei ; Myslinska, Margaret ; Sondag, John Paul. / Adaptive fastest path computation on a road network : A traffic mining approach. 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings. editor / Johannes Gehrke ; Christoph Koch ; Minos Garofalakis ; Karl Aberer ; Carl-Christian Kanne ; Erich J. Neuhold ; Venkatesh Ganti ; Wolfgang Klas ; Chee-Yong Chan ; Divesh Srivastava ; Dana Florescu ; Anand Deshpande. Association for Computing Machinery, Inc, 2007. pp. 794-805 (33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings).
@inproceedings{6a290a2073004484b441ccf8fca77e5f,
title = "Adaptive fastest path computation on a road network: A traffic mining approach",
abstract = "Efficient fastest path computation in the presence of varying speed conditions on a large scale road network is an essential problem in modern navigation systems. Factors affecting road speed, such as weather, time of day, and vehicle type, need to be considered in order to select fast routes that match current driving conditions. Most existing systems compute fastest paths based on road Euclidean distance and a small set of predefined road speeds. However, {"}History is often the best teacher{"}. Historical traffic data or driving patterns are often more useful than the simple Euclidean distance-based computation because people must have good reasons to choose these routes, e.g., they may want to avoid those that pass through high crime areas at night or that likely encounter accidents, road construction, or traffic jams. In this paper, we present an adaptive fastest path algorithm capable of efficiently accounting for important driving and speed patterns mined from a large set of traffic data. The algorithm is based on the following observations: (1) The hierarchy of roads can be used to partition the road network into areas, and different path pre-computation strategies can be used at the area level, (2) we can limit our route search strategy to edges and path segments that are actually frequently traveled in the data, and (3) drivers usually traverse the road network through the largest roads available given the distance of the trip, except if there are small roads with a significant speed advantage over the large ones. Through an extensive experimental evaluation on real road networks we show that our algorithm provides desirable (short and well-supported) routes, and that it is significantly faster than competing methods.",
author = "Hector Gonzalez and Jiawei Han and Xiaolei Li and Margaret Myslinska and Sondag, {John Paul}",
year = "2007",
month = "1",
day = "1",
language = "English (US)",
series = "33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings",
publisher = "Association for Computing Machinery, Inc",
pages = "794--805",
editor = "Johannes Gehrke and Christoph Koch and Minos Garofalakis and Karl Aberer and Carl-Christian Kanne and Neuhold, {Erich J.} and Venkatesh Ganti and Wolfgang Klas and Chee-Yong Chan and Divesh Srivastava and Dana Florescu and Anand Deshpande",
booktitle = "33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings",

}

TY - GEN

T1 - Adaptive fastest path computation on a road network

T2 - A traffic mining approach

AU - Gonzalez, Hector

AU - Han, Jiawei

AU - Li, Xiaolei

AU - Myslinska, Margaret

AU - Sondag, John Paul

PY - 2007/1/1

Y1 - 2007/1/1

N2 - Efficient fastest path computation in the presence of varying speed conditions on a large scale road network is an essential problem in modern navigation systems. Factors affecting road speed, such as weather, time of day, and vehicle type, need to be considered in order to select fast routes that match current driving conditions. Most existing systems compute fastest paths based on road Euclidean distance and a small set of predefined road speeds. However, "History is often the best teacher". Historical traffic data or driving patterns are often more useful than the simple Euclidean distance-based computation because people must have good reasons to choose these routes, e.g., they may want to avoid those that pass through high crime areas at night or that likely encounter accidents, road construction, or traffic jams. In this paper, we present an adaptive fastest path algorithm capable of efficiently accounting for important driving and speed patterns mined from a large set of traffic data. The algorithm is based on the following observations: (1) The hierarchy of roads can be used to partition the road network into areas, and different path pre-computation strategies can be used at the area level, (2) we can limit our route search strategy to edges and path segments that are actually frequently traveled in the data, and (3) drivers usually traverse the road network through the largest roads available given the distance of the trip, except if there are small roads with a significant speed advantage over the large ones. Through an extensive experimental evaluation on real road networks we show that our algorithm provides desirable (short and well-supported) routes, and that it is significantly faster than competing methods.

AB - Efficient fastest path computation in the presence of varying speed conditions on a large scale road network is an essential problem in modern navigation systems. Factors affecting road speed, such as weather, time of day, and vehicle type, need to be considered in order to select fast routes that match current driving conditions. Most existing systems compute fastest paths based on road Euclidean distance and a small set of predefined road speeds. However, "History is often the best teacher". Historical traffic data or driving patterns are often more useful than the simple Euclidean distance-based computation because people must have good reasons to choose these routes, e.g., they may want to avoid those that pass through high crime areas at night or that likely encounter accidents, road construction, or traffic jams. In this paper, we present an adaptive fastest path algorithm capable of efficiently accounting for important driving and speed patterns mined from a large set of traffic data. The algorithm is based on the following observations: (1) The hierarchy of roads can be used to partition the road network into areas, and different path pre-computation strategies can be used at the area level, (2) we can limit our route search strategy to edges and path segments that are actually frequently traveled in the data, and (3) drivers usually traverse the road network through the largest roads available given the distance of the trip, except if there are small roads with a significant speed advantage over the large ones. Through an extensive experimental evaluation on real road networks we show that our algorithm provides desirable (short and well-supported) routes, and that it is significantly faster than competing methods.

UR - http://www.scopus.com/inward/record.url?scp=85011017713&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85011017713&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85011017713

T3 - 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings

SP - 794

EP - 805

BT - 33rd International Conference on Very Large Data Bases, VLDB 2007 - Conference Proceedings

A2 - Gehrke, Johannes

A2 - Koch, Christoph

A2 - Garofalakis, Minos

A2 - Aberer, Karl

A2 - Kanne, Carl-Christian

A2 - Neuhold, Erich J.

A2 - Ganti, Venkatesh

A2 - Klas, Wolfgang

A2 - Chan, Chee-Yong

A2 - Srivastava, Divesh

A2 - Florescu, Dana

A2 - Deshpande, Anand

PB - Association for Computing Machinery, Inc

ER -