Edge-Based Shortest Path Caching in Road Networks

Detian Zhang; An Liu; Gaoming Jin; Qing Li

doi:10.1007/978-3-030-18590-9_56

Edge-Based Shortest Path Caching in Road Networks

Detian Zhang, An Liu, Gaoming Jin, Qing Li

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

Abstract

In this paper, we propose an edge-based shortest path cache that can efficiently handle large-scale path queries without needing any road information. We achieve this by designing a totally new edge-based path cache structure, an efficient R-tree-based cache lookup algorithm, and a greedy-based cache construction algorithm. Experiments on a real road network and real POI datasets are conducted, and the results show the efficiency of our proposed caching techniques.

Original language	English
Title of host publication	Database Systems for Advanced Applications - DASFAA 2019 International Workshops
Subtitle of host publication	BDMS, BDQM, and GDMA, Proceedings
Editors	Guoliang Li, Jun Yang, Joao Gama, Juggapong Natwichai, Yongxin Tong
Publisher	Springer-Verlag
Pages	411-414
Number of pages	4
ISBN (Print)	9783030185893
DOIs	https://doi.org/10.1007/978-3-030-18590-9_56
Publication status	Published - 1 Jan 2019
Event	24th International Conference on Database Systems for Advanced Applications, DASFAA 2019 - Chiang Mai, Thailand Duration: 22 Apr 2019 → 25 Apr 2019

Publication series

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

Conference

Conference	24th International Conference on Database Systems for Advanced Applications, DASFAA 2019
Country/Territory	Thailand
City	Chiang Mai
Period	22/04/19 → 25/04/19

Keywords

Large-scale
Path cache
Shortest path queries

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

More information

10.1007/978-3-030-18590-9_56

Cite this

Zhang, D., Liu, A., Jin, G., & Li, Q. (2019). Edge-Based Shortest Path Caching in Road Networks. In G. Li, J. Yang, J. Gama, J. Natwichai, & Y. Tong (Eds.), Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Proceedings (pp. 411-414). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11448 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-030-18590-9_56

Zhang, Detian ; Liu, An ; Jin, Gaoming et al. / Edge-Based Shortest Path Caching in Road Networks. Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Proceedings. editor / Guoliang Li ; Jun Yang ; Joao Gama ; Juggapong Natwichai ; Yongxin Tong. Springer-Verlag, 2019. pp. 411-414 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{5a46691373a94551a4210e6ba0ff6772,

title = "Edge-Based Shortest Path Caching in Road Networks",

abstract = "In this paper, we propose an edge-based shortest path cache that can efficiently handle large-scale path queries without needing any road information. We achieve this by designing a totally new edge-based path cache structure, an efficient R-tree-based cache lookup algorithm, and a greedy-based cache construction algorithm. Experiments on a real road network and real POI datasets are conducted, and the results show the efficiency of our proposed caching techniques.",

keywords = "Large-scale, Path cache, Shortest path queries",

author = "Detian Zhang and An Liu and Gaoming Jin and Qing Li",

year = "2019",

month = jan,

day = "1",

doi = "10.1007/978-3-030-18590-9_56",

language = "English",

isbn = "9783030185893",

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

publisher = "Springer-Verlag",

pages = "411--414",

editor = "Guoliang Li and Jun Yang and Joao Gama and Juggapong Natwichai and Yongxin Tong",

booktitle = "Database Systems for Advanced Applications - DASFAA 2019 International Workshops",

note = "24th International Conference on Database Systems for Advanced Applications, DASFAA 2019 ; Conference date: 22-04-2019 Through 25-04-2019",

}

Zhang, D, Liu, A, Jin, G & Li, Q 2019, Edge-Based Shortest Path Caching in Road Networks. in G Li, J Yang, J Gama, J Natwichai & Y Tong (eds), Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11448 LNCS, Springer-Verlag, pp. 411-414, 24th International Conference on Database Systems for Advanced Applications, DASFAA 2019, Chiang Mai, Thailand, 22/04/19. https://doi.org/10.1007/978-3-030-18590-9_56

Edge-Based Shortest Path Caching in Road Networks. / Zhang, Detian; Liu, An; Jin, Gaoming et al.
Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Proceedings. ed. / Guoliang Li; Jun Yang; Joao Gama; Juggapong Natwichai; Yongxin Tong. Springer-Verlag, 2019. p. 411-414 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11448 LNCS).

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

TY - GEN

T1 - Edge-Based Shortest Path Caching in Road Networks

AU - Zhang, Detian

AU - Liu, An

AU - Jin, Gaoming

AU - Li, Qing

PY - 2019/1/1

Y1 - 2019/1/1

N2 - In this paper, we propose an edge-based shortest path cache that can efficiently handle large-scale path queries without needing any road information. We achieve this by designing a totally new edge-based path cache structure, an efficient R-tree-based cache lookup algorithm, and a greedy-based cache construction algorithm. Experiments on a real road network and real POI datasets are conducted, and the results show the efficiency of our proposed caching techniques.

AB - In this paper, we propose an edge-based shortest path cache that can efficiently handle large-scale path queries without needing any road information. We achieve this by designing a totally new edge-based path cache structure, an efficient R-tree-based cache lookup algorithm, and a greedy-based cache construction algorithm. Experiments on a real road network and real POI datasets are conducted, and the results show the efficiency of our proposed caching techniques.

KW - Large-scale

KW - Path cache

KW - Shortest path queries

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

U2 - 10.1007/978-3-030-18590-9_56

DO - 10.1007/978-3-030-18590-9_56

M3 - Conference article published in proceeding or book

AN - SCOPUS:85065416932

SN - 9783030185893

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

SP - 411

EP - 414

BT - Database Systems for Advanced Applications - DASFAA 2019 International Workshops

A2 - Li, Guoliang

A2 - Yang, Jun

A2 - Gama, Joao

A2 - Natwichai, Juggapong

A2 - Tong, Yongxin

PB - Springer-Verlag

T2 - 24th International Conference on Database Systems for Advanced Applications, DASFAA 2019

Y2 - 22 April 2019 through 25 April 2019

ER -

Zhang D, Liu A, Jin G, Li Q. Edge-Based Shortest Path Caching in Road Networks. In Li G, Yang J, Gama J, Natwichai J, Tong Y, editors, Database Systems for Advanced Applications - DASFAA 2019 International Workshops: BDMS, BDQM, and GDMA, Proceedings. Springer-Verlag. 2019. p. 411-414. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-18590-9_56

Edge-Based Shortest Path Caching in Road Networks

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this