Sequenced Route Query with Semantic Hierarchy
Sequenced Route Query with Semantic Hierarchy
复制标题
DOI：
10.5441/002/edbt.2018.05
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Yuya Sasaki;Y. Ishikawa;Y. Fujiwara;Makoto Onizuka
中科院分区：
文献类型：
--
作者：
Yuya Sasaki;Y. Ishikawa;Y. Fujiwara;Makoto Onizuka
行程规划查询搜索从给定点出发经过多个符合用户需求的兴趣点 (PoI) 的首选路线。尽管之前的研究已经调查了行程计划查询，但它们在查找路线方面缺乏灵活性，因为它们都输出严格符合用户需求的路线。我们研究以灵活的方式输出多条路线的旅行计划查询。我们提出了一种称为天际线排序路线（SkySR）查询的新型查询，它通过利用路线中 PoI 的语义相似性扩展最短路线搜索来搜索用户的所有首选排序路线。灵活性是通过 PoI 类别的{\it 语义层次结构}实现的。我们提出了一种用于 SkySR 查询的有效算法，即批量 SkySR 算法，该算法可同时搜索有序路由并有效地修剪不必要的路由。实验评估表明，所提出的方法在响应时间方面显着优于现有方法（高达四个数量级）。此外，我们开发了一个使用 SkySR 查询的原型服务，并进行用户测试来评估其实用性。
The trip planning query searches for preferred routes starting from a given point through multiple Point-of-Interests (PoI) that match user requirements. Although previous studies have investigated trip planning queries, they lack flexibility for finding routes because all of them output routes that strictly match user requirements. We study trip planning queries that output multiple routes in a flexible manner. We propose a new type of query called skyline sequenced route (SkySR) query, which searches for all preferred sequenced routes to users by extending the shortest route search with the semantic similarity of PoIs in the route. Flexibility is achieved by the {\it semantic hierarchy} of the PoI category. We propose an efficient algorithm for the SkySR query, bulk SkySR algorithm that simultaneously searches for sequenced routes and prunes unnecessary routes effectively. Experimental evaluations show that the proposed approach significantly outperforms the existing approaches in terms of response time (up to four orders of magnitude). Moreover, we develop a prototype service that uses the SkySR query, and conduct a user test to evaluate its usefulness.