Finding Top-k Shortest Paths with Diversity

Huiping Liu, Cheqing Jin, Bin Yang, Aoying Zhou

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

4 Citations (Scopus)

Abstract

The classical K Shortest Paths (KSP) problem, which identifies the k shortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for vehicle routing services. However, the returned k shortest paths may be highly similar, i.e., sharing significant amounts of edges, thus adversely affecting service qualities. In this paper, we formalize the K Shortest Paths with Diversity (KSPD) problem that identifies top-k shortest paths such that the paths are dissimilarwith each other and the total length of the paths is minimized. We first prove that the KSPD problem is NP-hard and then propose a generic greedy framework to solve the KSPD problem in the sense that (1) it supports a wide variety of path similarity metrics which are widely adopted in the literature and (2) it is also able to efficiently solve the traditional KSP problem if no path similarity metric is specified. The core of the framework includes the use of two judiciously designed lower bounds, where one is dependent on and the other one is independent on the chosen path similarity metric, which effectively reduces the search space and significantly improves efficiency. Empirical studies on five real-world and synthetic graphs and five different path similarity metrics offer insight into the design properties of the proposed general framework and offer evidence that the proposed lower bounds are effective.
Original languageEnglish
Title of host publication2018 IEEE 34th International Conference on Data Engineering (ICDE)
Number of pages2
PublisherIEEE
Publication date2018
Pages1761-1762
ISBN (Print) 978-1-5386-5521-4
ISBN (Electronic)978-1-5386-5520-7
DOIs
Publication statusPublished - 2018
Event34th IEEE International Conference on Data Engineering, ICDE 2018 - Paris, France
Duration: 16 Apr 201819 Apr 2018

Conference

Conference34th IEEE International Conference on Data Engineering, ICDE 2018
CountryFrance
CityParis
Period16/04/201819/04/2018
SeriesProceedings of the International Conference on Data Engineering
ISSN1063-6382

Fingerprint

Vehicle routing
Directed graphs
Computational complexity

Cite this

Liu, H., Jin, C., Yang, B., & Zhou, A. (2018). Finding Top-k Shortest Paths with Diversity. In 2018 IEEE 34th International Conference on Data Engineering (ICDE) (pp. 1761-1762). IEEE. Proceedings of the International Conference on Data Engineering https://doi.org/10.1109/ICDE.2018.00238
Liu, Huiping ; Jin, Cheqing ; Yang, Bin ; Zhou, Aoying. / Finding Top-k Shortest Paths with Diversity. 2018 IEEE 34th International Conference on Data Engineering (ICDE) . IEEE, 2018. pp. 1761-1762 (Proceedings of the International Conference on Data Engineering).
@inproceedings{2df0be19913d414eafea3cac5c9d7779,
title = "Finding Top-k Shortest Paths with Diversity",
abstract = "The classical K Shortest Paths (KSP) problem, which identifies the k shortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for vehicle routing services. However, the returned k shortest paths may be highly similar, i.e., sharing significant amounts of edges, thus adversely affecting service qualities. In this paper, we formalize the K Shortest Paths with Diversity (KSPD) problem that identifies top-k shortest paths such that the paths are dissimilarwith each other and the total length of the paths is minimized. We first prove that the KSPD problem is NP-hard and then propose a generic greedy framework to solve the KSPD problem in the sense that (1) it supports a wide variety of path similarity metrics which are widely adopted in the literature and (2) it is also able to efficiently solve the traditional KSP problem if no path similarity metric is specified. The core of the framework includes the use of two judiciously designed lower bounds, where one is dependent on and the other one is independent on the chosen path similarity metric, which effectively reduces the search space and significantly improves efficiency. Empirical studies on five real-world and synthetic graphs and five different path similarity metrics offer insight into the design properties of the proposed general framework and offer evidence that the proposed lower bounds are effective.",
author = "Huiping Liu and Cheqing Jin and Bin Yang and Aoying Zhou",
year = "2018",
doi = "10.1109/ICDE.2018.00238",
language = "English",
isbn = "978-1-5386-5521-4",
series = "Proceedings of the International Conference on Data Engineering",
publisher = "IEEE",
pages = "1761--1762",
booktitle = "2018 IEEE 34th International Conference on Data Engineering (ICDE)",
address = "United States",

}

