An efficient approach for searching optimal multi-keywords coverage routes

Rong Yang (), Baoning Niu () and Pengfei Jin ()
Additional contact information
Rong Yang: Taiyuan University of Technology
Baoning Niu: Taiyuan University of Technology
Pengfei Jin: ZheJiangUniversity

Journal of Combinatorial Optimization, 2022, vol. 44, issue 2, No 12, 1104-1133

Abstract: Abstract Keyword-aware optimal route queries are a combinatorial optimization problem with three factors, namely keyword coverage, route budget constraint and route popularity, which is NP-hard. Previous work takes an adjacent edge expansion approach to get an approximate result and the computational complexity is proportional to the number of vertices and edges of the road network, which is not scalable for large road networks or road networks with sparse points of interest. Motivated by this, we propose an algorithm called Keyword-aware Skyline Route Generating (KSRG*). KSRG* consists of a preprocessing stage, in which KSRG* computes all the skyline routes for each pair of vertices, and an expansion stage, in which KSRG* expands feasible routes from the source vertex to target vertex via vertices containing keywords. Based on KSRG*, another two approximation algorithms with performance guarantees, namely KSRG $$^{+}$$ + and KSRG $$^{++}$$ + + are proposed. KSRG $$^{+}$$ + applies three acceleration strategies to KSRG* to greatly reduce the routes to be expanded. KSRG $$^{++}$$ + + combines KSRG $$^{+}$$ + with a clustering strategy to solve the inefficient performance when the number of the vertices containing the same query keyword is large. Comprehensive experiments on the datasets of four real road networks show that the execution time and accuracy of results of KSRG $$^+$$ + and KSRG $$^{++}$$ + + outperform the state of the art methods.

Keywords: Route query; Edge expansion; Keyword converage; Skyline routes (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00878-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:2:d:10.1007_s10878-022-00878-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00878-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().