Batch Processing of Shortest Path Queries in Road Networks

Mengxuan Zhang; Lei Li; Wen Hua; Xiaofang Zhou

doi:10.1007/978-3-030-12079-5_1

Batch Processing of Shortest Path Queries in Road Networks

Mengxuan Zhang, Lei Li, Wen Hua, Xiaofang Zhou

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

16 Citations (Scopus)

Abstract

Shortest path algorithm is a foundation to various location-based services (LBS) and has been extensively studied in the literature. However, server-side shortest path calculation faces a severe scalability issue when the business expands and a huge amount of requests are submitted to the server simultaneously. Although a straightforward solution widely-adopted in current industry is to deploy more processing resources, in this work, we aim to improve the efficiency algorithmically by answering queries in a batch and reusing shareable computations. In particular, we generalize the goal-directed A* algorithm to correctly solve the batch processing problem with localized destinations. We further propose two decomposition algorithms to deal with scenarios where the destinations are sparse. Extensive evaluations on a real-world road network verify the superiority of our algorithm compared with state-of-the-art methods.

Original language	English
Title of host publication	Databases Theory and Applications - 30th Australasian Database Conference, ADC 2019, Proceedings
Editors	Lijun Chang, Xin Cao, Junhao Gan
Publisher	Springer Verlag
Pages	3-16
Number of pages	14
ISBN (Print)	9783030120788
DOIs	https://doi.org/10.1007/978-3-030-12079-5_1
Publication status	Published - 2019
Externally published	Yes
Event	30th Australasian Database Conference, ADC 2019 - Sydney, Australia Duration: 29 Jan 2019 → 1 Feb 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11393 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	30th Australasian Database Conference, ADC 2019
Country/Territory	Australia
City	Sydney
Period	29/01/19 → 1/02/19

Keywords

Batch process
Road network
Shortest path

ASJC Scopus subject areas

Information Systems

More information

10.1007/978-3-030-12079-5_1

Cite this

Zhang, M., Li, L., Hua, W., & Zhou, X. (2019). Batch Processing of Shortest Path Queries in Road Networks. In L. Chang, X. Cao, & J. Gan (Eds.), Databases Theory and Applications - 30th Australasian Database Conference, ADC 2019, Proceedings (pp. 3-16). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11393 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-12079-5_1

Zhang, Mengxuan ; Li, Lei ; Hua, Wen et al. / Batch Processing of Shortest Path Queries in Road Networks. Databases Theory and Applications - 30th Australasian Database Conference, ADC 2019, Proceedings. editor / Lijun Chang ; Xin Cao ; Junhao Gan. Springer Verlag, 2019. pp. 3-16 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{38ddac5d30474cbd96ffe078d3658dde,

title = "Batch Processing of Shortest Path Queries in Road Networks",

abstract = "Shortest path algorithm is a foundation to various location-based services (LBS) and has been extensively studied in the literature. However, server-side shortest path calculation faces a severe scalability issue when the business expands and a huge amount of requests are submitted to the server simultaneously. Although a straightforward solution widely-adopted in current industry is to deploy more processing resources, in this work, we aim to improve the efficiency algorithmically by answering queries in a batch and reusing shareable computations. In particular, we generalize the goal-directed A* algorithm to correctly solve the batch processing problem with localized destinations. We further propose two decomposition algorithms to deal with scenarios where the destinations are sparse. Extensive evaluations on a real-world road network verify the superiority of our algorithm compared with state-of-the-art methods.",

keywords = "Batch process, Road network, Shortest path",

author = "Mengxuan Zhang and Lei Li and Wen Hua and Xiaofang Zhou",

note = "Funding Information: This research is partially supported by the Australian Research Council (Grants No. DP150103008 and DP170101172). Funding Information: Acknowledgment. This research is partially supported by the Australian Research Council (Grants No. DP150103008 and DP170101172). Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 30th Australasian Database Conference, ADC 2019 ; Conference date: 29-01-2019 Through 01-02-2019",

year = "2019",

doi = "10.1007/978-3-030-12079-5_1",

language = "English",

isbn = "9783030120788",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "3--16",

editor = "Lijun Chang and Xin Cao and Junhao Gan",

booktitle = "Databases Theory and Applications - 30th Australasian Database Conference, ADC 2019, Proceedings",

address = "Germany",

}

