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

^*Corresponding author for this work

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › 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

Bibliographical note

Publisher Copyright:
© 2019, Springer Nature Switzerland AG.

Keywords

Batch process
Road network
Shortest path

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

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{316eaf77aaea41efa745fb22d650cfa9,

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 = "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",

}

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/Report › Conference Paper published in a book › 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

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 - https://www.webofscience.com/wos/woscc/full-record/WOS:000876918300001

UR - https://openalex.org/W2912492336

UR - https://www.scopus.com/pages/publications/85061084631

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

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

M3 - Conference Paper published in a book

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

Bibliographical note

Keywords

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this