Liu, H, Jin, C, Yang, B & Zhou, A 2018, Finding Top-k Shortest Paths with Diversity. in 2018 IEEE 34th International Conference on Data Engineering (ICDE) . IEEE, Proceedings of the International Conference on Data Engineering, pp. 1761-1762, 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, 16/04/2018. https://doi.org/10.1109/ICDE.2018.00238

Finding Top-k Shortest Paths with Diversity. / Liu, Huiping; Jin, Cheqing; Yang, Bin; Zhou, Aoying.

2018 IEEE 34th International Conference on Data Engineering (ICDE) . IEEE, 2018. p. 1761-1762 (Proceedings of the International Conference on Data Engineering).

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - Finding Top-k Shortest Paths with Diversity

AU - Liu, Huiping

AU - Jin, Cheqing

AU - Yang, Bin

AU - Zhou, Aoying

PY - 2018

Y1 - 2018

N2 - The classical K Shortest Paths (KSP) problem, which identifies the k shortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for vehicle routing services. However, the returned k shortest paths may be highly similar, i.e., sharing significant amounts of edges, thus adversely affecting service qualities. In this paper, we formalize the K Shortest Paths with Diversity (KSPD) problem that identifies top-k shortest paths such that the paths are dissimilarwith each other and the total length of the paths is minimized. We first prove that the KSPD problem is NP-hard and then propose a generic greedy framework to solve the KSPD problem in the sense that (1) it supports a wide variety of path similarity metrics which are widely adopted in the literature and (2) it is also able to efficiently solve the traditional KSP problem if no path similarity metric is specified. The core of the framework includes the use of two judiciously designed lower bounds, where one is dependent on and the other one is independent on the chosen path similarity metric, which effectively reduces the search space and significantly improves efficiency. Empirical studies on five real-world and synthetic graphs and five different path similarity metrics offer insight into the design properties of the proposed general framework and offer evidence that the proposed lower bounds are effective.

AB - The classical K Shortest Paths (KSP) problem, which identifies the k shortest paths in a directed graph, plays an important role in many application domains, such as providing alternative paths for vehicle routing services. However, the returned k shortest paths may be highly similar, i.e., sharing significant amounts of edges, thus adversely affecting service qualities. In this paper, we formalize the K Shortest Paths with Diversity (KSPD) problem that identifies top-k shortest paths such that the paths are dissimilarwith each other and the total length of the paths is minimized. We first prove that the KSPD problem is NP-hard and then propose a generic greedy framework to solve the KSPD problem in the sense that (1) it supports a wide variety of path similarity metrics which are widely adopted in the literature and (2) it is also able to efficiently solve the traditional KSP problem if no path similarity metric is specified. The core of the framework includes the use of two judiciously designed lower bounds, where one is dependent on and the other one is independent on the chosen path similarity metric, which effectively reduces the search space and significantly improves efficiency. Empirical studies on five real-world and synthetic graphs and five different path similarity metrics offer insight into the design properties of the proposed general framework and offer evidence that the proposed lower bounds are effective.

U2 - 10.1109/ICDE.2018.00238

DO - 10.1109/ICDE.2018.00238

M3 - Article in proceeding

SN - 978-1-5386-5521-4

T3 - Proceedings of the International Conference on Data Engineering

SP - 1761

EP - 1762

BT - 2018 IEEE 34th International Conference on Data Engineering (ICDE)

PB - IEEE

ER -

Liu H, Jin C, Yang B, Zhou A. Finding Top-k Shortest Paths with Diversity. In 2018 IEEE 34th International Conference on Data Engineering (ICDE) . IEEE. 2018. p. 1761-1762. (Proceedings of the International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2018.00238