Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach

Zhang, U; Yuan, L; Li, W; Qin, L; Zhang, Y

Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach

Zhang, U Yuan, L Li, W

Qin, L

Zhang, Y

Permalink

Publisher:: VLDB Endowment
Publication Type:: Journal Article
Citation:: Proceedings of the VLDB Endowment, 2021, 15, (3), pp. 686-698
Issue Date:: 2021-01-01

Recently Added

	Filename	Description	Size
	3494124.3494148.pdf	Published version	1.22 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is new to OPUS and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Zhang, U
dc.contributor.author	Yuan, L
dc.contributor.author	Li, W https://orcid.org/0000-0003-4941-8814
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.date.accessioned	2022-05-23T22:59:27Z
dc.date.available	2022-05-23T22:59:27Z
dc.date.issued	2021-01-01
dc.identifier.citation	Proceedings of the VLDB Endowment, 2021, 15, (3), pp. 686-698
dc.identifier.issn	2150-8097
dc.identifier.issn	2150-8097
dc.identifier.uri	http://hdl.handle.net/10453/157657
dc.description.abstract	Computing the shortest path between two vertices is a fundamental problem in road networks. Most of the existing works assume that the edges in the road networks have no labels, but in many real applications, the edges have labels and label constraints may be placed on the edges appearing on a valid shortest path. Hence, we study the label-constrained shortest path queries in this paper. In order to process such queries efficiently, we adopt an index-based approach and propose a novel index structure, LSD-Index, based on tree decomposition. With LSD-Index, we design an efficient query processing algorithm with good performance guarantees. Moreover, we also propose an algorithm to construct LSD-Index and further improve the efficiency of index construction by exploiting the parallel computing techniques. We conduct extensive performance studies using large real road networks including the whole USA road network. Compared with the state-of-the-art approach, the experimental results demonstrate that our algorithm not only achieves up to 2 orders of magnitude speedup in query processing time but also consumes much less index space. Meanwhile, the indexing time is also competitive, especially that for the parallel index construction algorithm.
dc.language	en
dc.publisher	VLDB Endowment
dc.relation.ispartof	Proceedings of the VLDB Endowment
dc.relation.isbasedon	10.14778/3494124.3494148
dc.rights	This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment.
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.subject	0802 Computation Theory and Mathematics, 0806 Information Systems, 0807 Library and Information Studies
dc.title	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach
dc.type	Journal Article
utslib.citation.volume	15
utslib.for	0802 Computation Theory and Mathematics
utslib.for	0806 Information Systems
utslib.for	0807 Library and Information Studies
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 - AAII - Australian Artificial Intelligence Institute
utslib.copyright.status	recently_added	*
dc.date.updated	2022-05-23T22:59:26Z
pubs.issue	3
pubs.publication-status	Published
pubs.volume	15
utslib.citation.issue	3

Abstract:

Computing the shortest path between two vertices is a fundamental problem in road networks. Most of the existing works assume that the edges in the road networks have no labels, but in many real applications, the edges have labels and label constraints may be placed on the edges appearing on a valid shortest path. Hence, we study the label-constrained shortest path queries in this paper. In order to process such queries efficiently, we adopt an index-based approach and propose a novel index structure, LSD-Index, based on tree decomposition. With LSD-Index, we design an efficient query processing algorithm with good performance guarantees. Moreover, we also propose an algorithm to construct LSD-Index and further improve the efficiency of index construction by exploiting the parallel computing techniques. We conduct extensive performance studies using large real road networks including the whole USA road network. Compared with the state-of-the-art approach, the experimental results demonstrate that our algorithm not only achieves up to 2 orders of magnitude speedup in query processing time but also consumes much less index space. Meanwhile, the indexing time is also competitive, especially that for the parallel index construction algorithm.

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

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