天際線旅遊路線: 旅遊路線推薦的天際線探勘

Skyline Travel Route: Exploring Skyline for Travel Route Recommendation

許菀庭(Wan-Ting Hsu)

指導教授 ： 彭文志

國立交通大學/資訊學院/資訊科學與工程研究所/碩士(2014年)

https://doi.org/10.6842/NCTU.2014.00292

摘要

With the advance of location positioning technology and some geo-Web services (e.g., EveryTrail), users can easily use mobile Apps to record their travel experiences via photos and trip trajectories. Prior works have elaborated on trip planning in mining travel routes from a huge number of trajectories. However, most of the travel routes mined may have some overlapping Regions-Of-Interest (ROIs) information, which incur some redundant travel information. Moreover, each ROI may have its appropriate visiting time, and users may also have their own preferred must-see ROIs (referred to as a set of query points). The above two factors are not considered in prior works. Thus, in this paper, given a spatial range $Q$ and a set of query points specified by users, the goal of this paper is to return the travel routes that fulfill two requirements: 1.) travel routes should contain all those query points specified, and 2.) travel routes should be within the spatial range Q. Furthermore, we claim that each query point may have its proper visiting time. As such, the travel routes should go through these query points at their corresponding proper visiting time. To avoid some redundant information in the travel routes, we utilize the skyline concept to retrieve travel routes with more diversity. Specifically, in our paper, we consider some factors, such as the visiting time information of POIs and the set of query points, in retrieving travel routes. These factors could be mapped into dimensional spaces. Then, each travel route is viewed as a data point in the dimensional space. Thus, skyline data points (referred to as skyline travel routes) are returned as the query result. To evaluate our proposed methods, we conducted extensive experiments on real datasets. The experimental results show that skyline travel routes indeed provide more diversity in the query result. In addition, we evaluate the efficiency of retrieving skyline travel routes.

關鍵字

軌跡模式挖掘 ； 軌跡搜尋 ； 旅遊路線規劃 ； 路線天際線查詢

並列摘要

With the advance of location positioning technology and some geo-Web services (e.g., EveryTrail), users can easily use mobile Apps to record their travel experiences via photos and trip trajectories. Prior works have elaborated on trip planning in mining travel routes from a huge number of trajectories. However, most of the travel routes mined may have some overlapping Regions-Of-Interest (ROIs) information, which incur some redundant travel information. Moreover, each ROI may have its appropriate visiting time, and users may also have their own preferred must-see ROIs (referred to as a set of query points). The above two factors are not considered in prior works. Thus, in this paper, given a spatial range $Q$ and a set of query points specified by users, the goal of this paper is to return the travel routes that fulfill two requirements: 1.) travel routes should contain all those query points specified, and 2.) travel routes should be within the spatial range Q. Furthermore, we claim that each query point may have its proper visiting time. As such, the travel routes should go through these query points at their corresponding proper visiting time. To avoid some redundant information in the travel routes, we utilize the skyline concept to retrieve travel routes with more diversity. Specifically, in our paper, we consider some factors, such as the visiting time information of POIs and the set of query points, in retrieving travel routes. These factors could be mapped into dimensional spaces. Then, each travel route is viewed as a data point in the dimensional space. Thus, skyline data points (referred to as skyline travel routes) are returned as the query result. To evaluate our proposed methods, we conducted extensive experiments on real datasets. The experimental results show that skyline travel routes indeed provide more diversity in the query result. In addition, we evaluate the efficiency of retrieving skyline travel routes.

並列關鍵字

trajectory pattern mining ； trajectory search ； travel route planning ； route skyline query

參考文獻

[1] Z. Chen, H. T. Shen, X. Zhou, Y. Zheng, and X. Xie, Searching trajectories by lo cations: an eciency study. in SIGMOD Conference, 2010,

[7] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma, Mining interesting locations and travel sequences from gps tra jectories for mobile users, in Proceedings of the 18th International Conference on World Wide Web (WWW) , 2009, pp. 791800.

[8] K. Zheng, S. Shang, N. J. Yuan, Y. Yang, and U. Computing, Towards efficient search for activity trajectories. ICDE, 2013.

[9] X. Cao, G. Cong, and C. S. Jensen, Mining signicant semantic lo cations from gps data, Proceedings of the VLDB Endowment, vol. 3, no.

[11] D. J. Crandall, L. Backstrom, D. Huttenlo cher, and J. Kleinb erg, Mapping the world's photos, in Proceedings of the 18th international conference on World wide web. ACM, 2009, pp. 761770.