Efficient Shortest Path Counting on Large Road Networks

Qiu, YX; Wen, D; Qin, L; Li, W; Li, RH; Zhang Ying.Zhang@Uts.Edu.Au, Y

Efficient Shortest Path Counting on Large Road Networks

Qiu, YX Wen, D

Qin, L

Li, W

Li, RH Zhang Ying.Zhang@Uts.Edu.Au, Y

Permalink

Publisher:: Association for Computing Machinery (ACM)
Publication Type:: Journal Article
Citation:: Proceedings of the VLDB Endowment, 2022, 15, (10), pp. 2098-2110
Issue Date:: 2022-01-01

Open Access

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is open access.

Adobe PDF

Download Published versionAdobe PDF (1.89 MB)

View on publisher's site

View statistics

Full metadata record

Field	Value	Language
dc.contributor.author	Qiu, YX
dc.contributor.author	Wen, D https://orcid.org/0000-0002-0903-1503
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Li, W https://orcid.org/0000-0003-4941-8814
dc.contributor.author	Li, RH
dc.contributor.author	Zhang Ying.Zhang@Uts.Edu.Au, Y
dc.date.accessioned	2023-02-28T00:51:31Z
dc.date.available	2023-02-28T00:51:31Z
dc.date.issued	2022-01-01
dc.identifier.citation	Proceedings of the VLDB Endowment, 2022, 15, (10), pp. 2098-2110
dc.identifier.issn	2150-8097
dc.identifier.issn	2150-8097
dc.identifier.uri	http://hdl.handle.net/10453/166491
dc.description.abstract	The shortest path distance and related concepts lay the foundations of many real-world applications in road network analysis. The shortest path count has drawn much research attention in academia, not only as a closeness metric accompanying the shorted distance but also serving as a building block of centrality computation. This paper aims to improve the efficiency of counting the shortest paths between two query vertices on a large road network. We propose a novel index solution by organizing all vertices in a tree structure and propose several optimizations to speed up the index construction. We conduct extensive experiments on 14 realworld networks. Compared with the state-of-the-art solution, we achieve much higher efficiency on both query processing and index construction with a more compact index.
dc.language	en
dc.publisher	Association for Computing Machinery (ACM)
dc.relation.ispartof	Proceedings of the VLDB Endowment
dc.relation.isbasedon	10.14778/3547305.3547315
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	0802 Computation Theory and Mathematics, 0806 Information Systems, 0807 Library and Information Studies
dc.title	Efficient Shortest Path Counting on Large Road Networks
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	open_access	*
dc.date.updated	2023-02-28T00:51:29Z
pubs.issue	10
pubs.publication-status	Published
pubs.volume	15
utslib.citation.issue	10

Abstract:

The shortest path distance and related concepts lay the foundations of many real-world applications in road network analysis. The shortest path count has drawn much research attention in academia, not only as a closeness metric accompanying the shorted distance but also serving as a building block of centrality computation. This paper aims to improve the efficiency of counting the shortest paths between two query vertices on a large road network. We propose a novel index solution by organizing all vertices in a tree structure and propose several optimizations to speed up the index construction. We conduct extensive experiments on 14 realworld networks. Compared with the state-of-the-art solution, we achieve much higher efficiency on both query processing and index construction with a more compact index.

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

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