Finding time-dependent shortest paths over large graphs

Ding, B; Yu, JX; Qin, L

Finding time-dependent shortest paths over large graphs

Ding, B Yu, JX

Qin, L

Permalink

Publication Type:: Conference Proceeding
Citation:: Advances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings, 2008, pp. 205 - 216
Issue Date:: 2008-05-16

Closed Access

	Filename	Description	Size
	2013002372OK.pdf		314.33 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Ding, B	en_US
dc.contributor.author	Yu, JX https://orcid.org/0000-0002-9738-827X	en_US
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062	en_US
dc.date.issued	2008-05-16	en_US
dc.identifier.citation	Advances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings, 2008, pp. 205 - 216	en_US
dc.identifier.isbn	9781595939265	en_US
dc.identifier.uri	http://hdl.handle.net/10453/28926
dc.description.abstract	The spatial and temporal databases have been studied widely and intensively over years. In this paper, we study how to answer queries of finding the best departure time that minimizes the total travel time from a place to another, over a road network, where the traffic conditions dynamically change from time to time. We study a generalized form of this problem, called the time-dependent shortest-path problem. A time-dependent graph GT is a graph that has an edge-delay function, wi,j(t), associated with each edge (v i, vj), to be stored in a database. The edge-delay function Wi,j(t) specifies how much time it takes to travel from node v i to node Vj, if it departs from vi at time t. A user-specified query is to ask the minimum-travel-time path, from a source node, vs, to a destination node, ve, over the time-dependent graph, GT, with the best departure time to be selected from a time interval T. We denote this user query as LTT(vs ve, T) over GT. The challenge of this problem is the added complexity due to the time dependency in the time-dependent graph. That is, edge delays are not constants, and can vary from time to time. In this paper, we propose a novel algorithm to find the minimum-travel-time path with the best departure time for a LTT(vs, ve, T) query over a large graph GT. Our approach outperforms existing algorithms in terms of both time complexity in theory and efficiency in practice. We will discuss the design of our algorithm, together with its correctness and complexity. We conducted extensive experimental studies over large graphs and will report our findings. Copyright 2008 ACM.	en_US
dc.relation.ispartof	Advances in Database Technology - EDBT 2008 - 11th International Conference on Extending Database Technology, Proceedings	en_US
dc.relation.isbasedon	10.1145/1353343.1353371	en_US
dc.title	Finding time-dependent shortest paths over large graphs	en_US
dc.type	Conference Proceeding
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
dc.location.activity	Nantes, France	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.publication-status	Published	en_US

Abstract:

The spatial and temporal databases have been studied widely and intensively over years. In this paper, we study how to answer queries of finding the best departure time that minimizes the total travel time from a place to another, over a road network, where the traffic conditions dynamically change from time to time. We study a generalized form of this problem, called the time-dependent shortest-path problem. A time-dependent graph GT is a graph that has an edge-delay function, wi,j(t), associated with each edge (v i, vj), to be stored in a database. The edge-delay function Wi,j(t) specifies how much time it takes to travel from node v i to node Vj, if it departs from vi at time t. A user-specified query is to ask the minimum-travel-time path, from a source node, vs, to a destination node, ve, over the time-dependent graph, GT, with the best departure time to be selected from a time interval T. We denote this user query as LTT(vs ve, T) over GT. The challenge of this problem is the added complexity due to the time dependency in the time-dependent graph. That is, edge delays are not constants, and can vary from time to time. In this paper, we propose a novel algorithm to find the minimum-travel-time path with the best departure time for a LTT(vs, ve, T) query over a large graph GT. Our approach outperforms existing algorithms in terms of both time complexity in theory and efficiency in practice. We will discuss the design of our algorithm, together with its correctness and complexity. We conducted extensive experimental studies over large graphs and will report our findings. Copyright 2008 ACM.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/28926