Semantic‐Aware Top‐k Multirequest Optimal Route
Authors:
Open Access
- 1 January 2019
- journal article
- research article
- Published by Wiley in Complexity
- Vol. 2019 (1)
Abstract
In recent years, research on location‐based services has received a lot of interest, in both industry and academic aspects, due to a wide range of potential applications. Among them, one of the active topic areas is the route planning on a point‐of‐interest (POI) network. We study the top‐k optimal routes querying on large, general graphs where the edge weights may not satisfy the triangle inequality. The query strives to find the top‐k optimal routes from a given source, which must visit a number of vertices with all the services that the user needs. Existing POI query methods mainly focus on the textual similarities and ignore the semantic understanding of keywords in spatial objects and queries. To address this problem, this paper studies the semantic similarity of POI keyword searching in the route. Another problem is that most of the previous studies consider that a POI belongs to a category, and they do not consider that a POI may provide various kinds of services even in the same category. So, we propose a novel top‐k optimal route planning algorithm based on semantic perception (KOR‐SP). In KOR‐SP, we define a dominance relationship between two partially explored routes which leads to a smaller searching space and consider the semantic similarity of keywords and the number of single POI’s services. We use an efficient label indexing technique for the shortest path queries to further improve efficiency. Finally, we perform an extensive experimental evaluation on multiple real‐world graphs to demonstrate that the proposed methods deliver excellent performance.Keywords
Funding Information
- National Natural Science Foundation of China (N161704004, 61602102, 61872069)
This publication has 26 references indexed in Scilit:
- On personalized and sequenced route planningWorld Wide Web, 2015
- Mining User Check-In Behavior with a Random Walk for Urban Point-of-Interest RecommendationsACM Transactions on Intelligent Systems and Technology, 2014
- Trip Recommendation with Multiple User Constraints by Integrating Point-of-Interests and Travel Packages2014
- Keyword-aware optimal route searchProceedings of the VLDB Endowment, 2012
- Hierarchical Hub Labelings for Shortest Paths2012
- The optimal sequenced route queryThe VLDB Journal, 2007
- Reachability and Distance Queries via 2-Hop LabelsSIAM Journal on Computing, 2003
- Approximation algorithms for the geometric covering salesman problemDiscrete Applied Mathematics, 1994
- A note on two problems in connexion with graphsNumerische Mathematik, 1959
- Ergebnisse eines mathematischen KolloquiumsMonatshefte für Mathematik, 1932