Zhang, M, Li, L, Hua, W & Zhou, X 2019, Batch Processing of Shortest Path Queries in Road Networks. in L Chang, X Cao & J Gan (eds), Databases Theory and Applications - 30th Australasian Database Conference, ADC 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11393 LNCS, Springer Verlag, pp. 3-16, 30th Australasian Database Conference, ADC 2019, Sydney, Australia, 29/01/19. https://doi.org/10.1007/978-3-030-12079-5_1

Batch Processing of Shortest Path Queries in Road Networks. / Zhang, Mengxuan; Li, Lei; Hua, Wen et al.
Databases Theory and Applications - 30th Australasian Database Conference, ADC 2019, Proceedings. ed. / Lijun Chang; Xin Cao; Junhao Gan. Springer Verlag, 2019. p. 3-16 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11393 LNCS).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - Batch Processing of Shortest Path Queries in Road Networks

AU - Zhang, Mengxuan

AU - Li, Lei

AU - Hua, Wen

AU - Zhou, Xiaofang

N1 - Funding Information: This research is partially supported by the Australian Research Council (Grants No. DP150103008 and DP170101172). Funding Information: Acknowledgment. This research is partially supported by the Australian Research Council (Grants No. DP150103008 and DP170101172). Publisher Copyright: © 2019, Springer Nature Switzerland AG.

PY - 2019

Y1 - 2019

N2 - Shortest path algorithm is a foundation to various location-based services (LBS) and has been extensively studied in the literature. However, server-side shortest path calculation faces a severe scalability issue when the business expands and a huge amount of requests are submitted to the server simultaneously. Although a straightforward solution widely-adopted in current industry is to deploy more processing resources, in this work, we aim to improve the efficiency algorithmically by answering queries in a batch and reusing shareable computations. In particular, we generalize the goal-directed A* algorithm to correctly solve the batch processing problem with localized destinations. We further propose two decomposition algorithms to deal with scenarios where the destinations are sparse. Extensive evaluations on a real-world road network verify the superiority of our algorithm compared with state-of-the-art methods.

AB - Shortest path algorithm is a foundation to various location-based services (LBS) and has been extensively studied in the literature. However, server-side shortest path calculation faces a severe scalability issue when the business expands and a huge amount of requests are submitted to the server simultaneously. Although a straightforward solution widely-adopted in current industry is to deploy more processing resources, in this work, we aim to improve the efficiency algorithmically by answering queries in a batch and reusing shareable computations. In particular, we generalize the goal-directed A* algorithm to correctly solve the batch processing problem with localized destinations. We further propose two decomposition algorithms to deal with scenarios where the destinations are sparse. Extensive evaluations on a real-world road network verify the superiority of our algorithm compared with state-of-the-art methods.

KW - Batch process

KW - Road network

KW - Shortest path

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

U2 - 10.1007/978-3-030-12079-5_1

DO - 10.1007/978-3-030-12079-5_1

M3 - Conference article published in proceeding or book

AN - SCOPUS:85061084631

SN - 9783030120788

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 16

BT - Databases Theory and Applications - 30th Australasian Database Conference, ADC 2019, Proceedings

A2 - Chang, Lijun

A2 - Cao, Xin

A2 - Gan, Junhao

PB - Springer Verlag

T2 - 30th Australasian Database Conference, ADC 2019

Y2 - 29 January 2019 through 1 February 2019

ER -

Zhang M, Li L, Hua W, Zhou X. Batch Processing of Shortest Path Queries in Road Networks. In Chang L, Cao X, Gan J, editors, Databases Theory and Applications - 30th Australasian Database Conference, ADC 2019, Proceedings. Springer Verlag. 2019. p. 3-16. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-12079-5_1

Batch Processing of Shortest Path Queries in Road Networks

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this