Semantic-Aware Top-k Multirequest Optimal Route
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...
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2019-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2019/4047894 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832547561384181760 |
|---|---|
| author | Shuang Wang Yingchun Xu Yinzhe Wang Hezhi Liu Qiaoqiao Zhang Tiemin Ma Shengnan Liu Siyuan Zhang Anliang Li |
| author_facet | Shuang Wang Yingchun Xu Yinzhe Wang Hezhi Liu Qiaoqiao Zhang Tiemin Ma Shengnan Liu Siyuan Zhang Anliang Li |
| author_sort | Shuang Wang |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-343d685746d545359b2bfdcc69b03d61 |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2019-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-343d685746d545359b2bfdcc69b03d612025-02-03T06:44:14ZengWileyComplexity1076-27871099-05262019-01-01201910.1155/2019/40478944047894Semantic-Aware Top-k Multirequest Optimal RouteShuang Wang0Yingchun Xu1Yinzhe Wang2Hezhi Liu3Qiaoqiao Zhang4Tiemin Ma5Shengnan Liu6Siyuan Zhang7Anliang Li8Software College, Northeastern University, Shenyang 110004, ChinaSoftware College, Northeastern University, Shenyang 110004, ChinaSoftware College, Northeastern University, Shenyang 110004, ChinaSoftware College, Northeastern University, Shenyang 110004, ChinaSoftware College, Northeastern University, Shenyang 110004, ChinaSoftware College, Northeastern University, Shenyang 110004, ChinaSoftware College, Northeastern University, Shenyang 110004, ChinaSoftware College, Northeastern University, Shenyang 110004, ChinaSoftware College, Northeastern University, Shenyang 110004, ChinaIn 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.http://dx.doi.org/10.1155/2019/4047894 |
| spellingShingle | Shuang Wang Yingchun Xu Yinzhe Wang Hezhi Liu Qiaoqiao Zhang Tiemin Ma Shengnan Liu Siyuan Zhang Anliang Li Semantic-Aware Top-k Multirequest Optimal Route Complexity |
| title | Semantic-Aware Top-k Multirequest Optimal Route |
| title_full | Semantic-Aware Top-k Multirequest Optimal Route |
| title_fullStr | Semantic-Aware Top-k Multirequest Optimal Route |
| title_full_unstemmed | Semantic-Aware Top-k Multirequest Optimal Route |
| title_short | Semantic-Aware Top-k Multirequest Optimal Route |
| title_sort | semantic aware top k multirequest optimal route |
| url | http://dx.doi.org/10.1155/2019/4047894 |
| work_keys_str_mv | AT shuangwang semanticawaretopkmultirequestoptimalroute AT yingchunxu semanticawaretopkmultirequestoptimalroute AT yinzhewang semanticawaretopkmultirequestoptimalroute AT hezhiliu semanticawaretopkmultirequestoptimalroute AT qiaoqiaozhang semanticawaretopkmultirequestoptimalroute AT tieminma semanticawaretopkmultirequestoptimalroute AT shengnanliu semanticawaretopkmultirequestoptimalroute AT siyuanzhang semanticawaretopkmultirequestoptimalroute AT anliangli semanticawaretopkmultirequestoptimalroute |