Distributed shortest path query processing on dynamic road networks

Zhang, D; Yang, D; Wang, Y; Tan, KL; Cao, J; Shen, HT

Distributed shortest path query processing on dynamic road networks

Zhang, D Yang, D Wang, Y Tan, KL Cao, J Shen, HT

Permalink

Publication Type:: Journal Article
Citation:: VLDB Journal, 2017, 26 (3), pp. 399 - 419
Issue Date:: 2017-06-01

Closed Access

	Filename	Description	Size
	10.1007%2Fs00778-017-0457-6.pdf	Published Version	3.31 MB	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	Zhang, D	en_US
dc.contributor.author	Yang, D	en_US
dc.contributor.author	Wang, Y	en_US
dc.contributor.author	Tan, KL	en_US
dc.contributor.author	Cao, J	en_US
dc.contributor.author	Shen, HT	en_US
dc.date.issued	2017-06-01	en_US
dc.identifier.citation	VLDB Journal, 2017, 26 (3), pp. 399 - 419	en_US
dc.identifier.issn	1066-8888	en_US
dc.identifier.uri	http://hdl.handle.net/10453/124176
dc.description.abstract	© 2017, Springer-Verlag Berlin Heidelberg. Shortest path query processing on dynamic road networks is a fundamental component for real-time navigation systems. In the face of an enormous volume of customer demand from Uber and similar apps, it is desirable to study distributed shortest path query processing that can be deployed on elastic and fault-tolerant cloud platforms. In this paper, we combine the merits of distributed streaming computing systems and lightweight indexing to build an efficient shortest path query processing engine on top of Yahoo S4. We propose two types of asynchronous communication algorithms for early termination. One is first-in-first-out message propagation with certain optimizations, and the other is prioritized message propagation with the help of navigational intelligence. Extensive experiments were conducted on large-scale real road networks, and the results show that the query efficiency of our methods can meet the real-time requirement and is superior to Pregel and Pregel+. The source code of our system is publicly available at https://github.com/yangdingyu/cands.	en_US
dc.relation.ispartof	VLDB Journal	en_US
dc.relation.isbasedon	10.1007/s00778-017-0457-6	en_US
dc.subject.classification	Information Systems	en_US
dc.title	Distributed shortest path query processing on dynamic road networks	en_US
dc.type	Journal Article
utslib.citation.volume	3	en_US
utslib.citation.volume	26	en_US
utslib.for	0805 Distributed Computing	en_US
utslib.for	0804 Data Format	en_US
utslib.for	0806 Information Systems	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/Faculty of Engineering and Information Technology/School of Software
utslib.copyright.status	closed_access
pubs.issue	3	en_US
pubs.publication-status	Published	en_US
pubs.volume	26	en_US

Abstract:

© 2017, Springer-Verlag Berlin Heidelberg. Shortest path query processing on dynamic road networks is a fundamental component for real-time navigation systems. In the face of an enormous volume of customer demand from Uber and similar apps, it is desirable to study distributed shortest path query processing that can be deployed on elastic and fault-tolerant cloud platforms. In this paper, we combine the merits of distributed streaming computing systems and lightweight indexing to build an efficient shortest path query processing engine on top of Yahoo S4. We propose two types of asynchronous communication algorithms for early termination. One is first-in-first-out message propagation with certain optimizations, and the other is prioritized message propagation with the help of navigational intelligence. Extensive experiments were conducted on large-scale real road networks, and the results show that the query efficiency of our methods can meet the real-time requirement and is superior to Pregel and Pregel+. The source code of our system is publicly available at https://github.com/yangdingyu/cands.

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

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